- Mesin Turing 3-state 3-simbol Bigfoot adalah contoh yang mengharuskan kita memecahkan masalah mirip Collatz untuk membuktikan apakah ia berhenti pada tape kosong, menunjukkan bahwa (BB(3, 3)) juga bisa sesulit itu
- Mesin ini adalah salah satu dari 160 kandidat (BB(3, 3)) yang belum terselesaikan di bbchallenge.org, dan didefinisikan dengan tabel transisi
1RB2RA1LC_2LC1RB2RB_---2LA1LA - Perilakunya direduksi menjadi aturan iterasi konfigurasi (A(a,b,c)); bergantung pada (b \bmod 6), a bertambah atau berkurang, dan mesin hanya berhenti ketika (a) hendak turun di bawah 0
- Dari tape kosong, setelah 69 langkah ia mencapai (A(2,1,2)), lalu setelah 24 juta iterasi (a) membesar hingga (3.999.888), sehingga secara eksperimen kemungkinan berhentinya tampak sangat rendah
- Deret (b \bmod 6) bersifat deterministik, tetapi dalam gambaran besar terlihat seperti random walk bias dengan peluang 2/3 ke kanan dan 1/3 ke kiri; untuk membuktikan ia berjalan selamanya, perlu ditunjukkan bahwa fungsi mirip Collatz ini tidak mencapai transisi berhenti
Mengapa Bigfoot membuat (BB(3, 3)) sulit
- Untuk membuktikan apakah berhenti satu mesin Turing 3-state 3-simbol, kita harus menyelesaikan masalah mirip Collatz
- Karena itu, menyelesaikan masalah (BB(3, 3)) bisa jadi sama sulitnya dengan menyelesaikan masalah mirip Collatz ini
- Paul Erdős pernah berkata tentang masalah-masalah sejenis Collatz: “Mathematics may not be ready for such problems”
- Tulisan sebelumnya Mother of Giants membahas keluarga mesin Turing yang ditemukan dalam pencarian Busy Beaver “Beeping”
- Untuk membuktikan apakah keluarga tersebut berada dalam keadaan mirip berhenti (quasihalt), kita harus mensimulasikan masalah mirip Collatz secara efisien atau menyelesaikannya sepenuhnya
- Bigfoot bukan ditemukan dalam gim varian, melainkan dalam gim Busy Beaver biasa
Contoh kesulitan Busy Beaver yang sudah ada
- Beberapa mesin Turing yang dibuat manual memberikan contoh bahwa untuk membuktikan nilai Busy Beaver tertentu, kita harus membuktikan proposisi matematika sulit lainnya
- (BB(745)): membutuhkan pembuktian konsistensi ZFC
- (BB(27)): membutuhkan pembuktian Goldbach Conjecture
- (BB(15)) dan (BB(5,4)): membutuhkan pembuktian dugaan Erdős bahwa untuk (n > 8), representasi basis-3 dari (2^n) memiliki setidaknya satu digit 2
- Namun nilai-nilai Busy Beaver seperti ini saat ini berada di luar jangkauan yang bisa didekati
- Selama 60 tahun terakhir, nilai yang berhasil dibuktikan hanya (BB(2), BB(3), BB(4), BB(2,3)), dan diketahui bahwa (BB(6) > 10 \uparrow\uparrow 15)
- Sebelum menganalisis Bigfoot, (BB(3, 3)) dianggap masih mungkin dibuktikan
Definisi dan asal-usul Bigfoot
- Nama mesin Turing ini adalah Bigfoot, dan tabel transisinya didefinisikan oleh string berikut
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- Mesin ini terdaftar di bbchallenge
- Tabel transisinya adalah sebagai berikut
| State | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot adalah salah satu dari 160 holdout tidak resmi (BB(3,3)) yang tersisa dan dibagikan di kanal Discord bbchallenge.org
- Mesin Turing khusus ini pertama kali dibagikan oleh @savask pada 14 Oktober 2023 di kanal Discord yang sama, beserta deskripsi perilaku tingkat rendah
- Analisis berikutnya mengungkap struktur mirip Collatz dan sifat random walk bias
Perilaku yang direduksi menjadi konfigurasi (A(a,b,c))
- Ambil konfigurasi umum sebagai berikut
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- Ketika Bigfoot memasuki konfigurasi (A(a,b,c)) dengan (c \ge 1), aturan-aturan berikut menjelaskan perilaku selanjutnya secara persis sampai ia berhenti atau selamanya
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- Aturan-aturan ini mengiterasikan fungsi mirip Collatz pada parameter (b) dan (c)
- (a) bergerak seperti nilai akumulatif
- Jika (b \equiv 1 \pmod{6}) atau (b \equiv 4 \pmod{6}), (a) bertambah
- Jika (b \equiv 2 \pmod{6}), (a) berkurang
- Bigfoot hanya berhenti jika (a) hendak berkurang ke bawah 0
Trajektori yang diamati dari tape kosong
- Jika dimulai dari tape kosong, Bigfoot mencapai konfigurasi (A(2,1,2)) setelah 69 langkah
- Dalam simulasi setelah itu, (a) tampak terus meningkat, dan setelah 24 juta iterasi menjadi (a = 3.999.888)
- Jika kita mengasumsikan deret sisa (b \bmod 6) acak seragam, proses ini sama seperti random walk bias di garis bilangan
- Peluang bergerak ke kanan pada tiap langkah adalah (\frac{2}{3})
- Peluang bergerak ke kiri adalah (\frac{1}{3})
- Dalam teori Markov chain, dapat dibuktikan bahwa ketika posisi saat ini (a=n), peluang di masa depan mencapai (a=-1) adalah ((\frac{1}{2})^{n+1})
- Deret (b \bmod 6) yang sebenarnya bukan acak, melainkan sepenuhnya deterministik, dan secara konsisten mengikuti pola ganjil-ganjil-genap-genap
- Meski begitu, pada skala besar trajektorinya mirip dengan Markov chain acak
- Setelah 24 juta langkah, Markov chain diperkirakan bergerak ke kanan 8 juta kali dan ke kiri 4 juta kali
- Ini sangat dekat dengan nilai (a) sebenarnya, sekitar 4 juta
Heuristik “probviously” bahwa ia tidak berhenti
- Pada saat (a \approx 4.000.000), peluang Markov chain acak mencapai (a=-1) kira-kira ((\frac{1}{2})^{4.000.000})
- Angka ini begitu kecil sehingga secara ilmiah dapat diperlakukan seolah kegagalan sudah terjamin
- Jika Bigfoot berperilaku mirip Markov chain, ia tampaknya tidak akan berhenti
- Namun ini bukan proposisi matematika yang ketat, melainkan heuristik eksperimental
- Kita juga tidak bisa menyingkirkan kemungkinan Bigfoot berhenti setelah googolplex iterasi
- John Conway menciptakan istilah ini untuk menjelaskan heuristik bahwa dugaan Collatz “probviously” benar, tetapi bukti Collatz masih belum terlihat
Dua kemungkinan akhir bagi Bigfoot
- Bigfoot adalah salah satu dari dua hal berikut
- Berhenti
- Berjalan selamanya
- Jika berhenti, hal itu dapat dibuktikan dengan mempercepat iterasi fungsi mirip Collatz ini secukupnya dan mensimulasikannya sampai akhir
- Jika berjalan selamanya, kita harus membuktikan bahwa fungsi mirip Collatz ini tidak pernah mencapai transisi berhenti pada (a=0)
- Menurut heuristik Markov chain, kasus kedua tampak lebih masuk akal, dan yang ini tampak jauh lebih sulit dibuktikan
Nama Cryptids
- Mesin seperti ini dapat direduksi perilakunya menjadi aturan matematika yang relatif sederhana, tetapi aturan tersebut masuk ke kelas masalah matematika terbuka
- Ia mirip makhluk legendaris yang hanya dikabarkan berhenti atau tidak berhenti, tetapi tidak ada pihak yang dapat memberikan bukti konkret
- Ada usulan untuk menyebut mesin-mesin seperti ini Cryptids
- Ini adalah analogi dengan makhluk legendaris seperti Loch Ness Monster atau Chupacabra
- Mesin Turing ini dinamai Bigfoot karena tampak berjalan secara acak
Apakah perilaku mirip Collatz ini benar-benar sulit?
- Dinamika fungsi mirip Collatz khusus ini tampaknya merupakan masalah yang nyaris belum pernah dianalisis sebelumnya
- Masih ada kemungkinan bahwa sedikit teori bilangan dan komputasi dapat menemukan sifat matematika cerdik yang hanya berlaku untuk masalah ini
- Jika sifat seperti itu ditemukan, itu akan menunjukkan bahwa pembuktian (BB(3,3)) masih berada dalam jangkauan
- Pertanyaan yang dapat diajukan dalam masalah mirip Collatz secara empiris terbagi menjadi dua jenis
- Pertanyaan yang dapat dibuktikan relatif sepele
- Pertanyaan yang tidak diketahui cara pembuktiannya oleh matematikawan mana pun
- Fakta bahwa pada Bigfoot (b) mengulangi pola ganjil-ganjil-genap-genap, atau fakta bahwa setelah menerapkan aturan Collatz tradisional (3n+1), hasilnya selalu genap sehingga dibagi 2 pada langkah berikutnya, termasuk kategori pertama
- Hampir semua pertanyaan lain tentang perilaku sistem Collatz dapat dianggap sebagai contoh kategori kedua
Ekspresi alternatif dengan 81 kasus
- Ekspresi alternatif yang ditambahkan pada 18 Oktober 2023 mengurangi ketidaknyamanan deskripsi (A(a,b,c)) yang ada
- Deskripsi yang ada memiliki tiga ketidaknyamanan
- Parameter (b) dan (c) saling terkait
- Modulo input 6 dan modulo output 8 memiliki faktor persekutuan 2
- (b) mengikuti pola berulang ganjil-ganjil-genap-genap
- Matthew House menunjukkan bahwa masalah-masalah ini dapat dihindari jika konfigurasi baru didefinisikan sebagai berikut
[ B(a,b)=A(a,2b+1,2) ]
- Dengan menetapkan (b=81k+r) dan menggabungkan empat transisi asli menjadi satu transisi, perilaku mirip Collatz Bigfoot dapat dinyatakan sebagai aturan dengan 81 kasus
- Ekspresi ini menyelesaikan tiga ciri dari ekspresi (A) yang lama dan tampak lebih mirip dengan masalah Collatz klasik
- Namun karena harus menangani semua 81 kasus, ekspresi ini agak sulit dikelola
- Sebagian aturan bergantung pada kondisi (a \ge 2)
1 komentar
Pendapat di Hacker News
Daripada mengatakan BB(3, 3) itu sendiri sulit, tampaknya lebih tepat mengatakan bahwa ia mengodekan masalah sejenis Collatz, dan masalah-masalah seperti itu pada umumnya dianggap sangat sulit
Namun apakah instans spesifik ini memang sulit adalah persoalan terpisah. Perilakunya terlihat cukup condong ke satu arah, dan tidak seperti masalah Collatz klasik yang mengharuskan kita melihat lintasan semua bilangan bulat, di sini cukup melihat satu lintasan saja
Saya juga cukup setuju soal satu lintasan versus banyak lintasan. Namun jika kita mengasumsikan dunia tempat mesin Turing ini tidak berhenti, membuktikan satu lintasan sistem ini bisa dianggap “lebih sulit” daripada satu lintasan pada konjektur Collatz klasik. Jika konjektur Collatz benar, pembuktian lintasan tunggal mana pun pada akhirnya cukup berupa komputasi hingga; tetapi lintasan tunggal dalam tulisan ini harus ditunjukkan tidak pernah berhenti selamanya, sehingga membutuhkan matematika yang lebih canggih
Saya tidak ingin melebih-lebihkan. Ini bukan berarti untuk menyelesaikan BB(3, 3) kita pasti harus membuktikan konjektur Collatz atau masalah terbuka dalam matematika yang sudah banyak diteliti. Namun sebagai hasil “terbaik kedua”, bahwa ini adalah masalah sulit yang mirip dengan masalah yang telah banyak dikaji, saya rasa tetap bermakna. Seberapa sulit masalah mirip Collatz ini mungkin bisa dilihat dari siapa yang mampu menyelesaikannya
Saya ingin membantu memperjelas di sini. Ada mesin Turing dengan 748 state [0], dan saya memahaminya sebagai mesin yang berhenti hanya jika ZFC kontradiktif
Mesin ini adalah objek “fisik” yang bisa diimplementasikan dan dijalankan di komputer. Daya komputasi saat ini memang tidak cukup, tetapi secara prinsip tidak ada yang menghalangi kita menjalankan mesin ini selama BB(748) langkah. Jika berhenti, maka berdasarkan Teorema 1 kita membuktikan bahwa ZFC kontradiktif; jika tidak berhenti, tampaknya kita membuktikan bahwa ZFC konsisten
Inilah inti kebingungannya. Ini terlihat bukan seperti hasil abstrak, melainkan seperti komputasi yang benar-benar bisa dilakukan dan menghasilkan nilai
Tentu saja, menurut Teorema Ketaklengkapan Kedua Gödel, di dalam ZFC kita tidak dapat membuktikan konsistensi ZFC. Namun jika mesin Turing di atas berhenti, itu seolah membuktikan bahwa ZFC konsisten, sehingga tampak seperti kontradiksi
Di mana letak kesalahannya? Dugaan saya saat ini adalah bahwa dalam pembuktian Teorema 1, untuk menunjukkan bahwa mesin Turing 748 state tersebut berhenti hanya ketika ZFC kontradiktif, digunakan metateori yang lebih kuat daripada ZFC. Kalau begitu, itu bukan kontradiksi. Meskipun kita bisa menjalankannya selama BB(748) langkah, hal itu hanya menunjukkan bahwa ZFC+ membuktikan konsistensi ZFC, dan ini sudah diketahui. Misalnya ZFC + “ada kardinal tak terjangkau” dapat berperan demikian
Saya belum membaca makalahnya secara rinci, jadi tidak tahu apakah memang demikian. Adakah yang pernah memikirkan masalah ini secara mendalam dan bisa memberi wawasan?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Jika dewa busy beaver memberi tahu nilainya, secara teoretis kita bisa menjalankan mesin Turing selama itu dan, seperti yang Anda katakan, membuktikan apakah ZFC konsisten atau tidak. Namun agar manusia dapat menghitung BB(748), pada dasarnya kita harus mengetahui apakah mesin Turing 748 state spesifik ini suatu hari akan berhenti, dan juga apakah semua mesin Turing 748 state lainnya berhenti
Kalau pun seluruh materi dan energi alam semesta dipakai untuk membuat komputer, dan komputer itu menjalankan hanya tugas ini dengan efisiensi tertinggi yang dimungkinkan secara fisik, komputasinya tetap tidak akan selesai
Karena itu muncul titik di mana matematika terpisah dari fisika dan kenyataan. Kita masih bisa berbicara dan bernalar tentang objek-objek seperti itu, tetapi objek tersebut tidak lagi memiliki makna fisik
Namun membuktikan bahwa ia tidak berhenti jauh lebih sulit. Menjalankannya selama TREE(3) langkah bukanlah bukti bahwa ia tidak akan berhenti pada langkah TREE(3)+1
Jadi sayangnya kita tidak bisa mengatakan “jalankan saja”
Saya suka gaya penulisan penulisnya. Tulisan itu membantu memahami topik tanpa terasa bertele-tele, dan menemukan titik keseimbangan seperti itu tidak mudah
Materi terkait: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... dan https://googology.fandom.com/wiki/Googology_Wiki
Apakah maksudnya BB tidak dapat dihitung itu seperti ini? Semakin besar BB, ia mencakup seluruh matematika, dan pada akhirnya kita harus membuktikan semuanya?
Seluruh sisa matematika diselundupkan ke dalam BB melalui masalah penghentian. Karena kita bisa menulis program yang berhenti hanya ketika suatu dugaan matematika sembarang benar atau salah, mencoba menyelesaikan masalah penghentian atau BB berarti harus mengetahui seluruh matematika[0]. Ini dimungkinkan karena kelengkapan Turing adalah batas komputabilitas. Sesuatu yang dapat memuat komputer, pada dirinya sendiri adalah komputer
[0] Sebenarnya ini sendiri bukan alasan yang membuat penghentian tidak dapat diputuskan. Ketidakdapatdiputusan muncul dari program yang “menarik dirinya sendiri ke dalam masalah penghentian”, misalnya dengan berhenti hanya ketika penentu penghentian hipotetis mengatakan bahwa dirinya tidak akan berhenti
Ada masalah matematika yang kita “ketahui” tidak dapat kita buktikan maupun bantah. Itulah isi teorema ketidaklengkapan pertama Gödel, kecuali jika semua proposisi dapat dibuktikan benar sekaligus salah. Jika semua proposisi dapat dibuktikan benar dan salah, sistem pembuktian itu tidak berguna, dan tindakan membuktikan tidak lagi bermakna, sehingga kita harus memilih sistem pembuktian lain yang tidak seperti itu. Jadi biasanya kita mengasumsikan kasus pertama, yakni ada masalah yang tidak dapat dibuktikan maupun dibantah. Tambahan lagi, teorema ketidaklengkapan kedua Gödel menyatakan bahwa kita tidak pernah dapat membuktikan bahwa kita berada dalam kasus pertama itu sendiri
Dan fakta bahwa BB tidak dapat dihitung berarti, ketika BB menjadi cukup besar, suatu saat kita dapat mengodekan program yang berhenti hanya ketika masalah yang tidak dapat dibuktikan maupun dibantah itu benar. Karena itu kita tidak dapat membuktikan apakah program tersebut berhenti atau tidak
Secara ketat, membuktikan atau membantah sesuatu yang tidak dapat dibuktikan maupun dibantah berarti membuktikan sesuatu yang salah, dan itu pada akhirnya dapat dipakai untuk “membuktikan” semua proposisi, jadi dalam arti tertentu ungkapan “mencakup seluruh matematika” memang benar. Namun ini adalah kondisi ambang, dan bekerja jauh sebelum muncul mesin Turing yang cukup besar untuk mengodekan “semua” masalah matematika. Pada kenyataannya tidak ada jumlah state berhingga yang cukup untuk mengodekan semua masalah matematika, karena string aritmetika dapat terus dibuat semakin panjang
Setelah itu, tidak mengejutkan bahwa ada BB yang tidak dapat kita selesaikan; yang menarik adalah menyelidiki BB mana yang dapat diselesaikan dan mana yang tidak
Saya tidak mengerti mengapa bagian “karena itu, menyelesaikan masalah BB(3, 3) setidaknya sesulit menyelesaikan masalah mirip Collatz ini” mengejutkan. Sebenarnya ini tampak hampir terbukti secara jelas. Bukankah semua masalah BB(x, y) dapat direduksi menjadi masalah tipe Collatz?
BB(x, y) dapat dengan mudah diubah menjadi masalah penghentian. Cari semua mesin dengan x state dan y simbol yang berhenti, dan pisahkan yang tidak berhenti. Lalu jalankan semua mesin yang berhenti itu bersama-sama satu langkah demi satu langkah sampai semuanya berhenti; jumlah langkah yang dijalankan menjadi nilai BB(x, y)
Sejauh yang saya tahu, Conway menunjukkan cara mereduksi masalah penghentian menjadi masalah tipe Collatz. Kalau begitu, melalui reduksi dua tahap dari BB ke masalah penghentian lalu ke masalah Collatz, tampaknya BB(x, y) untuk x, y sembarang dapat direduksi menjadi masalah tipe Collatz
Yang dibutuhkan adalah reduksi dari Collatz ke masalah penghentian, lalu ke B(x,y). Dari Collatz ke masalah penghentian itu jelas, tetapi dari masalah penghentian ke B(x,y) tidak begitu jelas. Kita harus mendefinisikan dengan tepat subset masalah penghentian apa yang dapat direduksi dari Collatz tetapi tidak lebih sulit daripada B(3,3)
Masalah penghentian tampaknya sering “menghalangi” banyak pendekatan terhadap teori informasi algoritmik dan induksi yang berbasis program yang dapat dihitung. Namun saya penasaran apakah ada penelitian tentang apakah masalah penghentian benar-benar berdampak material pada kemampuan induksi di dunia nyata
Misalnya, anggap ada sebuah oracle yang memberi tahu apakah suatu mesin Turing universal monoton sembarang telah mencapai titik dalam eksekusinya di mana ia tidak akan lagi menulis apa pun ke pita output. Apakah hasil induksi dengan oracle ini akan jauh berbeda dari cara menelusuri seluruh ruang program, lalu jika suatu program tidak menghasilkan output selama n langkah yang cukup besar, kita cukup “melewati” program itu dan lanjut ke program berikutnya?
Yang saya maksud adalah induksi atas data yang “biasa” dan dapat dikompresi, bukan kasus batas atau contoh adversarial yang sengaja dibuat seperti BB(3,3)
Sebagai peneliti keamanan, saya sendiri menulis fuzzer. Fuzzer adalah alat yang secara otomatis mencari input yang bermakna secara keamanan untuk program yang diuji. Ia menghasilkan dan memutasi input secara algoritmik, memasukkannya ke program, lalu mengamati apa yang terjadi puluhan, ratusan, atau ribuan kali per detik
Jika suatu input membuat program crash, itu bisa dianggap telah “menghentikan” program. Untuk membuat fuzzer yang dapat menemukan semua bug pada program apa pun dalam waktu yang realistis, rasanya kita harus menyelesaikan masalah penghentian. Kenyataannya, bahkan setelah miliaran pengujian, masih ada orang yang menemukan bug di image decoder, jadi benar bahwa fuzzer yang kita miliki tidak sempurna
Pada saat yang sama, di dunia nyata saya juga melihat bahwa jika diberi cukup waktu, fuzzer dapat menembus lebih dalam ke bagian dalam program kompleks daripada yang diperkirakan. Validasi input yang dilakukan target uji, serta memori dan penyimpanan PC modern yang terbatas, sampai batas tertentu menempatkan fuzzer pada jalurnya. Pengecualiannya adalah ketika kriptografi terlibat; bagi fuzzer, itu seperti rawa tar komputasional. Program yang dipertahankan dengan baik dan dispesifikasikan dengan baik bertindak sebagai pagar pembatasnya sendiri sehingga fuzzer tidak perlu menyelesaikan masalah penghentian
Jadi untuk deteksi bug keamanan pada program, saya melihatnya begini. Selain kriptografi, fuzzer kuat untuk menargetkan program yang melakukan validasi input ketat. Sebaliknya, pada program yang tidak melakukan validasi input ketat, fuzzer tidak terlalu diperlukan, dan di tempat seperti itu fuzzer juga belum tentu bekerja dengan baik
Apakah ada intuisi mengapa BBB, yaitu busy beaver yang berbunyi bip, bisa berjalan jauh lebih lama sebelum kuasi-berhenti?
Satu hal yang terlihat adalah bahwa pada dasarnya tidak perlu memakai keadaan berhenti. Dalam arti itu, BBB 3-keadaan mungkin mirip dengan BB 4-keadaan. Penasaran apakah ada hal lain
Jadi program atau mesin Turing berukuran X dapat dibuat untuk menyimulasikan eksekusi semua program berukuran Y, dengan Y >> X. Jika dibuat berbunyi bip setiap kali salah satu program itu berhenti, bip terakhir terjadi saat menyimulasikan program yang berhenti setelah lebih banyak langkah daripada BB(Y). Maka BBB(X) > BB(Y) >> BB(X)
Kalau ingatan saya benar, karena konstruksi yang pada dasarnya sama, jika kita tahu BB(N), kita bisa menghitung masalah berhenti untuk program berukuran hingga N dengan sangat lambat, sedangkan jika kita tahu BBB(N), kita bisa menghitung masalah berhenti untuk mesin Turing yang diberi oracle berhenti berukuran hingga itu dengan jauh lebih lambat
Ini terlalu nerd buat saya
Saya penasaran pengetahuan prasyarat apa yang dibutuhkan untuk memahami hal seperti ini. Apakah cukup hanya tahu kalkulus dasar? Topik atau mata kuliah spesifik apa yang bisa jadi fondasi yang bagus?
[1] https://www.scottaaronson.com/writings/bignumbers.html
Mengikuti buku teks pengantar ilmu komputer teoretis akan membantu memahami sebagian besar isinya. Mahasiswa ilmu komputer biasanya mempelajarinya di tahun pertama atau kedua, dan materinya tidak mudah. Di kampus saya, ini salah satu ujian yang paling ditakuti
Buku pengantar Hopcroft & Ullmann bagus. Namun karena ada begitu banyak materi terkait, anggap saja itu sebagai titik awal
Banyak program sarjana ilmu komputer seharusnya punya mata kuliah dengan materi yang tersedia secara publik
Bagaimana cara membaca
1RB2RA1LC_2LC1RB2RB_---2LA1LA?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
Misalnya, jika sedang di keadaan B dan nilai pita di posisi head saat ini adalah 0, tulis 2, gerakkan head satu langkah ke kiri, lalu masuk ke keadaan C
Tiga karakter itu berarti simbol yang ditulis, keadaan baru, dan arah gerak. Keadaan
---adalah berhenti(keadaan, nilai pita)saat ini dipetakan ke tripel(nilai pita baru, arah gerak head pita, keadaan baru)[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA