BB(3, 3) Itu Sulit

• Artikel ini membahas mesin Turing 3 status, 3 simbol yang status berhentinya tidak dapat dibuktikan tanpa menyelesaikan masalah mirip Collatz, dan karena itu menyatakan bahwa masalah BB(3,3) sama sulitnya dengan menyelesaikan masalah mirip Collatz tersebut.
• Penulis menyebut keluarga mesin Turing (TM) yang untuk membuktikan apakah ia "quasihalt" memerlukan simulasi yang efisien atau penyelesaian penuh atas masalah mirip Collatz.
• Penulis mengambil contoh dari permainan Busy Beaver umum, dan menemukan banyak TM yang memberikan hasil bagi permainan Busy Beaver.
• Penulis memperkenalkan TM bernama "Bigfoot", yang merupakan salah satu dari 160 kandidat informal BB(3,3) yang masih bertahan.
• Perilaku Bigfoot dijelaskan sebagai pengulangan fungsi mirip Collatz pada b dan c, sementara a mempertahankan jumlah akumulatif.
• Penulis menggunakan teori rantai Markov untuk menjelaskan perilaku Bigfoot, dan menyimpulkan bahwa Bigfoot "probviously" tidak akan pernah berhenti.
• Penulis mengusulkan bahwa kita hidup di salah satu dari dua dunia: dunia tempat Bigfoot berhenti atau dunia tempat ia berjalan selamanya, dan ia percaya kita hidup di dunia kedua.
• Penulis mengusulkan untuk menyebut mesin jenis ini sebagai "Cryptids", yang merupakan analogi dengan makhluk legendaris seperti Loch Ness Monster atau Chupacabra.
• Penulis mengundang ide tentang cara menyerang masalah ini, dan menyatakan harapan bahwa pembuktian BB(3,3) masih mungkin.
• Penulis menutup dengan mengatakan bahwa menurut pengalamannya, pertanyaan yang bisa diajukan tentang masalah mirip Collatz secara relatif hanya ada dua jenis: yang cukup mudah dibuktikan dan yang bahkan matematikawan pun tidak tahu cara membuktikannya.

[GN⁺]

Opini Hacker News

• Diskusi tentang kompleksitas BB(3, 3), yang dikenal sebagai masalah tipe Collatz, tetapi ada argumen bahwa ini belum tentu sulit karena perilakunya bias dan hanya perlu mempertimbangkan satu lintasan.
• Diskusi tentang mesin Turing dengan 748 status, sebuah mesin yang berhenti jika ZFC (teori himpunan Zermelo-Fraenkel dan aksioma pilihan) tidak konsisten. Ada kebingungan tentang implikasi menjalankan mesin ini pada langkah BB(748) dan potensi kontradiksi dengan teorema ketidaklengkapan kedua Gödel.
• Pujian untuk gaya penulisan penulis yang jelas dan ringkas, sehingga membantu pembaca memahami topik tanpa bertele-tele.
• Pertanyaan tentang apa arti BB (Busy Beaver) tidak dapat dihitung, dan apakah ketika BB bertumbuh kita harus membuktikan semuanya.
• Saran bahwa semua masalah BB(x, y) dapat direduksi menjadi masalah seperti Collatz, dan karena itu menemukan BB(x, y) untuk nilai x dan y tertentu juga dapat direduksi menjadi masalah seperti Collatz.
• Pertanyaan mengapa Beeping Busy Beavers (BBB) bisa quasi-halt jauh lebih awal sebelum berjalan jauh lebih lama, dengan saran bahwa ini mungkin karena tidak perlu menggunakan status berhenti.
• Pertanyaan tentang dampak halting problem terhadap induksi di dunia nyata, dengan skenario hipotetis yang mencakup oracle yang dapat menentukan apakah mesin Turing tertentu akan mencetak sesuatu yang berbeda pada pita keluarannya.
• Pertanyaan tentang pengetahuan prasyarat yang diperlukan untuk memahami topik-topik ini, serta permintaan topik atau mata pelajaran tertentu yang dapat memberikan dasar yang baik.
• Pertanyaan tentang cara membaca string tertentu, 1RB2RA1LC_2LC1RB2RB_---2LA1LA.