BusyBeaver(6) Benar-Benar Sangat Besar

• Bilangan Busy Beaver keenam (BB(6)) baru-baru ini mengalami kenaikan batas bawah yang sangat besar berkat riset baru
• Sebelumnya diketahui bahwa BB(6) > 10↑36,534, lalu pada 2022 dinaikkan menjadi BB(6) > 10↑1510
• Baru-baru ini di BBchallenge, nilainya kembali dinaikkan menjadi BB(6) > 10↑10,000,00010, lalu diperbarui lagi hingga 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
• Ukuran BB(6) melampaui imajinasi, dan bilangan ini berada pada skala yang dapat memenuhi seluruh alam semesta berkali-kali
• Perkembangan ini menjadi momentum untuk kembali menyadari batas dan potensi logika matematika dan teori komputasi

---

Ringkasan capaian riset terbaru BB(6)

• Dalam beberapa tahun terakhir, situasi dunia dan lingkungan riset terus terasa berat
• Namun, kemajuan dalam riset Busy Beaver kali ini menjadi pengingat akan gairah murni terhadap penelitian
• Pada 2022, Pavel Kropitz membuktikan bahwa BB(6) > 10↑1510
  • BB(6) berarti berapa kali maksimum mesin Turing dengan 6 state dapat beroperasi di atas pita semua-nol sebelum berhenti
  • Di sini ^1510 adalah nilai tetrasi, yakni 10 dipangkatkan berulang terhadap dirinya sendiri sebanyak 15 tingkat
• Dalam riset sebelumnya, terungkap bahwa BB(5) adalah 47,176,870 (tim BBchallenge), dan ini adalah titik ketika nilainya mulai melonjak ke wilayah yang melampaui cakupan realitas yang dapat diamati

Proses pembaruan batas bawah terbaru

• "mxdys" dari BBchallenge membuktikan bahwa BB(6) > 10↑10,000,00010
  • Bukti ini didasarkan pada bukti formal yang ditulis dalam bahasa Coq
• Setelah itu, batas bawah kembali diperbarui menjadi BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
  • ↑↑ berarti tetrasi, yaitu bentuk pengulangan pangkat, dalam hal ini 2 ditetrasikan dengan 2, lalu hasilnya digunakan lagi untuk tetrasi, dan proses itu berulang hingga 9 tingkat
  • Bilangan sebesar ini berada di wilayah yang melampaui pemahaman intuitif apa pun yang ada sebelumnya
• Sebagai referensi, pentasi berarti pengulangan tetrasi, yaitu operasi yang melampaui perkalian, perpangkatan, dan tetrasi

Memahami besarnya bilangan raksasa

• Atas permintaan reporter, perlu dijelaskan seberapa besar bilangan 10↑10,000,00010 itu
• Jumlah ini cukup untuk mengisi 10↑10,000,00010 alam semesta dengan pasir
• Dengan demikian, tersampaikan bahwa nilai BB(6) jauh melampaui dunia nyata yang dapat kita amati

Renungan tentang batas hakiki algoritme BB

• Besarnya nilai BB(6) menunjukkan potensi sesungguhnya dari fungsi Busy Beaver
• Titik ketika nilai BB(n) menjadi independen dari sistem aksioma teori himpunan (ZFC) diperkirakan berada di sekitar n=20~30, tetapi kini muncul dugaan bahwa mungkin pada n=7~9 pun nilainya sudah bisa independen
  • Saat ini, secara resmi diketahui bahwa pada n=643 nilainya independen

Lampiran: kabar acara dan kuliah terbaru

• Penulis baru-baru ini menghadiri acara STOC'2025 di Praha, berinteraksi dengan berbagai peneliti, dan memperoleh informasi baru
• Ia juga membagikan slide kuliah utama tentang status percepatan kuantum miliknya
• Ulasan yang lebih rinci tentang hal ini akan dibagikan kemudian

[GN⁺]

Komentar Hacker News

• Di server Discord bbchallenge, ada yang membagikan tebakan tentang berapa banyak state mesin Turing yang dibutuhkan untuk melampaui Graham's Number. Angka 2^^2^^2^^9 yang baru-baru ini dicapai pemenang BB(6) saja sudah luar biasa besar, tetapi tetap mengejutkan bahwa pola pertumbuhan sekelas Graham bisa muncul lebih cepat dari dugaan. Disebutkan juga materi functional busy beaver [1] yang menyatakan bahwa term lambda 49-bit saja sudah cukup, fakta bahwa hanya ada 77519927606 closed lambda term berukuran itu[2], sementara ada sebanyak 399910780272640 mesin Turing 6-state[3]. Setelah pentation berhasil diimplementasikan hanya dengan 6 state, sekarang tampaknya cukup banyak orang yang percaya bahwa dengan 7 state pun Graham's Number bisa dilampaui. Meski begitu, penulis tetap merasa itu mengejutkan. Ia juga bercerita bahwa beberapa hari lalu ia membuat taruhan besar soal apakah dalam 10 tahun ke depan akan muncul bukti bahwa BB(7) melampaui Graham's Number, lalu menanyakan pendapat orang lain. (1, 2, 3 tautan disediakan)
  • Saya tidak mau berpura-pura sebagai ahli, tetapi saya memperkirakan BB(7) akan lebih besar daripada Graham's Number. BB harus tumbuh lebih cepat daripada sembarang barisan bilangan yang dapat dihitung, jadi meskipun kita hanya bisa meraba-raba seberapa besar BB(7) yang sebenarnya, arahnya tetap harus melampaui semua operator yang dapat dihitung seperti up-arrow^n dan sejenisnya. Lompatan dari 47176870 ke 2^^2^^2^^9 terasa jauh lebih dramatis dari sisi kekuatan operator daripada lompatan dari 2^^2^^2^^9 ke Graham's Number. Karena Graham's Number adalah g_64, yang juga bisa dipahami sebagai konsep satu tingkat di atas up-arrow^n, saya punya firasat bahwa BB(7) akan melampaui Graham's Number.
