BusyBeaver(6) Benar-Benar Sangat Besar

• Batas bawah yang diketahui untuk BB(6) kembali naik drastis, mengonfirmasi bahwa waktu henti maksimum mesin Turing 6-state jauh melampaui skala realitas yang dapat diamati
• BB(6) berarti jumlah langkah maksimum yang dapat dijalankan mesin Turing 6-state·2-simbol yang mulai dari pita terisi 0 sebelum berhenti
• Setelah peningkatan oleh Pavel Kropitz pada 2022, mxdys kembali mendorong batas bawah ke tingkat lebih besar daripada 10 yang ditetrasikan 10 juta kali
• Hasil terbaru menunjukkan BB(6) setidaknya 2 dipentasi ke 5, sehingga muncul operasi satu tingkat lebih tinggi daripada tetrasi berulang
• BB(5) telah ditetapkan sebagai 47,176,870, tetapi BB(6) menjadi sangat besar, memunculkan perkiraan bahwa titik ketika BB(n) independen dari aksioma ZFC bisa berada pada n=7, 8, atau 9

---

Batas bawah BB(6) kembali membesar

• Sebelum 2022, yang diketahui tentang BB(6) hanya sekitar BB(6) > 10^36,534, lalu Pavel Kropitz memperbaikinya menjadi lebih besar daripada 10 yang ditetrasikan 15 kali
• Tetrasi (tetration) berarti perpangkatan berulang
  • Misalnya, bilangan 10 yang ditumpuk 15 kali adalah bentuk 10 pangkat 10 pangkat 10 pangkat … yang berlanjut 15 kali
• Penyelenggara BBchallenge Tristan Sterin mengabarkan bahwa anggota tim mxdys kembali menaikkan batas bawah BB(6)
  • Peningkatan pertama: BB(6) > 10 yang ditetrasikan 10 juta kali
  • Hasil ini disertai bukti ketepatan Coq
• Peningkatan berikutnya oleh mxdys menunjukkan bahwa BB(6) setidaknya 2 ditetrasikan ke 2 ditetrasikan ke 2 ditetrasikan ke 9
  • Secara khusus, BB(6) setidaknya 2 dipentasi ke 5
  • Pentasi (pentation) adalah tetrasi berulang, operasi satu tingkat lebih tinggi daripada sekadar mengulang perpangkatan

Perbedaan ekstrem antara BB(5) dan BB(6)

• BB(6) adalah bilangan Busy Beaver ke-6
  • Ditujukan pada mesin Turing 6-state
  • Alfabetnya adalah {0,1}
  • Pita masukan pada awalnya seluruhnya 0
  • Ini berarti jumlah langkah eksekusi maksimum yang mungkin sebelum berhenti
• Tim internasional BBchallenge tahun lalu menetapkan BB(5) sebagai 47,176,870
• Saat beralih dari BB(5) ke BB(6), fungsi Busy Beaver melonjak dari puluhan juta ke ukuran yang melampaui cakupan realitas yang dapat diamati

Bilangan yang nyaris tak bisa dipahami skalanya

• Bahkan ketika BB(6) > 10 yang ditetrasikan 10 juta kali, penjelasan intuitifnya hampir mustahil
• Sebagai analogi, jika ada butiran pasir sebanyak itu, maka salinan alam semesta teramati bisa diisi sekitar sebanyak jumlah yang sama
• Analogi ini menunjukkan bahwa bilangan tersebut jauh lebih besar daripada bilangan berskala kosmik seperti 10^100, sehingga bahkan setelah dibagi pun skalanya nyaris tetap seperti semula

Kemungkinan turunnya perkiraan independensi ZFC

