Pada tahun 1936 seorang jenius dari Universitas Cambridge yang berjasa menghentikan Perang Dunia II dengan memecahkan Sandi Enigma Nazi yaitu Alan Turing, muncul untuk menjawab pertanyaan Hilbert yang belum selesai ini. Tetapi untuk itu Alan Turing harus menemukan sebuah komputer modern. Turing membayangkan sebuah alat yang dengannya kita dapat melakukan penalaran dan mengimput pernyataan dan mengambil keputusan tampa batas.
Ia membuat sebuah mesin dengan pita panjang ber sel persegi yang masing-masing berisi angka 0 atau 1 yang dapat saja bergerak ke kiri dan ke kanan untuk menggandakan output. Mesin Turing dianggap sangat sederhana dan efektif karena menggunakan data numerik sebagai basis input dan operasinya sehingga lebih menggambarkan sebuah mekanisme algoritma. Ini berguna untuk menjawab tentang problem decidabilitiy yang yang Hilbert pertanyakan.
Mesin Turing memiliki problem pada keputusan berhenti atau terus mengoperasikan data pada saat pemrosesan yang disebut dengan problem Halting. Mesin Turing dapat saja bergerak tanpa henti secara reversal seperti cell dalam game of life karena sebuah input. Ada tiga jenis klasifikasi data dalam mesin turing yakni decidable language yang berarti input yang dapat diputuskan jika bersifat rekursif, Partially Decidable Language yang berarti kadang dapat diperoses dan kadang juga tidak, dan yang ketiga Undecidable Language yaitu input yang mungkin termasuk bahasa yang dapat diputuskan secara parsial namun tidak dapat diproses. Terkadang sebuah input kode dalam dalam mesin turing menyebabkan problem dalam penghentian atau Halting alias head bergerak secara reversal tanpa batas (Infinite loop) sehingga tidak memutuskan apapun. Namun mesin itu terus begerak seolah sedang memproses sesuatu.
Itulah yang membuat mesin Turing sangat berguna dalam menjawab pertanyaan Hilbert tentang decidability. Pada kasus undecidabelity mesin turing tidak dapat berhenti dalam proses sirkular tanpa batas. Alan Turing menyadari masalah Halting ini mirip dengan masalah yang dipikirkan Hilbert dan bahkan menjawab pertanyaannya. Jika kita mengetahaui bagaimana masalah ini terjadi. Kita bisa memutuskan apakah suatu pernyataan yang benar selalui mengikuti aksiomanya. Sederhananya, bisakah kita menemukan aksioma yang dilanjutkan dengan teorema yang dapat diterapkan pada mesin turing untuk memproses dan menemukan bilangan prima kembar lainnya dengan menggunakan hukum-hukum inferensi hanya dengan satu atau dua tahap. Mungkin bukan itu saja, kita bisa saja mengimput semua pernyataan yang benar dan menemukan padanannya. Pada kenyataan algoritma jenis ini tidak ada.
Mungkin kita mengasumsikan, kenapa tidak dibuat saja mesin yang berfungsi untuk mengevaluasi pemrosesan pada mesin turing? Inilah kontradiksinya. Kenapa kita butuh mesin lain untuk mengevaluasi suatu mesin yang fungsinya juga adalah evaluator? Tentu saja mesin seperti ini tidak pernah akan ada. Dengan kata lain tidak ada algoritma yang selalu dapat menentukan apakah suatu pernyataan selalu berasal dari aksioma yang jelas.
Masalah ketidakpastian seperti ini juga muncul dalam Fisika Kuantum tentang perbedaan energi dalam keadaan dasar dan dalam keadaan tereksitasi yang disebut denga celah spektral. Beberapa sistem memiliki celah spektral yang signifikan sedangkan sistem yang lain tanpa celah yang merupakan kontinum. Contohnya celah pada massa dengan partikel paling ringan, juga celah energi pada sistem elektron tubuh. Di tahun 2015 para penulis menggunakan ubin aperiodik mesin Turing kuantum dan menunjukkan bahwa bahan hipotetis ini menjadi celah jika dan hanya jika mesin berhenti. Kasus satu dimensi juga terbukti tidak dapat diputuskan pada tahun 2020 dengan membangun rantai qutrit yang berinteraksi dibagi menjadi blok yang memperoleh energi jika dan hanya jika mereka mewakili perhitungan penuh oleh mesin Turing, dan menunjukkan bahwa sistem ini menjadi gap jika dan hanya jika mesin tidak berhenti alias mengalami sirkular loop.
Banyak sekali masalah Undecidable problem yang dapat kita jadikan contoh selain yang dipaparkan di atas tentang betapa sangat tidak mungkin untuk mengurutkan algoritma pada sebuah sistem yang mengandung kompleksitas sehingga kita menemukan aksioma dasarnya. Kita mungkin dapat saja mendemonstrasikannya atau mengaplikasikannya pada teknologi. Tapi kita tidak tau kenapa itu terjadi.
*Penulis: Dosen UIN FAS Bengkulu dan aktif sebagai peneliti PUSKAPP.
======
Refrensi
Tulisan ini mengambil ide pada Video di Chanell Youtube Veritasium yang dipresentasikan oleh Dereck Muller. Refrensi-refrensi yang ditambahkan sebagai footnote untuk memudahkan pembaca melacak sumber-sumber rujukan yang digunakan.
Anda dapat mencoba Game ini di link berikut: https://playgameoflife.com/
McKee, Maggie. First proof that prime numbers pair up into infinity (Nature. 2013) https://hmn.wiki/id/Spectral_gap_(physics)
