Hasil BB(3, 4) > Ack(14)

BB(3, 4) > Ack(14)

• 22 Mei 2024
  • Pavel menemukan mesin Turing 3-status 4-simbol (Turing Machine, TM)
  • Mesin ini menghitung fungsi tingkat "Ackermann" dan berhenti dengan tepat (2↑155)+14 simbol non-nol
  • Karena notasi panah atas Knuth menjadi agak merepotkan, ini dapat didekati sebagai berikut: BB(3,4)>Ack(14)
  • Di sini Ack(14) didefinisikan sebagai bilangan Ackermann ke-14: Ack(n)=n↑nn
  • Mesin ini adalah TM pertama yang dapat mensimulasikan fungsi tingkat Ackermann yang ditemukan "di alam liar"

Mesin

• Tabel transisi status

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3LB | 1RZ | 2RA |
  | B   | 2LC | 3RB | 1LC | 2RA |
  | C   | 3RB | 1LB | 3LC | 2RC |
  

• Konfigurasi akhir

  • 0∞32g153(0)+12161 Z> 0∞
  • Tepat σ=2g153(0)+18=(2↑155)+14 simbol non-nol tersisa di pita

Attribution

• Penemu
  • TM ini ditemukan oleh Pavel Kropitz(@uni) dan dibagikan di Discord pada 25 April 2024
  • Kodenya tidak dapat menentukan batas yang mudah dibaca manusia untuk skor TM, dan hanya dinyatakan sebagai Halt(SuperPowers(13))
  • Ia mulai memverifikasi hasil ini menggunakan "validator bukti induktif" yang baru
  • Pada 20 Mei 2024, definisi tepat gkn(m) berhasil diekstrak dan diperoleh batas σ>2↑153
  • Matthew House(@LegionMammal978) menemukan bentuk tertutup sederhana gkn(0)=2↑k(n+2)2−2 pada 22 Mei 2024

Analisis

• Definisi B(k,n,m)

  B(k,n,m)=0∞32m+12k A> 1n
  

• Bukti

  0∞A>0∞→241B(16,3,0)20∞
  B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
  B(k,0,m)2→10∞32m+12k1Z>
  

• Definisi gk(m)

  g0(m)=m+1
  gk+1(m)=gk2m+2(0)
  

Bukti dengan induksi ganda

• Aturan utama

  B(k,n,m)→B(k,0,gk−1n(m))
  

• Lemma 1

  For all k≥1: 32k<B→2k+12k<B1
  

• Corollary 2

  For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m
  

• Theorem 3

  For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))
  

Nilai tepat

• Theorem

  For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)
  

• Corollary

  For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)
  

• Kesimpulan

  σ=2g153(0)+18=(2↑155)+14
  

Permutasi

• Mulai dari status B

  σB=2g63(0)+9=(2↑65)+5
  

• Mulai dari status C

  σC=2g03(0)+3=(2↑05)−1=9 (berhenti dalam 72 langkah)
  

• TNF yang ditransformasikan

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3RB | 1LC | 2LA |
  | B   | 2LA | 2RB | 1LB | 3RA |
  | C   | 3LA | 1RZ | 1LC | 2RA |
  

Bukan Collatz

• Hal menarik
  • TM ini sangat sederhana secara mengejutkan
  • Tidak ada aturan seperti Collatz
  • Ini tidak menutup kemungkinan adanya TM tingkat Ackermann yang mirip Collatz

Validator Bukti Induktif

• Tujuan proyek
  • Sedang mengembangkan validator "bukti induktif"
  • Mengembangkan format sertifikat terstandarisasi agar dapat memverifikasi berbagai bukti induktif
  • Masih pada tahap awal, tetapi sudah berhasil membuktikan perilaku beberapa TM

Opini GN⁺

• Hal menarik

  • Artikel ini sangat membantu untuk memahami kompleksitas mesin Turing dan fungsi Ackermann
  • Menarik bahwa aturan sederhana dapat melakukan perhitungan yang kompleks

• Sudut pandang kritis

  • Untuk memahami kompleksitas mesin ini dibutuhkan pengetahuan latar belakang matematika
  • Fokusnya lebih pada ketertarikan teoretis daripada aplikasi praktis

• Teknologi terkait

  • Validator bukti induktif dapat memberikan kontribusi besar pada pengembangan sistem pembuktian matematika otomatis
  • Ada kemungkinan diterapkan pada masalah komputasi kompleks lainnya

• Hal yang perlu dipertimbangkan

  • Saat mengadopsi teknologi ini, akurasi dan efisiensi proses verifikasi perlu dipertimbangkan
  • Memahami dan menerapkan konsep matematika yang kompleks membutuhkan waktu

[GN⁺]

Opini Hacker News

Ringkasan kumpulan komentar Hacker News

• Program mesin Turing yang sederhana
  Berbeda dari anggapan bahwa program mesin Turing akan berupa kode spageti yang rumit, program baru ini relatif sederhana. Ada tiga state (A, B, C), dan state B meneruskan kontrol ke A dan C, tetapi A dan C tidak saling mengenal dan hanya meneruskan kontrol ke B. Ini adalah struktur modular; pada kode spageti yang sesungguhnya, setiap state dapat meneruskan kontrol ke semua state lainnya.

• Karakteristik yang menarik
  Program ini tidak mencetak sel kosong, dan semua instruksi mengubah state atau warna. Pemegang rekor baru BB(3,4) memiliki sekitar 64 bit informasi. BBλ(49) dengan 49 bit jauh melampaui bilangan Graham.

• Contoh implementasi
  Hasil implementasi langsung menunjukkan bahwa state B mengubah 0 menjadi 2, 1 menjadi 1, lalu beralih ke C; sedangkan state C mengubah 3 menjadi 2 lalu beralih ke A. Ini membuat rangkaian 3 menjadi panjang secara eksponensial.

• Kemiripan dengan code golf
  Semua ini terlihat seperti code golf yang ekstrem. Proyek hobi pribadi bernama BitGrid hanya memiliki state 4 bit per sel, dan grid 4x4 dapat menghitung hingga maksimum 2^64. Pada grid kecil, sambungan tepi sangat memengaruhi hasil.

• Permintaan materi interpretasi mesin Turing
  Ada permintaan materi tentang cara menafsirkan tabel. Ini tampaknya merupakan deskripsi mesin Turing.

• Batasan mesin Turing
  Jumlah mesin Turing yang dapat dijelaskan dengan jumlah simbol terbatas juga terbatas. Fakta bahwa beberapa mesin Turing dapat menjalankan jumlah langkah yang sangat besar sebelum berhenti terasa mengejutkan.

• Permintaan penjelasan tentang hal istimewanya
  Ada permintaan penjelasan mengapa himpunan instruksi tertentu ini begitu mengesankan. Juga muncul rasa ingin tahu tentang seperti apa fungsi setingkat fungsi Ackermann, dan sebenarnya apa yang dihitungnya.

• Ketertarikan pada kebenaran matematis
  Hasil yang tampak tidak berguna ini terasa lebih menarik daripada kemajuan LLM yang sangat berguna. Alasannya adalah adanya ketertarikan alami pada kebenaran matematis yang sederhana.

• Perbandingan BB(5) dan BB(3,4)
  Ada pertanyaan apakah BB(5) lebih besar daripada BB(3,4). Di situs bbchallenge.org, BB(5) disebut sekitar 47 juta, tetapi BB(3,4) dikatakan jauh lebih besar.

• Pemberian konteks oleh penulis
  Bagus bahwa penulis memberikan sebagian konteks.