• Fakta bahwa BB(6) menjadi sebesar ini tidak berarti semua pemikiran tentang fungsi Busy Beaver berubah total
• Kemungkinan bahwa BB(6) bukan berada di level yang relatif kecil seperti 10^36,534, melainkan di wilayah operasi berulang, sejak awal memang terbuka
• Karena batas bawah aktualnya kini terkonfirmasi pada skala seperti itu, perkiraan tentang titik ketika nilai BB(n) menjadi independen dari sistem aksioma teori himpunan ZFC bisa turun
  • Sebelumnya orang bisa membayangkan n=20 atau 30-an
  • Kini mungkin saja n=7, 8, atau 9
• Hasil independensi ZFC yang saat ini diketahui berada pada tingkat bahwa BB(n) menjadi independen dari ZFC pada n=643

Pembaruan terpisah: STOC 2025

• Di Prague, tempat STOC 2025 digelar, penulis bertemu banyak peneliti dan menemukan hal-hal baru
• Judul kuliah pleno STOC adalah The Status of Quantum Speedups
• Pembaca yang tertarik dapat melihat slide PowerPoint untuk kuliah tersebut

[GN⁺]

Komentar Hacker News

• Di server Discord bbchallenge, orang-orang sedang aktif berspekulasi berapa banyak state mesin Turing yang diperlukan untuk melampaui Graham's Number, yang jauh lebih besar daripada 2^^2^^2^^9 yang dicapai oleh juara BB(6) terbaru
  Kalau melihat functional busy beaver https://oeis.org/A333479, perilaku setingkat Graham bisa muncul lebih cepat dari dugaan. Term lambda 49-bit saja sudah cukup
  Term lambda tertutup di bawah ukuran itu hanya ada 77.519.927.606 buah https://oeis.org/A114852, sedangkan mesin Turing 6-state yang unik ada 4^12*23836540=399910780272640 buah https://oeis.org/A107668
  Karena pentation sudah dicapai hanya dengan 6 state, sekarang ada beberapa orang yang berpendapat bahwa 7 state cukup untuk melampaui Graham's Number. Meski begitu, menurut saya itu tetap cukup mengejutkan. Beberapa hari lalu saya bertaruh besar dengan salah satu dari mereka soal apakah dalam 10 tahun ke depan akan ada bukti BB(7)>Graham's, dan saya penasaran bagaimana pendapat kalian

  • Saya tidak bisa berpura-pura sebagai pakar, tetapi BB(7) mungkin lebih besar daripada Graham's Number
    BB harus tumbuh lebih cepat daripada deret apa pun yang dapat dihitung. Apa arti konkretnya untuk BB(7) pada akhirnya lebih seperti penjelasan dengan lambaian tangan, tetapi rasanya ia harus menaiki tangga kekuatan operator dengan sangat cepat. Pada akhirnya ia harus tumbuh lebih cepat daripada operator apa pun yang dapat dihitung yang kita definisikan, termasuk misalnya up-arrow^n atau up-arrow^f(n) untuk fungsi yang dapat dihitung f
    Secara intuitif, pertumbuhan dari 47 million ke 2^^2^^2^^9 terasa secara kualitatif lebih besar dalam hal kekuatan operator yang diperlukan dibanding pertumbuhan dari 2^^2^^2^^9 ke Graham's Number. Graham's Number adalah g_64, dan di sini g kira-kira satu tingkat di atas up_arrow^n, jadi mungkin besar kemungkinan BB(7)>Graham's Number

• Rasanya bikin pusing bahwa bilangan seperti BB(748), apalagi bilangan yang tidak dapat dihitung, bisa “independen dari ZFC”. Rasanya seperti kesalahan kategori

  • Yang membuat BB(748) independen dari ZFC bukan nilainya itu sendiri, melainkan karena salah satu mesin 748-state, TM_ZFC_INC, dirancang untuk mencari kontradiksi di dalam ZFC, yaitu bukti atas FALSE, dan berhenti hanya ketika menemukannya
    Jadi bukti bahwa BB(748)=N harus menunjukkan bahwa TM_ZF_INC berhenti dalam N langkah, atau menunjukkan bahwa ia tidak akan pernah berhenti. Jika mengasumsikan ZFC konsisten, karena hasil terkenal Gödel, keduanya mustahil
  • Yang tidak dapat dihitung adalah BB(n). Artinya tidak ada algoritme yang, untuk sembarang n, mengeluarkan nilai BB(n)
