Program Komputer Super Lambat Mengungkapkan Batasan Dasar Matematika


Pemrogram biasanya menginginkan untuk meminimalkan waktu yang dibutuhkan kode mereka untuk dieksekusi. Tetapi pada tahun 1962, matematikawan Hungaria Tibor Radó mengajukan masalah sebaliknya. Dia bertanya: Berapa lama program komputer sederhana dapat berjalan sebelum dihentikan? Radó menjuluki program yang sangat tidak efisien tetapi masih berfungsi ini sebagai “berang-berang sibuk”.

Cerita asli dicetak ulang dengan izin dari Majalah Quanta, sebuah publikasi independen editorial dari Simons Foundation yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren dalam matematika serta ilmu fisika dan kehidupan.

Menemukan program-program ini telah menjadi teka-teki yang sangat mengalihkan bagi pemrogram dan penghobi matematika lainnya sejak program itu dipopulerkan di Scientific AmericanKolom “Computer Recreations” pada tahun 1984. Namun dalam beberapa tahun terakhir, permainan berang-berang yang ramai, seperti yang dikenal, telah menjadi objek studi tersendiri, karena telah menghasilkan koneksi ke beberapa konsep paling terkemuka dan terbuka masalah dalam matematika.

“Dalam matematika, ada batas yang sangat jelas antara apa yang merupakan rekreasi yang menyenangkan dan apa yang sebenarnya penting,” kata Scott Aaronson, seorang ilmuwan komputer teoretis di University of Texas, Austin yang baru-baru ini menerbitkan survei kemajuan dalam “BusyBeaverology.”

Karya terbaru menunjukkan bahwa pencarian program komputer yang berjalan lama dapat menerangi keadaan pengetahuan matematika, dan bahkan memberi tahu kami apa yang dapat diketahui. Menurut para peneliti, permainan berang-berang sibuk memberikan tolok ukur konkret untuk mengevaluasi kesulitan masalah tertentu, seperti dugaan Goldbach yang belum terpecahkan dan hipotesis Riemann. Ia bahkan menawarkan sekilas di mana landasan logis yang mendasari matematika rusak. Ahli logika Kurt Gödel membuktikan keberadaan matematika terra incognita hampir seabad yang lalu. Tetapi permainan berang-berang yang sibuk dapat menunjukkan di mana ia sebenarnya terletak pada garis angka, seperti peta kuno yang menggambarkan ujung dunia.

Game Komputer yang Tidak Dapat Dihitung

Permainan berang-berang yang sibuk adalah tentang perilaku mesin Turing — komputer primitif dan ideal yang dikandung oleh Alan Turing pada tahun 1936. Mesin Turing melakukan tindakan pada selotip tak berujung yang dibagi menjadi beberapa kotak. Itu dilakukan sesuai dengan daftar aturan. Aturan pertama mungkin mengatakan:

Jika persegi berisi 0, ganti dengan 1, pindahkan satu persegi ke kanan dan lihat aturan 2. Jika persegi berisi 1, tinggalkan 1, pindahkan satu persegi ke kiri dan konsultasikan aturan 3.

Setiap aturan memiliki gaya pilih-pilih-petualangan-Anda-bercabang ini. Beberapa aturan mengatakan untuk melompat kembali ke aturan sebelumnya; akhirnya ada aturan yang berisi instruksi untuk “dihentikan”. Turing membuktikan bahwa komputer sederhana ini mampu melakukan segala kemungkinan perhitungan, dengan instruksi yang tepat dan waktu yang cukup.

Seperti yang dicatat Turing pada tahun 1936, untuk menghitung sesuatu, mesin Turing pada akhirnya harus berhenti — tidak bisa terjebak dalam putaran tak terbatas. Namun ia juga membuktikan bahwa tidak ada metode yang dapat diandalkan dan dapat diulang untuk membedakan mesin yang berhenti dari mesin yang berjalan selamanya — fakta yang dikenal sebagai masalah berhenti.

Permainan berang-berang yang sibuk bertanya: Dengan sejumlah peraturan, berapa jumlah langkah maksimum yang dapat diambil mesin Turing sebelum berhenti?

Misalnya, jika Anda hanya diperbolehkan satu aturan, dan Anda ingin memastikan bahwa mesin Turing berhenti, Anda dipaksa untuk memasukkan instruksi penghentian segera. Oleh karena itu, nomor berang-berang sibuk dari mesin satu aturan, atau BB (1), adalah 1.

Tetapi menambahkan hanya beberapa aturan lagi secara instan meningkatkan jumlah mesin yang perlu dipertimbangkan. Dari 6.561 mesin yang memungkinkan dengan dua aturan, salah satu yang berjalan paling lama — enam langkah — sebelum berhenti adalah berang-berang yang sibuk. Tetapi sebagian lainnya lari begitu saja. Tak satu pun dari ini adalah berang-berang yang sibuk, tetapi bagaimana Anda secara definitif menyingkirkan mereka? Turing membuktikan bahwa tidak ada cara untuk secara otomatis mengetahui apakah mesin yang berjalan selama seribu atau sejuta langkah pada akhirnya tidak akan berhenti.

Itulah mengapa sulit menemukan berang-berang yang sibuk. Tidak ada pendekatan umum untuk mengidentifikasi mesin Turing yang berjalan paling lama dengan jumlah instruksi yang berubah-ubah; Anda harus memecahkan secara spesifik setiap kasus sendiri. Dengan kata lain, permainan berang-berang yang sibuk, secara umum, “tidak dapat dihitung”.

Diposting oleh : joker123