Bayangkan jika pekerjaan Anda sehari-hari adalah berburu monster. Bukan monster sungguhan, tentu saja, tapi monster dalam wujud kode-kode rumit yang bisa bikin komputer nge-hang. Kedengarannya seperti plot film fiksi ilmiah murahan? Tunggu dulu, karena ini adalah dunia nyata bagi para “pemburu berang-berang sibuk” (busy beaver hunters).
Mengenal Berang-Berang Sibuk: Lebih Rumit dari Pacar yang Labil
Di dunia matematika dan ilmu komputer, “berang-berang sibuk” adalah sebutan untuk Turing machine (semacam model komputer teoritis) dengan jumlah aturan tertentu yang bisa berjalan paling lama sebelum akhirnya berhenti. Konsep ini dicetuskan oleh matematikawan Tibor Radó pada tahun 1962 sebagai cara untuk mengukur kompleksitas komputasi. Sederhananya, ini seperti mencari program komputer paling efisien yang bisa melakukan tugas tertentu.
Tapi kenapa disebut berang-berang? Mungkin karena berang-berang dikenal sebagai hewan yang pekerja keras dan suka membangun bendungan yang rumit. Mirip seperti para Turing machine ini yang “bekerja” dengan aturan-aturan yang kompleks sampai akhirnya “bendungan” mereka selesai dan mereka berhenti.
Mencari berang-berang sibuk bukanlah perkara mudah. Kita harus membuat daftar semua kemungkinan Turing machine dengan sejumlah aturan tertentu, lalu menjalankan simulasi untuk masing-masing mesin. Mesin-mesin yang terjebak dalam perulangan tak berujung atau langsung berhenti harus disingkirkan. Sisanya diadu, siapa yang paling lama “bekerja” sebelum akhirnya berhenti, dialah pemenangnya.
Masalahnya, jumlah kemungkinan Turing machine tumbuh sangat cepat seiring dengan bertambahnya jumlah aturan. Menganalisisnya satu per satu akan menjadi pekerjaan yang mustahil. Kita butuh program komputer khusus untuk mengklasifikasikan dan menyingkirkan mesin-mesin yang tidak relevan. Beberapa mesin mudah diklasifikasikan, tapi ada juga yang berjalan sangat lama tanpa pola yang jelas. Di sinilah letak tantangan sebenarnya.
Shawn Ligocki, seorang software engineer dan pemburu berang-berang sibuk berpengalaman, mengakui bahwa peningkatan teknologi sangat membantu. Tapi, menurutnya, teknologi saja tidak cukup. Beberapa mesin bisa berjalan sangat lama sebelum berhenti, sehingga menyimulasikannya langkah demi langkah menjadi tidak mungkin. Kita butuh trik matematika cerdas untuk mengukur waktu berjalannya.
Ketika Berang-Berang Sibuk Bikin Komputer Jebol
Perburuan berang-berang sibuk dengan enam aturan (BB(6)) dimulai pada era 90-an dan 2000-an. Shawn Ligocki dan ayahnya, Terry, seorang matematikawan terapan, ikut terjun dalam perburuan ini. Mereka menjalankan program pencarian mereka di komputer-komputer canggih di Lawrence Berkeley National Laboratory.
Pada tahun 2007, mereka menemukan Turing machine enam aturan yang memecahkan rekor waktu berjalan terlama. Jumlah langkah yang dibutuhkan sebelum berhenti mencapai hampir 3.000 digit. Angka yang sangat besar, tapi masih bisa dituliskan di selembar kertas.
Namun, kejutan datang tiga tahun kemudian. Pavel Kropitz, seorang mahasiswa ilmu komputer asal Slovakia, memutuskan untuk menaklukkan BB(6) sebagai proyek tesisnya. Ia menulis program pencarian sendiri dan menjalankannya di jaringan 30 komputer di laboratorium universitas.
Setelah sebulan, ia menemukan mesin yang berjalan jauh lebih lama daripada mesin yang ditemukan oleh Ligocki. “Saya beruntung, karena orang-orang di laboratorium sudah mulai mengeluh tentang penggunaan CPU saya dan saya harus mengurangi sedikit,” tulis Kropitz di server Discord Busy Beaver Challenge.
Tidak berhenti di situ, setelah sebulan pencarian lagi, Kropitz kembali memecahkan rekornya sendiri dengan mesin yang waktu berjalannya mencapai lebih dari 30.000 digit. Cukup untuk mengisi sekitar 10 halaman kertas!
BB(6): Monster yang Belum Bisa Dijinakkan Sepenuhnya
Penemuan Kropitz ini menjadi babak baru dalam perburuan berang-berang sibuk. Tapi, bukan berarti masalah BB(6) sudah sepenuhnya terpecahkan. Masih banyak misteri yang belum terungkap, dan para pemburu terus mencari mesin-mesin yang lebih “sibuk” lagi.
Perburuan berang-berang sibuk ini bukan sekadar mencari rekor atau angka-angka fantastis. Lebih dari itu, ini adalah upaya untuk memahami batasan-batasan komputasi dan kompleksitas. Ini juga menunjukkan bahwa ada masalah-masalah matematika yang sangat sederhana untuk dijelaskan, tapi sangat sulit untuk dipecahkan.
Jadi, lain kali jika Anda merasa frustrasi dengan program komputer yang lambat atau bug yang sulit dipecahkan, ingatlah para pemburu berang-berang sibuk ini. Mereka berhadapan dengan monster yang jauh lebih menakutkan daripada sekadar error message. Mereka adalah para pahlawan tanpa tanda jasa yang terus menggali batas-batas pengetahuan kita tentang komputasi.
Dan mungkin, suatu saat nanti, mereka akan menemukan berang-berang sibuk yang waktu berjalannya melebihi jumlah atom di alam semesta. Siapa tahu?
