Permasalahan dan program

Apakah untuk semua masalah dapat dibuat program untuk menjawabnya? Sekilas tampaknya bisa. Betul begitu?

Kita akan memeriksa hal ini. Kita akan memulai dengan mengasumsikan hipotesis nol terlebih dahulu:

Namun istilah masalah di sini dapat bermakna terlalu luas. Kita akan membatasinya pada masalah penentuan, yaitu masalah berupa pertanyaan yang dapat dijawab sebagai ya atau tidak.

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. Hasilnya bisa True (jika benar genap), atau False (jika bukan genap).

  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. Spasi kita buang sebanyak mungkin selama tidak mengubah makna. 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. Berarti input program ini bukan bilangan, melainkan rangkaian huruf. Dalam Python kita menuliskan inputnya sebagai rangkaian huruf (disebut sebagai string atau untai) di antara tanda kutip. Untuk keperluan pembuktian, kita perlu konversi input ini terlebih dahulu menjadi bilangan.

  return len(x) % 2 == 0

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.

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.

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 masalah penentuan.

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 sekalipun ada tak berhingga program yang mungkin kita buat, 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, setidaknya ketika manusia dalam keadaan sadar.

Masalah yang kita bicarakan di sini barulah masalah penentuan, yaitu masalah-masalah yang berupa pertanyaan yang selalu dapat dijawab ya atau tidak. Masih ada permasalahan lain yang lebih rumit.

Setidaknya, karena kita telah membuktikan bahwa tidak semua masalah penentuan (yang adalah bagian dari masalah yang lebih umum) dapat dibuat programnya, berarti secara umum kita tidak dapat menyelesaikan semua masalah. Akan ada jauh lebih banyak masalah di dunia yang tidak sanggup kita selesaikan.

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 yang dilakukan 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. Namun tidak ada yang dapat memastikan hal tersebut.

Berikutnya: Halting Problem