Peneliti mendekati batas komputasi dengan Busy Beaver kelima

• Pendahuluan

  • Empat puluh tahun lalu, para ilmuwan komputer berkumpul di Dortmund, Jerman, untuk berlomba menemukan Busy Beaver kelima
  • Busy Beaver adalah program komputer sederhana yang dapat berjalan dalam waktu sangat lama
  • Program-program ini terkait dengan masalah-masalah tak terpecahkan terkenal dalam matematika, dan berasal dari persoalan lama dalam ilmu komputer
  • Dua tahun lalu, mahasiswa pascasarjana Tristan Stérin memulai Busy Beaver Challenge, dan lebih dari 20 kontributor dari seluruh dunia ikut berpartisipasi
  • Kini, tim tersebut telah mengonfirmasi nilai BB(5) sebagai 47,176,870

• Akan berhenti, atau tidak akan berhenti

  • Program Busy Beaver ditulis sebagai instruksi untuk komputer teoretis yang disebut mesin Turing
  • Mesin Turing melakukan komputasi dengan membaca dan menulis 0 dan 1 pada pita tak berhingga
  • Masalah memprediksi apakah sebuah mesin Turing akan berhenti atau berjalan selamanya disebut masalah penghentian
  • Masalah penghentian tidak memiliki solusi umum, yang membuat perburuan Busy Beaver semakin menarik

• Munculnya sang berang-berang

  • Matematikawan Tibor Radó menciptakan permainan Busy Beaver pada tahun 1962
  • Dalam setiap kelompok aturan, mesin Turing yang berjalan paling lama disebut Busy Beaver
  • BB(n) menyatakan jumlah langkah yang dibutuhkan mesin Busy Beaver dengan n aturan sebelum berhenti

• Koloni berang-berang Brady

  • Allen Brady mengembangkan teknik berburu Busy Beaver pada 1960-an, dan pada 1974 menentukan nilai Busy Beaver keempat
  • BB(4) dipastikan sebagai mesin yang berhenti setelah 107 langkah

• Busy Beaver kelima

  • Pada kompetisi Dortmund tahun 1984, perburuan besar pertama untuk menemukan Busy Beaver kelima dimulai
  • Pada 1989, Heiner Marxen menemukan mesin yang berhenti setelah 47,176,870 langkah
  • Pada 2003, Georgi Georgiev menghentikan perburuan BB(5), menyisakan 43 mesin Turing yang belum terselesaikan

• Panggilan untuk semua pemburu

  • Tristan Stérin memulai Busy Beaver Challenge pada 2022, dengan kontributor dari seluruh dunia ikut serta
  • Shawn Ligocki bergabung dengan tim pada 2022 dan memberikan kontribusi penting
  • Justin Blanchard mengembangkan metode closed tape language, salah satu teknik tim yang paling kuat

• Mendekati sang monster

  • Skelet #1 dan #17 adalah mesin yang sangat sulit, dan tim menggabungkan berbagai ide untuk menyelesaikannya
  • Pada Mei 2023, kontributor anonim bernama mxdys menyelesaikan pembuktian Coq

• Tempat berang-berang berkeliaran

  • Tim sedang menulis makalah akademik formal, dan sebagian anggotanya berupaya menemukan Busy Beaver berikutnya
  • BB(6) tampaknya akan sulit diselesaikan karena persoalan yang mirip dengan dugaan Collatz

Opini GN⁺

• Artikel ini memberikan contoh menarik tentang eksplorasi batas-batas ilmu komputer
• Busy Beaver Challenge menunjukkan pentingnya riset kolaboratif
• Penyelesaian BB(5) memiliki makna besar bagi komunitas ilmu komputer dan matematika
• Proyek dengan karakteristik serupa termasuk riset tentang dugaan Collatz
• Saat mengadopsi teknologi baru atau open source, kolaborasi dan reproduksibilitas sangat penting

[GN⁺]

Komentar Hacker News

• Komentar tentang posting blog Scott Aaronson dibagikan

  • Tautan ke utas sebelumnya yang relevan juga disertakan

• Ada berbagai variasi dari masalah Busy Beaver

  • Ada variasi yang menggunakan lambda calculus
  • Ada variasi yang diekspresikan dengan kompleksitas Kolmogorov

• Dibagikan kisah seorang insinyur yang berhenti dari pekerjaannya untuk meneliti masalah Busy Beaver

  • Ia bertanya-tanya apakah insinyur ini adalah mxdys

• Ada penyebutan tentang pembuktian Coq

  • Muncul kemungkinan bahwa ini bukan pembuktian yang dirapikan sejak awal, melainkan pembuktian pertama yang berhasil dirapikan

• Ada pendapat bahwa makalah Busy Beaver asli karya Tibor Radó mudah dibaca dan menyenangkan

  • Tautan ke versi modern dari makalah tersebut disertakan

• Masalah berhenti untuk program mesin Turing 5-status 2-warna telah diselesaikan

  • Ditanyakan apakah ini bisa diterapkan pada kasus 2-status 4-warna

• Disebutkan adanya gagasan keliru bahwa manusia bisa menyelesaikan masalah berhenti secara intuitif

• Dibagikan pengalaman menulis program untuk menyelesaikan masalah Cutting Stock dalam proyek pribadi

  • Menggunakan metode optimisasi yang mirip dengan program Brady

• Ada pendapat bahwa kemampuan membuktikan apakah program mesin Turing 5-status berhenti atau tidak merupakan keberuntungan

• Menurut posting blog Scott Aaronson, ada 16,679,880,978,201 mesin Turing 5-status

  • Ia penasaran berapa persen di antaranya yang berhenti

• Nilai fungsi Busy Beaver dibagikan

  • BB(5) terbukti bernilai 47,176,870
  • BB(6) setidaknya bernilai 10^10^...^10 (menara eksponen 15 tingkat)