Apakah permasalahan ini hanya untuk komputer?

Sewaktu Alan Turing memikirkan mesin Turing, ia tidak memikirkan mengenai memesan GoFood ataupun bermain PUBG. Alan Turing memikirkan mesin ini dengan tujuan untuk menyelesaikan masalah komputasi. Jadi mesin ini awalnya diciptakan untuk keperluan matematika.

Dalam sistem deduktif, kamu telah mempelajari bahwa ada sistem yang komplet dan yang tidak komplet. Sistem yang tidak komplet mengandung pernyataan yang tidak dapat ditentukan benar salahnya berdasarkan aksioma. Pernyataan-pernyataan seperti ini disebut pernyataan yang undecidable. Bukan kebetulan bahwa mesin Turing bisa juga bersifat undecidable.

Sebagian pernyataan dalam matematika dapat ditentukan benar salahnya menggunakan algoritma tertentu. Sewaktu kamu mengerjakan soal sistem deduktif untuk menentukan p(a, b), misalnya, kamu melakukan suatu prosedur untuk menarik kesimpulan dari aksioma hingga mencapai kesimpulan p(a, b) atau negasinya.

Kalau kamu berhasil menuliskan prosedur penarikan kesimpulannya (yang kita pelajari menggunakan diagram), berarti kebenaran p(a, b) dapat ditentukan berdasarkan sistem. Kasus semacam ini bisa diwakili mesin Turing yang berhasil menyelesaikan tugasnya dan berhenti. Untuk pernyataan matematika apapun yang dapat ditentukan kebenarannya, dapat dibuat mesin Turing untuk melakukan prosedur untuk menurunkan pernyataan tersebut dari aksiomanya. Sistem deduktif yang komplet memiliki padanan mesin Turing yang decidable.

Ada kalanya kamu berputar-putar dalam menarik kesimpulan, dan akhirnya kamu menyerah. Memang ternyata kamu tidak dapat menemukannya bukan karena kamu kurang pintar, tetapi karena memang pernyataan tersebut undecidable. Tindakan kamu berputar-putar mencari solusi inilah yang juga dilakukan mesin Turing yang mengerjakan sesuatu berulang-ulang tanpa berhenti. Bedanya, kamu langsung merasa ada hal yang salah, sementara mesin Turing tidak tahu hal itu karena tidak memiliki perasaan.

Tidak semua masalah dapat diselesaikan

Sampai di sini kita telah melihat bahwa tidak semua masalah bisa diselesaikan oleh komputer. Ada batas hal-hal yang di luar kemampuan komputer. Ini bukan hal yang baru, tentu saja, mengingat bahwa setiap hal yang diciptakan manusia pasti memiliki batas. Namun pertanyaan berikutnya adalah: Apakah otak manusia adalah mesin Turing?

Sampai hari ini pertanyaan ini belum terjawab. Seandainya otak manusia ekivalen dengan mesin Turing, berarti otak manusia dengan komputer pada prinsipnya sama. Bahan boleh beda, mekanisme boleh beda, tetapi prinsip kerjanya sama. Jika demikian, komputer tidak lebih terbatas dari manusia. Komputer dan manusia memiliki batas yang sama: Tidak dapat menyelesaikan masalah yang non-komputabel.

Kita masih belum tahu apakah otak manusia adalah mesin Turing. Namun kita bisa melihat sedikit banyak ada kemiripan dalam hal ini. Dalam tingkat individu, seorang manusia bisa terus menerus memikirkan mengapa ia diperlakukan tidak adil tanpa menemukan jawaban sampai akhirnya mengalami depresi hingga bunuh diri.

Termasuk permasalahan matematis

Dalam skala yang lebih luas, manusia bisa memikirkan persoalan matematis berabad-abad tanpa tahu apakah itu bisa dipecahkan atau tidak.