BB(748) dapat dihitung. Menurut definisi, itu adalah jumlah angka 1 yang ditulis oleh suatu mesin Turing dengan 748 state, dan mesin itulah yang menghitung BB(748)
    Bilangan itu sendiri secara harfiah hanyalah bilangan bulat yang besarnya tak terbayangkan. Independensi ZFC muncul ketika kita mencoba membuktikan bahwa bilangan ini adalah bilangan yang kita cari. Untuk itu diperlukan teori yang lebih kuat daripada ZFC, yang mampu menangkap sifat mesin Turing 748-state
  • Justru lebih mengejutkan bahwa orang mengira teks pendek seperti aksioma ZFC, yang cukup muat dengan longgar di atas serbet, akan “cukup” untuk menangkap kebenaran aritmetika atau aspek realitas fisik yang terutama terkait dengan aktivitas manusia
    Sama sekali tidak mengejutkan bahwa perilaku mesin Turing 6-state bisa tidak dapat diprediksi oleh teks beberapa baris
    Saya mengira begitu Gödel mengumumkan teorema ketaklengkapan pertamanya, seluruh dunia matematika akan berlari sekuat tenaga mencari lebih banyak aksioma. Namun selama hampir satu abad, karya Gödel cenderung diperlakukan sebagai fakta aneh yang berada di ranah sempit fondasi, bukan sebagai program arus utama. Saya tahu Feferman, Friedman, dan lainnya, tetapi penelitian di bidang ini jauh lebih sedikit dibanding kebanyakan topik lain dalam matematika
  • Bukan bilangannya sendiri yang independen dari ZFC. Semua bilangan bulat dapat direpresentasikan dalam ZFC. Yang independen dari ZFC adalah proses menghitung BB(748)
  • Angka individual itu sendiri tidaklah tidak dapat dihitung. Tidak ada pasangan berupa suatu angka dan bukti di dalam ZFC yang membuktikan bahwa angka itu adalah nilai BB(748)
    Karena itu, tidak ada program yang dapat dibuktikan oleh ZFC akan mengeluarkan nilai BB(748). Namun seperti semua bilangan lainnya, program yang mengeluarkan BB(748) itu sendiri tetap ada

• Diketahui bahwa BB(14) lebih besar daripada Graham's Number, tetapi melihat hasil kali ini, sepertinya BB(7) juga mungkin lebih besar daripada Graham's Number
  Secara intuitif, teknik yang diperlukan untuk beralih dari pentation ke Graham's Number terasa lebih sederhana daripada teknik yang diperlukan untuk beralih dari 47,176,870 ke 2 5

• Saat membaca penjelasan bahwa superskrip kiri berarti tetration, yaitu perpangkatan berulang, awalnya saya kira itu salah ketik. Ini pertama kalinya saya mengenal tetration

  • Saya pernah melihatnya sebelumnya, tetapi waktu itu memakai notasi panah atas Knuth, yang saya suka karena mudah digeneralisasi https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
  • Mengikuti alur pengulangan itu, kali ini saya pertama kali mengenal pentation

