Permasalahan dan program

Apakah semua masalah yang decidable dapat dibuat program untuk menjawabnya? Sekilas sepertinya seperti itu, bukan?

Baiklah, kita akan membuat hipotesis nol kita:

Setiap program dapat dituliskan sebagai bilangan asli. Sebagai contoh, fungsi genapkah yang ditulis dalam Python berikut ini akan menentukan apakah bilangan asli yang diberikan adalah genap atau bukan.

def genapkah(x):
  return x % 2 == 0

Dalam memori komputer, program di atas disimpan sebagai rangkaian bit yang jika diartikan sebagai bilangan nilanya adalah sangat besar, yaitu 9\times 10^{31} atau sembilan noniliun.

Dengan menganggap bahwa inputnya pasti diwakili oleh variabel x, maka bagian penting program tersebut sebenarnya hanyalah return x%2==0. Bagian ini yang akan kita terjemahkan sebagai bilangan menggunakan pengkodean ASCII atau UTF-8.

Masih ingat bilangan Gödel? Dalam pembuktian teorema ketaklengkapan, bilangan Gödel adalah bilangan asli yang mewakili teorema. Kali ini kita menggunakan bilangan Gödel juga tetapi untuk mewakili program.

Selain program, input juga perlu dinyatakan sebagai bilangan asli. Karena input untuk program genapkah adalah bilangan asli, maka kita tidak perlu melakukan konversi.

Berbeda dengan program genapkah, program berikut ini akan menentukan apakah banyaknya huruf dalam sebuah untaian adalah genap.

def genapkahBanyakHurufnya(x):
  return len(x) % 2 == 0

Berarti input program ini bukan bilangan, melainkan rangkaian huruf, sehingga kita perlu konversi terlebih dahulu menjadi bilangan.

Sebagai contoh, kata streptococcus merupakan barisan bit sebagai berikut, yang nilainya dalam desimal adalah 9.147.277.246.856.551.059.006.056.265.075.

Karena setiap program dapat dikonversi ke dalam bilangan asli, sementara ada tak berhingga program yang mungkin diciptakan, berarti kardinalitas himpunan semua program yang mungkin dibuat adalah \aleph_0. Artinya semua program dapat kita nomori dengan 1, 2, 3, dan seterusnya. Kita akan menyebut program-program itu sebagai P₁, P₂, P₃, dan seterusnya.

Input juga dapat dikonversi ke dalam bilangan asli. Alih-alih mulai dari 1, kita mengizinkan input nol, sehingga kita dapat mendaftar input sebagai bilangan 0, 1, 2, 3, dan seterusnya.

Sekarang mari kita anggap bahwa P_1(0)=ya, P_1(1)=ya, P_1(3)=tidak, P_2(1)=tidak, dan seterusnya sesuai tabel di bawah ini. Artinya program P_1 akan menjawab ya untuk input 0, menjawab ya untuk input 1, dan menjawab tidak untuk input 3. Lalu P_2 akan menjawab tidak untuk input 1.

Dengan mengambil diagonalnya, kita akan dapat mengandaikan ada program P_D yang menjawab ya untuk input 0, menjawab tidak untuk input 1, menjawab ya lagi untuk input 2, dan seterusnya.

Setelah itu, kita mengandaikan ada program P_{D'} yang selalu menjawab kebalikan dari P_D.

Program P_{D'} ini masih akan menjawab pertanyaan ya maupun tidak untuk semua bilangan asli, sehingga kita dapat mengatakan bahwa P_{D'} ini menjawab sebuah permasalahan yang decidable.

Namun pada saat yang sama, menurut sifat diagonal, program P_{D'} pastilah belum terdaftar sebagai salah satu dari program-program di atas.

Jadi ada kontradiksi di sini:

Karena kontradiksi ini dihasilkan oleh hipotesis awal kita, maka hipotesis awal tersebut salah, dan kita harus menerima yang sebaliknya.

Jadi ternyata, program yang dapat kita buat, sekalipun jumlahnya tak berhingga, tetap tak dapat menjawab setiap permasalahan penentuan yang dapat kita tanyakan. Banyaknya masalah jauh lebih banyak daripada banyaknya program yang dapat dibuat untuk menjawab masalah tersebut.

Pembuktian ini menggunakan diagonalisasi Cantor, sehingga kita juga dapat memperoleh kardinalitas masalah \mathfrak{c}.

Apakah manusia dapat menyelesaikan semua masalah di dunia?

Perhatikan bahwa setiap kali kita berpikir untuk menjawab permasalahan tertentu, kita berpikir dalam langkah-langkah yang diskret dan berhingga. Berarti manusia sebenarnya berpikir secara algoritmik, setara dengan program komputer.

Dengan demikian, pastilah ada jauh lebih banyak masalah di dunia yang tidak sanggup kita selesaikan.

Perhatikan bahwa masalah yang kita bicarakan di sini barulah masalah yang decidable, yaitu masalah-masalah yang berupa pertanyaan yang selalu dapat dijawab ya atau tidak. Masih ada permasalahan lain yang lebih rumit, yaitu masalah-masalah yang semi-decidable maupun undecidable.

Mungkinkah menyelesaikan masalah dengan cara yang lebih tinggi?

Kemampuan komputasi manusia ketika berusaha memikirkan masalah secara sadar terbatas pada komputasi algoritmik yang setara dengan program maupun mesin Turing. Kita dapat menyebut bahwa kemampuan komputasi manusia secara sadar berada dalam level \aleph_0.

Saya tidak tahu apakah manusia memiliki kemampuan komputasi di atas mesin Turing. Jika manusia memiliki kemampuan komputasi yang lebih tinggi dari \aleph_0, kemampuan itu setidaknya tidak dapat diakses secara sadar. Mungkin ketika kamu tiba-tiba tersadar, tercerahkan, dan mengatakan, Aha! untuk suatu masalah yang selama ini kamu tidak menemukan jawabannya, itu adalah komputasi di atas \aleph_0, tetapi tidak ada yang dapat memastikan hal tersebut.

Berikutnya: Halting Problem