Tapi seberapa lebih sulit? Pada 1962, matematikawan Tibor Radó menemukan cara baru untuk mengeksplorasi pertanyaan ini melalui apa yang dia sebut permainan busy beaver. Untuk memainkannya, mulailah dengan memilih sejumlah aturan tertentu—sebut saja angka itu n. Tujuan Anda ialah menemukan mesin Turing dengan n-aturan yang berjalan paling lama sebelum akhirnya berhenti. Mesin ini disebut busy beaver, dan angka busy beaver yang sesuai, BB(n), adalah jumlah langkah yang diperlukan.
Secara prinsip, untuk menemukan busy beaver untuk n tertentu, Anda hanya perlu melakukan beberapa hal. Pertama, buat daftar semua mesin Turing n-aturan yang mungkin. Selanjutnya, gunakan program komputer untuk mensimulasikan jalannya setiap mesin. Cari tanda-tanda bahwa mesin tidak akan pernah berhenti—misalnya, banyak mesin akan masuk ke dalam putaran berulang tanpa henti. Buang semua mesin yang tidak berhenti ini. Akhirnya, catat berapa banyak langkah yang diambil setiap mesin lain sebelum berhenti. Mesin dengan waktu proses terlama adalah busy beaver Anda.
Dalam praktiknya, ini menjadi rumit. Sebagai permulaan, jumlah mesin yang mungkin tumbuh dengan cepat seiring setiap aturan baru. Menganalisisnya semua satu per satu akan sia-sia, jadi Anda perlu menulis program komputer khusus untuk mengklasifikasikan dan membuang mesin. Beberapa mesin mudah diklasifikasikan: Mereka要么 berhenti dengan cepat atau masuk ke dalam loop tak hingga yang mudah diidentifikasi. Tetapi yang lain berjalan untuk waktu yang lama tanpa menampilkan pola yang jelas. Untuk mesin-mesin ini, masalah pemberhentian memang layak mendapatkan reputasi menakutkannya.
Semakin banyak aturan yang ditambahkan, semakin banyak daya komputasi yang diperlukan. Tetapi kekuatan kasar tidaklah cukup. Beberapa mesin berjalan sangat lama sebelum berhenti sehingga mensimulasikannya langkah demi langkah adalah mustahil. Diperlukan trik-trik matematika yang cerdik untuk mengukur waktu proses mereka.
“Peningkatan teknologi pasti membantu,” kata Shawn Ligocki, seorang insinyur perangkat lunak dan pemburu busy beaver lama. “Tapi itu hanya membantu sampai sejauh tertentu.”
Akhir Sebuah Era
Pemburu busy beaver mulai mengikis masalah BB(6) dengan sungguh-sungguh pada tahun 1990-an dan 2000-an, selama kebuntuan dalam perburuan BB(5). Di antara mereka adalah Shawn Ligocki dan ayahnya, Terry, seorang matematikawan terapan yang menjalankan program pencarian mereka di luar jam kerja pada komputer-komputer kuat di Lawrence Berkeley National Laboratory. Pada 2007, mereka menemukan sebuah mesin Turing enam-aturan yang memecahkan rekor untuk waktu proses terlama: Jumlah langkah yang diperlukan sebelum berhenti memiliki hampir 3.000 digit. Itu adalah angka yang kolosal menurut ukuran biasa. Tapi itu tidak terlalu besar untuk dituliskan. Dalam font 12-point, 3.000 digit itu kira-kira akan memenuhi satu lembar kertas.
Pada 2022, Shawn Ligocki menemukan sebuah mesin Turing enam-aturan yang waktu prosesnya memiliki lebih banyak digit daripada jumlah atom di alam semesta.
Foto: Kira Treibergs
Tiga tahun kemudian, seorang mahasiswa sarjana ilmu komputer Slovakia bernama Pavel Kropitz memutuskan untuk menangani perburuan BB(6) sebagai proyek tesis senior. Dia menulis program pencariannya sendiri dan menyiapkannya untuk berjalan di latar belakang pada jaringan 30 komputer di lab universitas. Setelah satu bulan dia menemukan sebuah mesin yang berjalan jauh lebih lama daripada yang ditemukan oleh keluarga Ligocki—sebuah “juara” baru, dalam istilah para pemburu busy beaver.
“Saya beruntung, karena orang-orang di lab sudah mengeluh tentang penggunaan CPU saya dan saya harus mengurangi sedikit,” tulis Kropitz dalam pertukaran pesan langsung di server Busy Beaver Challenge Discord. Setelah satu bulan pencarian lagi, dia memecahkan rekor miliknya sendiri dengan sebuah mesin yang waktu prosesnya memiliki lebih dari 30.000 digit—cukup untuk mengisi sekitar 10 halaman.