• Saya tidak paham bagian yang berbunyi, “Bayangkan ada 10,000,000sub10 butir pasir. Maka Anda bisa mengisi kira-kira 10,000,000sub10 alam semesta teramati dengan pasir itu”
  Apakah benar-benar nilai volume alam semesta teramati dibagi volume rata-rata butir pasir lalu dibulatkan sampai hilang? Itu selisih jumlah digit yang jauh lebih besar daripada total massa alam semesta yang biasanya dipakai untuk perbandingan

  • Benar. Pembagian dengan rasio itu pada dasarnya hampir tidak berpengaruh, karena dalam notasi ini angka-angka yang “bersebelahan” menghasilkan perubahan yang jauh lebih besar
    10↑↑10,000,000 / (jumlah butir pasir per satu alam semesta) masih jauh lebih besar daripada, misalnya, 10↑↑9,999,999
    Dalam sistem yang memakai angka seperti ini, hampir tidak ada cara yang lebih baik untuk menyatakan (angka yang sangat besar)/(angka yang hanya berskala kosmis) selain menuliskannya persis begitu, dan dalam notasi untuk angka yang sangat besar pada akhirnya ia hampir dibulatkan menjadi (angka yang sangat besar)
  • Dalam tetrasi, kita tidak lagi berurusan dengan skala jumlah digit, melainkan skala jumlah digit dari skala jumlah digit
  • Contoh yang lebih umum untuk perbandingan semacam ini: dilihat dari angka penting, 1 miliar dikurangi 1 juta tetap 1 miliar
  • Tepat. Angka ini begitu jauh lebih besar daripada besaran seperti 10^100000 atau berapa banyak butir pasir yang muat, sehingga dibagi sebesar itu pun pada dasarnya tidak berubah. Setidaknya tidak turun sampai mendekati 9,999,999sub10
  • Benar. Itu hanya selisih jumlah digit sebesar angka biasa. 10,000,000^10,000,000 saja sudah cukup besar sehingga hal semacam itu tidak penting, apalagi setelah eksponennya sendiri dipangkatkan lagi sembilan kali