• Sangat menakjubkan bahwa bilangan tak-terhitung seperti BB(748) bisa independen dari ZFC (sistem aksioma teori himpunan). Rasanya seperti semacam category error.
  • Alasan BB(748) independen dari ZFC bukan pada nilainya sendiri, melainkan karena salah satu dari 748 state tersebut, yaitu TM_ZFC_INC, berhenti hanya jika ia menemukan kontradiksi dalam ZFC (pembuktian hal yang salah). Untuk membuktikan BB(748)=N, kita harus menunjukkan bahwa TM_ZFC_INC berhenti dalam N langkah atau terus berjalan tanpa henti; tetapi menurut teorema ketidaklengkapan Gödel, bila ZFC konsisten, implikasi semacam itu tidak dapat dibuktikan.
  • Yang lebih mengejutkan adalah bahwa sejumlah kecil baris teks, yaitu aksioma ZFC itu sendiri, bisa cukup untuk mengekspresikan kebenaran aritmetika yang penting bagi manusia. Fakta bahwa kita bahkan tidak bisa dengan mudah memprediksi perilaku mesin Turing 6-state justru terasa wajar. Setelah teorema ketidaklengkapan Gödel diumumkan, mestinya dunia matematika bergerak jauh lebih aktif untuk mencari aksioma tambahan, tetapi kenyataannya hal itu hanya dibahas di sebagian riset dasar.
  • Nilai kebenaran hipotesis kontinum, yang secara platonis adalah 1 atau 0, terbukti independen dari ZFC. Ini contoh yang baik: bahkan bukan bilangan raksasa, hanya 1 bit sederhana pun tidak dijamin oleh ZFC.
  • Penting dibedakan bahwa BB(n) bersifat tak-terhitung, sedangkan BB(748), yang menurut definisi adalah banyaknya angka 1 yang ditulis mesin Turing 748-state, adalah bilangan yang dapat dihitung. Label "independen" berarti bahwa untuk membuktikan bahwa bilangan ini benar-benar bernilai seperti yang kita inginkan, dibutuhkan teori yang lebih kuat daripada ZFC.
  • Yang independen dari ZFC bukan bilangan itu sendiri, melainkan proses menghitung BB(748). (Semua bilangan bulat bisa diekspresikan dalam ZFC.)
• Sudah dikenal luas bahwa BB(14) lebih besar daripada Graham's Number, dan riset kali ini membuat saya merasa bahwa BB(7) juga kemungkinan setidaknya sebesar Graham's Number. Secara intuitif, ide dari pentation ke Graham's Number terasa malah lebih sederhana daripada mencapai 47,176,870 ke 2 <pentate> 5.
  • Informasi yang bagus, ini sepertinya bisa menjadi jawaban yang sangat baik untuk tulisan saya.
• Dibagikan tautan ke kuliah YouTube Scott Aaronson, “How Much Math Is Knowable?” [Harward CMSA] https://www.youtube.com/watch?v=VplMHWSZf5c, serta thread HN terbaru https://news.ycombinator.com/item?id=43776477
• Dijelaskan bahwa "superskrip kiri atas" adalah tetration, yaitu eksponensiasi berulang. Jadi ¹⁵10 berarti 10 pangkat 10 pangkat ... sebanyak 15 kali. Katanya ini konsep baru baginya, sampai sempat mengira itu hanya salah ketik.
  • Melanjutkan tema operasi berulang, kali ini ada yang menanggapi bahwa ia baru pertama kali menemui "pentation".
  • Saya pernah melihat tetration sebelumnya, tetapi saya lebih suka notasi up-arrow Knuth[1] karena lebih umum dipakai dan lebih enak untuk digeneralisasi (1)