Pierre de Fermat menuliskan teorema terkenalnya pada abad ke-17. Teorema tersebut adalah, Untuk n bilangan asli lebih dari 2, maka tidak ada a, b, c bilangan bulat yang memenuhi a^n+b^n=c^n. Untuk n=2, persamaan tersebut menjadi teorema Pythagoras (a^2+b^2=c^2 yang memiliki penyelesaian bilangan bulat, yaitu (3,4,5), (5,11,12), dan seterusnya, yang kita sebut sebagai tripel Pythagoras. Namun untuk n lebih dari 2, hal tersebut tidak berlaku lagi.

Tidak ada seorangpun matematikawan yang berhasil membuktikan pernyataan Fermat tersebut, hingga pada tahun 1993 (akhir abad 20) Andrew Wiles membuktikan teorema tersebut. Jadi umat manusia perlu lebih dari 3 abad untuk membuktikan hal ini.

Sementara teorema Fermat terbukti benar, hipotesis kekontinuan dari Georg Cantor ternyata diketahui undecidable. Jadi sampai selamanya tidak ada seorangpun yang akan dapat membuktikan hipotesis tersebut menggunakan teori himpunan.

Dua contoh di atas adalah hal-hal yang sudah diketahui dengan jelas. Teorema Fermat ternyata dapat dibuktikan. Hipotesis kekontinuan ternyata tidak dapat dibuktikan. Namun hari ini masih banyak pernyataan matematika yang menunggu ada yang membuktikan. Sementara kita menunggu, kita tidak tahu apakah sebenarnya pernyataan tersebut memang tidak dapat dibuktikan, ataukah sebenarnya dapat tetapi belum berhasil dibuktikan?

Bagaimana kita melihat kenyataan ini?

Manusia kurang suka kenyataan bahwa ada memang ada permasalahan yang tidak dapat diselesaikan. Kita lebih suka mendengar para motivator berkata bahwa semua masalah selalu memiliki jalan keluar. Di satu sisi itu memberikan pengharapan kepada kita untuk terus bertahan dalam kesulitan. Ini adalah hal yang sangat penting. Namun di sisi lain, kita juga perlu menyadari bahwa ketika kita berhadapan dengan suatu masalah, kita tidak dapat membedakan: Apakah permasalahan ini memang tak dapat diselesaikan, atau belum dapat diselesaikan?

Jika belum dapat diselesaikan, saya perlu berusaha terus. Namun jika tidak dapat diselesaikan, tidak ada gunanya untuk maju terus. Ini bukan ajakan untuk menjadi pesimis, melainkan untuk secara realistis mengalokasikan pikiran dan tenaga kita untuk masalah yang lebih memerlukan perhatian kita. Dan kadang-kadang manusia perlu melakukan satu hal ini: menyerah.

Ini juga membuat kita lebih bijaksana dalam menyikapi teori konspirasi. Dalam sejarah kita melihat berbagai pertanyaan yang belum dapat dijawab. Karena kita tidak suka dengan pertanyaan yang tak dapat dijawab, kita membuat banyak asumsi untuk menjawab pertanyaan itu seolah-olah kita tahu semuanya, sehingga lahirlah sebuah teori konspirasi. Belum tentu sebuah teori konspirasi salah, tetapi kita perlu bijaksana untuk menyadari bahwa mungkin memang kita sekadar tidak punya informasi yang cukup untuk menalar jawaban dari pertanyaan tersebut.

Batasan seperti ini membuat kita perlu memikirkan kembali mengenai identitas manusia: Apakah kita pada prinsipnya sama dengan mesin?

Hubungan dengan kardinalitas himpunan dan teorema ketaklengkapan Godel

Dengan mengkombinasikan simbol, status, dan program yang berbeda-beda, kita dapat membuat mesin Turing yang berbeda-beda. Jumlahnya adalah tak berhingga.

Di sisi lain, karena mesin Turing bekerja dengan menggunakan simbol dan status yang diskrit dan jumlahnya terhingga (sementara panjang pitanya tak berhingga), maka banyaknya mesin Turing yang dapat dibuat adalah tak berhingga terhitung, yang setara dengan banyaknya bilangan asli ({\aleph}_0).

Karena jumlahnya {\aleph}_0, maka pertanyaan yang berada dalam domain {\aleph}_1 tak dapat dijawab oleh mesin Turing. Ini seperti bilangan real yang tak dapat dinomori dengan lengkap oleh bilangan asli. Selalu akan ada yang bersisa, walaupun kita mengatakan keduanya sama-sama tak berhingga.

Teorema ketaklengkapan Godel memberitahu kita bahwa jika aritmetika konsisten, tidak mungkin komplet. Aritmetika terdiri dari simbol yang terbatas, yang bisa dirangkai menjadi rangkaian simbol yang tak terbatas. Setiap pembuktian aritmetika dapat diwakili oleh sebuah mesin Turing yang decidable. Karena itu, jika mesin Turing undecidable, berarti tidak ada pembuktian bagi pernyataan tersebut.

Permasalahan dalam mesin Turing, yaitu halting problem, setara dengan permasalahan self-reference Godel.

Berikutnya: Batas logika manusia