• How Much Math Is Knowable? dari Scott Aaronson [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
  Ini juga sempat naik di HN beberapa bulan lalu: https://news.ycombinator.com/item?id=43776477

• Logika terkaya apa yang bisa menghitung daftar bukti hanya dengan mesin Turing 5-keadaan?

  • Pertanyaan itu bergantung pada apa yang dianggap sebagai enumerasi, tetapi ada pertanyaan terkait: “Apa logika terkaya yang tidak mampu membuktikan apakah semua mesin Turing 5-keadaan berhenti atau tidak?” Dengan kata lain, menanyakan logika terkaya yang untuknya status berhenti dari suatu mesin Turing 5-keadaan bersifat independen
    Saya pernah memikirkan versi ini, tetapi tidak melangkah jauh karena kurang memiliki keahlian dalam logika orde pertama. Sejauh yang saya tahu, Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA adalah salah satu mesin yang secara matematis paling sulit dibuktikan tidak berhenti https://arxiv.org/abs/2407.02426, jadi jika ada teori yang dapat membuktikan bahwa Skelet #17 tidak berhenti, kemungkinan besar teori itu juga bisa memutuskan mesin-mesin 5-keadaan lainnya
  • Itu sepenuhnya bergantung pada bagaimana string biner berhingga ditafsirkan sebagai enumerasi bukti logis

• Setelah membaca penjelasan bahwa “BB(6) adalah bilangan Busy Beaver keenam, yaitu jumlah langkah maksimum yang dapat diambil sebelum berhenti oleh mesin Turing 6-keadaan dengan alfabet {0,1} ketika dijalankan pada pita yang awalnya seluruhnya 0,” sebagai orang non-ahli saya justru merasa itu terlalu mudah dipahami
  Ini jelas blog hardcore untuk orang-orang yang telah meneliti hal semacam ini selama puluhan tahun. Cukup keren rasanya menemukan tulisan yang tanpa ragu ditulis padat dan penuh istilah teknis untuk pembaca tertentu

  • Bagi orang yang pernah mendapat pendidikan ilmu komputer tingkat sarjana, penjelasan itu cukup untuk kira-kira menangkap apa yang sedang dibahas meski baru pertama kali menjumpai masalah Busy Beaver
    Memang itu jargon ceruk, tetapi menganggapnya hanya dapat diakses oleh orang yang telah mencurahkan puluhan tahun berarti meremehkan diri sendiri
  • Definisi itu adalah materi standar teori ilmu komputer tingkat sarjana. Namun mungkin bukan standar dalam rekayasa perangkat lunak

• Angka sebesar itu tidak bisa divisualisasikan manusia. Cara merepresentasikan angka bukan hanya dengan menghitung satu per satu
  Misalnya, satu butir pasir pun bisa dianggap memiliki tak hingga banyak keadaan yang mungkin. Karena ada tak hingga banyak bilangan real, bisa juga dikatakan satu butir pasir dapat merepresentasikan BB(6). Kombinasi bisa tumbuh secara eksponensial, jadi cara seperti itu mungkin berguna untuk representasi

  • Pada titik tertentu, bilangan besar jauh lebih dekat ke kekuatan konsistensi suatu sistem formal daripada sekadar “kuantitas besar”
    Artinya, seberapa lama suatu sistem bisa berpura-pura tidak kontradiktif sebelum ketahuan. Sistem kontradiktif yang berpura-pura konsisten melalui BB(3) akan “ketahuan” jauh lebih cepat daripada sistem yang berpura-pura konsisten melalui BB(6). Yang dimaksud berpura-pura konsisten di sini adalah mengklaim bahwa semua program yang berjalan lebih lama daripada BB(n) langkah untuk suatu n tidak akan berhenti
  • Jika alam semesta dibulatkan ke satuan Planck terdekat, jumlah keadaan yang bisa dimiliki satu butir pasir tiba-tiba tidak lagi begitu banyak
    Membawa presisi tak hingga agar terlihat mudah ditangani, menurut saya, lebih mirip sulap tangan. Untuk menjelaskan skala, lebih baik memakai bilangan bulat
  • Contoh ini membingungkan. Jika jumlah butir pasir sama dengan jumlah alam semesta teramati, bukankah itu berarti satu butir pasir per satu alam semesta?

• Saya penasaran apakah alam semesta teramati cukup besar untuk menuliskan nilai persis BB(6)

  • Jika alam semesta teramati dianggap sebagai sistem tertutup, kita bisa mencoba menerapkan batas Bekenstein
    Menggunakan R ≈ 46.5 billion light-years, yaitu radius alam semesta teramati, dan E ≈ total kandungan massa-energi alam semesta teramati
    Massa-energi mencakup materi biasa, materi gelap, dan energi gelap. Dengan estimasi saat ini, alam semesta teramati memiliki ekuivalen massa-energi sekitar 10^53 kg
    Jika dimasukkan ke S ≤ 2πER/ℏc, jumlah informasi maksimum kira-kira berada di kisaran 10^120 bits
S ≤ 2πER/ℏc
S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
S ≤ 2.654135e+124
S ≤ 10^120
    Jadi tidak mungkin
  • Jelas tidak cukup. Jumlah informasi yang bisa disimpan di alam semesta kira-kira sekitar 10^120 bit. Bahkan andaikan saya meleset sebanyak 1 triliun digit pun, hasilnya tidak akan berubah
  • Di tulisan itu, angka awalnya saja sudah ¹⁵10. Ini berarti 10^(¹⁴10), sehingga jumlah digitnya adalah ¹⁴10. Jadi tidak bisa dituliskan
  • Mungkin maksudnya adalah keadaan di mana semua bagian dari representasi lengkap ada secara bersamaan. Jika tidak perlu ada secara bersamaan, maka bila durasi alam semesta tak terbatas, mungkin saja “menuliskannya” bisa dilakukan. Saya tidak tahu bagaimana kematian panas berperan di sini, jadi hanya “mungkin saja”
    Namun dalam ruang-waktu relativistik, kata “bersamaan” tidak terdefinisi dengan baik. Komentar-komentar saudara jelas benar dalam kerangka acuan yang diimplikasikan oleh radiasi latar belakang gelombang mikro kosmik. Namun saya bertanya-tanya apakah dalam suatu kerangka acuan tertentu, mungkin ada cara mengiris ruang-waktu sehingga representasi itu bisa ada “secara bersamaan”