Misteri Angka Busy Beaver: Mesin Turing Terpanjang yang Tak Terbayangkan

Awalnya, seorang matematikawan bernama Tibor Radó menciptakan permainan yang dikenal sebagai busy beaver untuk mempelajari sejauh mana mesin komputer sederhana dapat berjalan sebelum berhenti. Permainan ini melibatkan mesin Turing yang memiliki sejumlah aturan tertentu, dengan tujuan menemukan mesin yang menjalankan langkah terbanyak sebelum akhirnya berhenti. Urutan angka busy beaver, seperti 1, 6, 21, 107, hingga angka besar BB(5) yang mencapai puluhan juta, merupakan contoh seberapa cepat kompleksitas mesin tersebut dapat berkembang. Masalah fundamental dari permainan busy beaver berkaitan erat dengan masalah halting yang ditemukan oleh Alan Turing pada 1936. Ia membuktikan tidak ada metode universal untuk menentukan kapan program komputer akan berhenti atau berjalan selamanya. Permasalahan ini semakin rumit ketika jumlah aturan mesin Turing bertambah, sehingga simulasi komputer biasa tidak memadai untuk mencari angka busy beaver terbesar. Selama beberapa dekade, para pemburu busy beaver berusaha mencari mesin dengan runtime terpanjang, terutama untuk BB(6). Pada tahun 2022, komunitas bernama Busy Beaver Challenge, yang terdiri dari ilmuwan profesional dan amatir, berhasil menentukan nilai BB(5) secara pasti dan terus menekan batas bawah BB(6) ke angka yang sangat besar, jauh melampaui jumlah digit yang bisa ditulis bahkan dengan seluruh materi alam semesta. Penemuan terbaru yang dilakukan oleh anggota komunitas ini menggunakan teknik dan konsep matematika yang sangat maju, seperti tetration dan pentation, yang digunakan untuk menyatakan angka yang melibatkan tumpukan pangkat yang sangat tinggi. Mesin-mesin baru ini memiliki runtime yang bahkan tidak bisa dijelaskan dengan tanda pangkat biasa, menunjukkan betapa tak terbatasnya kompleksitas dalam permainan busy beaver. Meskipun beberapa mesin seperti Antihydra belum diketahui apakah akan berhenti atau tidak, keberadaan mereka menghubungkan masalah ini dengan masalah-masalah matematika besar lainnya, seperti konjektur Collatz. Ini menunjukkan bahwa memecahkan angka busy beaver bukan hanya soal komputasi tetapi juga butuh terobosan dalam matematika murni. Namun para pemburu busy beaver tetap optimis karena mereka menikmati proses penemuan ini sebagai sebuah seni dan tantangan yang terus berkembang.