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

 (sligocki.com)
1 poin oleh GN⁺ 2024-05-25 | 1 komentar | Bagikan ke WhatsApp
  • Sebuah TM juara Busy Beaver 3-state 4-symbol baru ditemukan, dan dihitung meninggalkan ((2 \uparrow^{15} 5) + 14) simbol non-nol saat berhenti
  • Angka ini sangat besar bahkan dalam notasi up-arrow Knuth, sehingga dirumuskan sebagai batas bawah (BB(3,4) > Ack(14)), melampaui bilangan Ackermann ke-14 yang didefinisikan sebagai (Ack(n)=n \uparrow^n n)
  • Perilaku inti TM dapat dikompresi mendekati (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), tetapi untuk menunjukkannya diperlukan induksi ganda
  • Berkat rumus evaluasi bentuk tertutup Matthew House, (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2), skor akhir (\sigma=(2 \uparrow^{15}5)+14) dapat ditulis secara tepat
  • TM ini menyimulasikan fungsi setingkat Ackermann bahkan tanpa percabangan sisa bergaya Collatz, dan juga digunakan sebagai kasus verifikasi untuk Inductive Proof Validator yang sedang dikembangkan

Skala juara Busy Beaver baru

  • Pavel Kropitz menemukan juara Busy Beaver 3-state 4-symbol baru
  • TM ini dapat menghitung fungsi “setingkat Ackermann”, dan saat berhenti meninggalkan jumlah simbol non-nol berikut di pita
    • ((2 \uparrow^{15} 5) + 14)
  • Karena nilainya sangat besar bahkan dalam notasi up-arrow Knuth, batas bawahnya dapat diringkas sebagai berikut
    • (BB(3,4) > Ack(14))
  • Di sini (Ack(14)) adalah bilangan Ackermann ke-14 yang didefinisikan sebagai (Ack(n)=n \uparrow^n n)
  • Dalam rentang yang diketahui, ini adalah kasus pertama di antara TM yang ditemukan dalam pencarian nyata yang dapat menyimulasikan fungsi setingkat Ackermann

Definisi TM dan konfigurasi akhir

  • String transisi TM adalah sebagai berikut
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • Tabel transisi didefinisikan untuk state A, B, C dan simbol 0, 1, 2, 3
    • A: 1RB, 3LB, 1RZ, 2RA
    • B: 2LC, 3RB, 1LC, 2RA
    • C: 3RB, 1LB, 3LC, 2RC
  • Konfigurasi akhirnya adalah sebagai berikut
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • Dari konfigurasi ini, skor (\sigma) dihitung secara tepat
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Proses penemuan dan verifikasi

  • Pavel Kropitz membagikan TM ini pada 25 April 2024 di Discord
  • Saat itu, kode belum dapat menentukan batas bawah skor yang mudah dibaca manusia, dan menampilkan hasil sebagai Halt(SuperPowers(13))
    • Ini berarti pembuktiannya memerlukan 13 lapis aturan induksi
  • Setelah itu, verifikasi menggunakan Inductive Proof Validator baru dimulai
  • Ketika verifikasi selesai pada 20 Mei 2024, definisi tepat (g_k^n(m)) berhasil diekstraksi, dan dari sana diperoleh batas bawah (\sigma > 2 \uparrow^{15} 3)
  • Matthew House menemukan rumus evaluasi bentuk tertutup sederhana berikut pada 22 Mei 2024
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • Dengan rumus evaluasi ini, nilai tepat (\sigma) dapat diekspresikan

