Halting Problem dengan Pembuktian Diagonal

Ketidakmampuan komputer menjawab halting problem juga dapat dibuktikan dengan pembuktian diagonal seperti yang Georg Cantor lakukan untuk bilangan real dalam interval (0, 1).

Setiap program dapat dituliskan sebagai bilangan asli. Sebagai contoh, fungsi Python berikut ini:

def f(x):
  return x * x

Akan mengerjakan hal yang diwakili oleh rangkaian bit berikut:

100010011111100000001111101011111100011111000011

Yang merupakan sebuah bilangan biner yang sangat besar, yang nilainya dalam heksadesimal adalah 0x89F80FAFC7C3, atau dalam desimal 151698508072899. Jadi program di atas sebenarnya sama dengan bilangan asli 151698508072899.

Ini seharusnya mengingatkanmu pada bilangan Godel. Bilangan Godel adalah bilangan asli yang mewakili teorema, sementara sekarang kita menggunakan bilangan asli untuk mewakili program.

Selain program, input juga dapat dinyatakan sebagai bilangan asli. Sebagai contoh, kata streptococcus merupakan barisan bit sebagai berikut:

01110011 01110100 01110010 01100101 01110000 01110100 01101111 01100011 01101111 01100011 01100011 01110101 01110011 

Yang adalah bilangan biner yang nilainya adalah 115 116 114 101 112 116 111 99 111 99 99 117 115 dalam desimal.

Ada tak berhingga program yang mungkin dibuat. Karena setiap program pada dasarnya adalah bilangan, maka banyaknya program yang mungkin dibuat adalah sebanyak bilangan asli. Dengan kata lain, kardinalitas himpunan semua program yang mungkin dibuat adalah \aleph_0.

Demikian juga dengan input.

Mari kita berpura-pura mendaftarkan semua program yang mungkin dibuat ke arah bawah, sementara input yang diwakili bilangan, dapat kita daftarkan ke arah kanan.

Kemudian setiap sel dalam tabel mewakili apakah program P dengan input i akan berhenti atau tidak. Tanda centang berarti program tersebut akan berhenti pada input tersebut.

Sekarang kita mengasumsikan bahwa daftar di ini sudah mencakup semua program yang mungkin dibuat.

Namun dengan mengambil diagonal P_D, lalu membaliknya menjadi P_{D'}, kita akan mendapati bahwa P_{D'} pasti belum terdaftar di atasnya.

Dengan demikian, asumsi awal kita bahwa semua program sudah terdaftar ternyata salah. Artinya ada program yang di luar daftar kita. Sementara daftar kita dibuat menggunakan bilangan asli, berarti daftar yang lengkap akan lebih besar dari bilangan asli.

Kesimpulan

Sebelumnya kita telah mengetahui bahwa banyaknya program yang dapat kita buat adalah sebanyak bilangan asli (\aleph_0). Namun karena ternyata ada kondisi yang di luar daftar yang mungkin kita buat, berarti program yang dapat memeriksa apakah program lain berhenti atau tidak tidaklah dapat dibuat.

Berikutnya: Apakah permasalahan ini hanya untuk komputer?