• Penjelasan bahwa BB(6) adalah jumlah langkah maksimum sebelum mesin Turing 6-state 2-simbol ({0,1}) berhenti dari tape awal berisi 0 sangat membantu bagi orang non-ahli. Ini terasa seperti bidang yang dipenuhi kepadatan tinggi dan istilah khusus untuk peneliti puluhan tahun, jadi menarik bisa kebetulan menemukan tulisan sedalam ini.
  • Menurut saya, mahasiswa S1 ilmu komputer pun bisa menangkap idenya meskipun baru pertama kali melihat masalah busy beaver. Memang banyak istilah khusus, tetapi tidak perlu merasa bahwa ini hanya untuk orang dengan pengalaman puluhan tahun.
  • Definisi itu memang standar lebih di ranah teori ilmu komputer daripada software engineering.
• Saya bingung dengan penjelasan bahwa jika ada "10,000,000 sub10" butir pasir, maka itu bisa mengisi alam semesta teramati sebanyak 10,000,000 sub10 kali. Biasanya orang membandingkannya dengan massa alam semesta teramati, dan dengan cara ini ukurannya tampak sudah jauh melebihi jumlah materi yang benar-benar ada.
  • Benar. Bahkan jika dibagi dengan rasio butir pasir/alam semesta pun, angkanya tetap hampir berada pada kelas kebesaran yang sama, sementara bilangan yang berdekatan dalam notasi ini berbeda luar biasa jauh. 10↑↑10,000,000 / (butir pasir/alam semesta) pun masih jauh lebih besar daripada 10↑↑9,999,999. Dalam sistem kita, (sangat besar) / (besar secara kosmik) tetap saja disederhanakan menjadi (sangat besar).
  • Dalam tetration, kita tidak lagi membandingkan jumlah digit biasa, melainkan pertumbuhan setingkat "jumlah digit dari jumlah digit".
  • Bilangan ini bahkan tidak akan berkurang secara berarti sekalipun dibagi sekitar 10^100000 butir pasir, jadi pembagian semacam itu pada dasarnya tidak berpengaruh.
  • Bahkan 10,000,000^10,000,000 saja sudah absurd besarnya, jadi kalau ekor eksponennya ditambah sekali lagi, perbandingan itu sendiri jadi nyaris tak bermakna.
  • Contoh yang lebih umum: dalam konsep angka penting, mengatakan 1 miliar - 1 juta = 1 miliar bukanlah lompatan yang berlebihan.
• Saya penasaran, sistem logika paling "kaya" apa yang pembuktiannya bisa dienumerasi oleh mesin Turing 5-state?
  • Jawabannya bisa berbeda tergantung bagaimana Anda mendefinisikan "enumerasi". Pertanyaan terkait lain yang juga bermakna adalah: "Apa sistem logika terkuat yang tetap tidak bisa membuktikan status berhenti semua mesin Turing 5-state?" Karena sangat sulit membuktikan secara matematis bahwa Skelet #17 [0] tidak berhenti, saya pribadi merasa bahwa jika ada teori yang bisa membuktikan itu, mungkin semua mesin Turing 5-state lainnya juga bisa diputuskan (0, 1)
  • Kita harus lebih dulu memperjelas bagaimana string biner hingga ditafsirkan sebagai enumerasi pembuktian logis sebelum membahas premis itu.
• Ada yang bertanya-tanya apakah alam semesta teramati cukup besar untuk menuliskan nilai tepat BB(6).
  • Jika alam semesta teramati dipandang sebagai sistem tertutup, maka dengan menerapkan Bekenstein bound, batas penyimpanan informasinya sekitar 10^120 bit. Estimasi saat ini menempatkan total massa-energi sekitar 10^53kg, dan jika dimasukkan ke rumus, hasilnya tetap berada di kisaran 10^120 bit. Jadi itu tidak mungkin, dan ada dasar angka yang jelas untuk menyatakannya.
  • Jumlah informasi yang dapat disimpan di alam semesta sekitar 10^120 bit, dan bahkan jika perkiraan itu salah beberapa orde besaran pun, tetap saja "jelas tidak cukup".
  • Dugaan saya pertanyaannya mengasumsikan seluruh nilai harus disimpan sekaligus. Jika syarat keserempakan itu dihapus, mungkin secara teoretis pencatatan sepanjang waktu tak hingga bisa dilakukan, tetapi tetap ada batas realistis seperti kematian termal alam semesta. Dalam kerangka acuan CMB hal itu tak mungkin, tetapi mungkin menarik untuk memikirkan pemotongan ruang-waktu yang berbeda.
  • Bahkan angka pertama dalam artikel itu sendiri sudah berupa ¹⁵10, yaitu bentuk 10^(¹⁴10), sehingga jumlah digitnya saja adalah ¹⁴10. Dengan itu saja sudah jelas mustahil.
  • Ya, tidak mungkin.
• Setiap kali melihat hasil seperti ini dalam teori kompleksitas komputasi, saya makin merasa bahwa wacana populer semacam "superintelligence adalah tuhan" benar-benar tidak berdasar. Bahkan jika semua atom di alam semesta dijadikan superkomputer dan energi black hole ikut dipakai, menghitung status berhenti BB(6) akan tetap mustahil selamanya.
  • Strawman seperti itu memang sejak awal tidak pernah terlalu meyakinkan.