Analisis perilaku dan bukti induksi ganda

  • Didefinisikan konfigurasi berikut
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • Setelah 241 langkah, konfigurasi awal mencapai state berikut
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • Aturan intinya adalah sebagai berikut
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), dengan (k \ge 1)
  • (g_k) didefinisikan dengan relasi rekursif berikut
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • Perilaku keseluruhannya cukup sederhana hingga hampir dapat dikompresi menjadi satu aturan, tetapi aturan itu sendiri harus dibuktikan dengan induksi ganda
  • Lemma dan korolari membahas proses state B memproses blok 3 dan 2^k untuk menghasilkan 1
    • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
    • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
  • Teorema 3 menunjukkan bahwa aturan inti berlaku untuk semua (k \ge 1, n \ge 0, m \ge 0)
    • Kasus dasar (k=1) ditangani dengan induksi terhadap (n)
    • Langkah induksi menggunakan asumsi terhadap (k) dan asumsi induksi terhadap (n) secara bersamaan

Perhitungan nilai tepat

  • (g_k) memiliki evaluasi bentuk tertutup yang relatif sederhana dengan hanya memakai up-arrow Knuth dan aritmetika
  • Untuk semua (k \ge 0, m \ge 0), berlaku hal berikut
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • Di sini (a \uparrow^0 b = ab) didefinisikan demikian
  • Hasil ini dibuktikan dengan induksi terhadap (k)
    • Pada kasus dasar (k=0), diperoleh (g_1(m)=2m+2)
    • Pada langkah induksi, digunakan penerapan berulang ((2 \uparrow^k)^n)
  • Bentuk tertutup ini bergantung pada kebetulan bahwa (2 \uparrow^k 2 = 4) berlaku untuk semua (k)
    • Jika parameternya sedikit berbeda dan bentuknya menjadi ((2 \uparrow^k)^{2m+2}5), tampaknya ekspresi bentuk tertutup akan sulit diperoleh
  • Sebagai korolari, untuk semua (k \ge 0, n \ge 0), berlaku hal berikut
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • Skor akhir langsung diturunkan sebagai berikut
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Hasil permutasi dengan mengubah state awal

  • Jika state awal diubah menjadi B atau C, diperoleh hasil terkait yang lebih kecil
    • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
    • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
  • Skor ketika state awal adalah B adalah sebagai berikut
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • Ketika state awal adalah C, ia berhenti pada langkah 72, dengan skor sebagai berikut
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • Permutasi pertama yang dimulai dari B juga merupakan TM BB(3,4) lain di jajaran atas
  • Jika diubah menjadi TNF, string transisinya menjadi berikut
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

Kesederhanaan tanpa aturan bergaya Collatz

  • Salah satu hal menarik dari TM ini adalah bahwa ia lebih sederhana dari yang diperkirakan
  • Tidak ada aturan mirip Collatz yang berperilaku berbeda berdasarkan sisa nilai
  • Masih terlalu dini untuk mengetahui apakah dominasi TM mirip Collatz sudah berakhir
  • Ada dugaan bahwa TM mirip Collatz setingkat Ackermann mungkin masih ada, tetapi tidak langsung terlihat karena bias seleksi
  • Alasan TM ini ditemukan sebagai TM setingkat Ackermann pertama mungkin karena ia cukup sederhana untuk dibuktikan berhenti tanpa harus mengimplementasikan modular arithmetic di atas fungsi setingkat Ackermann

Inductive Proof Validator

  • TM ini cocok sebagai kasus uji untuk Inductive Proof Validator yang sedang dikembangkan
  • Tujuan proyek ini adalah membuat format sertifikat terstandardisasi untuk “bukti induksi”
  • Di sini, “bukti induksi” digunakan sebagai istilah payung yang merujuk pada inferensi maju dan analisis berbasis aturan secara umum
  • Caranya adalah: siapa pun yang memiliki “inductive decider” dapat menuliskan aturan tersebut dalam format ini, lalu validator dapat memeriksa buktinya
  • Sistemnya masih sangat kasar dan belum siap dipakai secara nyata, tetapi dengan sedikit pekerjaan manual, sistem ini telah digunakan untuk membuktikan perilaku beberapa TM termasuk TM ini

Bacaan terkait

1 komentar

 
GN⁺ 2024-05-25
Komentar Hacker News

  • Mudah untuk mengira program mesin Turing yang berjalan sangat lama pasti sangat rumit atau berupa spaghetti code, tetapi juara baru kali ini nyaris menjadi contoh tandingan
    Hanya ada tiga state, yaitu A, B, dan C; B meneruskan kontrol ke A dan C, tetapi A dan C tidak “mengenal” satu sama lain dan hanya kembali ke B
    Jika ini benar-benar spaghetti code, setiap state seharusnya bisa berpindah ke semua state lain, tetapi yang ini justru semacam konstruksi modular
    Selain itu, program ini tidak pernah menulis sel kosong, dan setiap instruksi selalu mengubah salah satu dari state atau warna, jadi tidak ada “instruksi malas” yang hanya memindahkan posisi seperti B1 -> 1LB

    • Bahkan di dalam proyek bbchallenge sendiri masih ada perdebatan apakah sifat para juara dengan waktu jalan terlama saat ini benar-benar merupakan sifat mesin dengan runtime terpanjang pada ukuran tersebut, atau hanya efek lampu jalan karena sifat itulah yang paling mudah ditemukan dan dibuktikan lewat pencarian otomatis
      Hal ini tidak akan diketahui sampai seluruh ruang pencarian disingkirkan, baik secara deterministik maupun heuristik
      Untuk semua ukuran di atas BB(5, 2), diperkirakan ada mesin yang berjalan selamanya, tetapi dengan sifat yang kacau dan pseudorandom sehingga tidak bisa dibuktikan tanpa kemajuan besar dalam teori bilangan
      Meski begitu, mesin yang berjalan lama tampaknya tidak mungkin sepenuhnya kacau
      Jika ia menumpahkan simbol ke pita secara acak, ia akan segera mencapai konfigurasi berhenti, konfigurasi berulang, atau pola yang disederhanakan
      Namun, tetap mungkin ada mesin yang mensimulasikan sesuatu yang kacau pada tingkat yang lebih tinggi, menghabiskan waktu yang sangat tidak masuk akal di antara tiap langkah tingkat tinggi, lalu akhirnya berhenti
    • Mesin Turing dengan n state dan s simbol hanya dapat bertransisi ke paling banyak n state berbeda
      Jadi jika s=4 atau s=2, hanya mesin Turing yang sangat kecil yang bisa menjadi seperti spaghetti code

  • Pemegang rekor BB(3,4) yang baru adalah sebagai berikut
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    (t', d, s') pada baris s dan kolom t menunjukkan transisi saat simbol di bawah kepala pita adalah t pada state s
    Simbol t ditimpa menjadi t', lalu mesin bergerak ke kiri/kanan sesuai arah d, setelah itu state diubah menjadi s', dan jika s' == Z maka mesin berhenti
    Ini setara dengan 3*4*log2(4*2*log2(4+1)), yaitu sekitar 64 bit informasi
    Sementara itu, BBλ(49) yang hanya 49 bit jauh melampaui bilangan Graham https://oeis.org/A333479

    • Menghitung jumlah mesin Turing yang berbeda bukan hal yang sederhana
      Perhitungan di atas memakai pendekatan paling luas, yaitu menganggap setiap sel dapat memiliki kombinasi (simbol, arah, state) secara sewenang-wenang, sehingga jumlah bit yang dibutuhkan untuk menjelaskan mesin Turing arbitrer menjadi cukup berlebihan
      Dalam kasus BB(3, 4), jika memakai Tree Normal Form, yaitu algoritma Brady(https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html), jumlah mesin Turing yang berbeda hanya sekitar 600 miliar, sehingga hasilnya kurang dari 40 bit
    • Dalam program ini, 1R pada 1RZ tampak seperti nilai yang dipilih secara arbitrer
      Karena mesin berhenti di sana, tidak masalah apa yang tertinggal di pita atau ke mana kepala bergerak
      Sebenarnya, menulis 1 juga tidak penting, tetapi sepertinya 0 tidak akan optimal
      Pada posisi itu sudah tertulis 2, dan meski diubah menjadi 1, jika dihitung berdasarkan jumlah simbol di pita maka 2 juga akan dihitung sama
    • Saya kurang paham dari mana muncul suku log2(4+1)
      Jika menghitung 3*4*log2(4*2*log2(4+1)), hasilnya sekitar 51, dan dari sudut pandang nonspesialis sepertinya mestinya 3*4*log2(4*2*4) = 60
      Mungkin maksudnya 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?

  • Karena penasaran bagaimana cara kerjanya, saya membuat implementasinya di sini: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    Cukup jalankan sebentar untuk melihat apa yang terjadi
    State B mengubah 0 menjadi 2, 1 tetap 1, lalu berpindah ke C; state C mengubah 3 menjadi 2, lalu berpindah ke A
    Jadi untuk memperbaiki 2 -> 1, mesin harus melewati semua 3 satu kali, sehingga rentang beruntun angka 3 berulang kali bertambah secara eksponensial

    • Membuat mesin Turing yang terus tumbuh secara eksponensial selamanya sebenarnya cukup mudah
      Bagian yang benar-benar sulit dipahami adalah mengapa pada akhirnya tetap berhenti setelah jumlah langkah yang tak terbayangkan banyaknya

  • Semua ini terdengar seperti code golf yang sangat ekstrem
    Ke arah lain, mungkin menarik untuk melihat sesuatu bernama BitGrid
    Di BitGrid, setiap sel hanya punya state 4 bit, jadi kisi 4x4 sel tidak mungkin menghitung lebih dari 2^64 apa pun yang terjadi
    Akan menarik untuk mencari tahu sampai sejauh mana ia benar-benar bisa menghitung, dan pada kisi kecil, keterhubungan tepi kemungkinan akan mendominasi hasil
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • Tabel ini sepertinya mungkin penjelasan tentang mesin Turing, jadi akan bagus jika ada materi yang layak dibaca tentang cara menafsirkannya

    • state A, B, C adalah target goto, dan color 0, 1, 2, 3 adalah data selama eksekusi
      Pada setiap state, mesin membaca color saat ini, lalu sesuai color tersebut menjalankan instruksi “warna apa yang akan ditulis, bergerak ke kiri/kanan, dan pindah ke state mana”
      Jika dipindahkan ke C, ini bisa diekspresikan apa adanya dengan switch (SCAN), WRITE, RIGHT/LEFT, dan goto
      Saya penasaran apakah masih ada ruang untuk menulis ulang logika ini dengan gaya yang lebih terstruktur atau melakukan optimasi lain
    • Setiap baris adalah state, dan setiap kolom adalah simbol yang baru saja dibaca dari tape
      Misalnya, baris pertama kolom pertama berarti “simbol 0 dibaca dan state saat ini adalah A”
      Sel pada tabel menunjukkan aksi yang dilakukan; 1RB berarti “ubah simbol pada tape menjadi 1, pindah satu langkah ke kanan, lalu beralih ke state B”
      State Z adalah state berhenti
    • Dalam Python, cukup buat fungsi L() dan R() untuk menggerakkan indeks tape ke kiri/kanan, lalu buat tabel yang memetakan (state, simbol saat ini) ke (simbol yang ditulis, fungsi gerak, state berikutnya), kemudian ulangi selama state != 'Z'
    • Penjelasan singkat ada di https://bbchallenge.org/story#turing-machines
      1RZ bisa dipahami sebagai transisi berhenti karena state Z tidak memiliki aturan
      Di Wikipedia juga ada contoh tabel state mesin Turing yang lebih rinci di https://en.wikipedia.org/wiki/Turing_machine#Formal_definition, dan jejak eksekusi mesin Turing khusus ini bisa dilihat di https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
    • Saya membuat repositori kecil yang mengumpulkan pemegang rekor saat ini dan juga menunjukkan contoh menjalankannya dengan Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      Sepertinya sekarang ini juga perlu diperbarui

  • Hasil penting dalam ilmu komputer dasar dikutip lewat tautan Discord

    • Saya tidak mengerti kenapa itu dianggap tidak boleh
      Gagasan bahwa satu-satunya cara yang sah untuk mengumumkan hasil ilmiah adalah lewat jurnal peer-review itu adalah peninggalan dari 200 tahun lalu, ketika komunitas ilmiah cukup kecil untuk muat dalam bilangan Dunbar
      Itu masih dipertahankan sekarang karena segelintir akademisi dan penerbit kuat mendapat keuntungan darinya, bukan karena ada kelebihan nyata bagi kemajuan ilmu pengetahuan
      Malah, ada kemungkinan itu memikul tanggung jawab yang cukup besar atas krisis reproduksibilitas modern
      Saya sangat mendukung metode ilmiah, tetapi menurut saya peer review tradisional sudah lama melewati masa berlakunya
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • Tetap saja, ini server Discord publik, dan tautan undangannya bisa ditemukan di kanan atas https://bbchallenge.org
      Saya melihat ini lebih sebagai pencantuman sumber daripada kutipan
      Argumen utama yang mendukung hasilnya direproduksi dalam bentuk yang lebih ketat di dalam tulisan blog itu sendiri sehingga berdiri sendiri, dan tautan Discord hanya memberi konteks historis bagi yang tertarik
    • Kalau ikut berpartisipasi dalam obrolan seperti ini, rasanya mirip memunculkan ide di papan tulis ruang istirahat lalu mengembangkannya bersama, hanya saja interaksinya bisa dikutip
      Jika pada saat yang tepat bisa diperkuat dengan literatur, itu perubahan yang positif
    • Saya paham keluhannya, tetapi banyak kemajuan matematika yang mengesankan belakangan ini lahir dari kolaborasi dan iterasi cepat
      Misalnya proyek yang memperbaiki batas atas celah antar prima milik Zhang, dan dalam hal seperti ini alat komunikasi lain mungkin tidak bisa dengan mudah menggantikan Discord
      Kita harus pergi ke tempat orang-orang benar-benar berkumpul
    • Mencari bilangan busy beaver yang lebih besar tidak persis bersifat fundamental, melainkan lebih dekat ke matematika rekreasional
      Jika itu benar-benar fundamental, hasilnya akan melalui peer review sebagai makalah jurnal, bukan diposting di blog

  • Mesin Turing yang bisa dijelaskan dengan jumlah simbol yang tidak terlalu besar seperti 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC jumlah kemungkinannya terbatas
    Namun sungguh menakjubkan bahwa sebagian di antaranya bisa menjalankan langkah sebanyak ini sebelum berhenti

    • Ada 2^60 mesin Turing 3-state 4-simbol seperti ini
      Yang lebih mengejutkan lagi adalah bahwa outputnya, yaitu bentuk normal, adalah suku lambda 49-bit yang melampaui bilangan Graham

  • Sejujurnya saya tidak memahaminya 100% dan mungkin hasil seperti ini juga hampir tidak ada gunanya, tetapi ini lebih menarik bagi saya daripada perkembangan LLM yang luar biasa berguna
    Mungkin karena saya secara alami lebih tertarik pada kebenaran matematis yang sederhana daripada hasil rekayasa yang “kompleks”

  • Bukankah seharusnya BB(5) > BB(3,4)?
    Di https://bbchallenge.org tertulis bahwa mereka sedang mencoba membuktikan atau membantah dugaan bahwa BB(5) sekitar 47 juta, tetapi BB(3,4) tampaknya jauh lebih besar dari itu

    • Benar, tampaknya BB(3, 4) >>> BB(5, 2)
      BB(5) = BB(5, 2), dan BB(3, 4) punya 12 transisi (3*4), sedangkan BB(5, 2) hanya 10, jadi ini tidak terlalu mengejutkan
      Bahkan tampaknya BB(3, 4) >> BB(6, 2) juga
      Karena keduanya punya jumlah transisi yang sama, tampaknya pada mesin Turing kecil seperti ini jumlah simbol yang lebih banyak cukup bernilai