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).

Pertanyaan dasarnya adalah sebagai berikut:

Adakah program yang dapat memeriksa sembarang program dengan sembarang input akan berhenti?

Kita akan membuktikan secara tak langsung dengan kontradiksi. Hipotesis nolnya adalah:

Kita belum tahu apakah program itu benar-benar ada. Tapi kita akan namakan program itu sebagai \text{ncek}(p,i) dengan p adalah bilangan Gödel untuk sebuah program P (P kapital), dan i adalah input yang diberikan untuk dikerjakan oleh program tersebut.

Karena \text{ncek} selalu dapat menentukan jawabannya, berarti \text{ncek} adalah program yang decidable.

Kemudian kita modifikasi sedikit program \text{ncek} ini menjadi semidecidable, yaitu berhenti dan menjawab ya jika P(i) akan berhenti, dan tidak berhenti (yang berarti tidak menjawab) jika P(i) tidak bisa berhenti.

Dalam bentuk program Python (bukan program aktual), bentuknya kira-kira akan seperti ini:

def ncek'(p,i):
  if P(I) decidable:
    return 'Ya'
  else:
    while True:
      pass

Yang dibaca: Apakah P(i) akan berhenti? Jika ya maka berhenti dan laporkan ya, jika tidak maka jangan berhenti juga.

Karena program P bisa sangat banyak, kita akan mendaftarkannya sebagai P_1, P_2, P_3, dan seterusnya. Karena input yang diberikan adalah bilangan Gödel untuk masing-masing program, maka inputnya adalah p_1, p_2, p_3, dan seterusnya.

Setiap sel dalam tabel akan mewakili kondisi dari \text{ncek}'(p_i,p_j).

Kemudian kita akan melakukan sesuatu yang nakal: Alih-alih mengerjakan \text{ncek}'(p,i) untuk menguji P(i), kita akan menggunakan nilai p sendiri sebagai input.

Hal nakal yang kita lakukan ini tidak lain adalah mengambil diagonal dari tabel.

Jika \text{ncek}' menjawab tidak, berarti ia berhenti. Tandanya adalah · (titik). Jika \text{ncek}' tidak menjawab karena tidak pernah berhenti, tandanya adalah ∞.

Jadi apakah arti D ini? Setiap tanda dalam D mewakili \text{ncek}'(p_i,p_i), yaitu keberhentian P(p) alias keberhentian program yang diberi input bilangan Godel dirinya sendiri.

atau

Kemudian kita akan membalik diagonalnya menjadi D'.

D' sendiri merupakan program yang terdapat dalam daftar di atas, karena daftar tersebut sudah diasumsikan mengandung semua program. Juga D' memiliki bilangan Gödel d'. Namun jika demikian, berarti akan ada satu sel perpotongan antara baris D' dengan kolom d' yang merupakan keberhentian dari D'(d').

Apa yang akan terjadi berikutnya? Kondisi D'(d') dapat merupakan salah satu dari berhenti maupun tidak berhenti, sesuai definisi \text{ncek}'.

Jika D'(d') tidak berhenti

Jika D'(d') tidak berhenti, maka D'(d') sesuai instruksi justru akan berhenti.

Jika D'(d') akan berhenti

Jika D'(d') akan berhenti, maka sesuai instruksi, D'(d') justru tidak berhenti.

Kesimpulan untuk D'(d')

Karena baik berhenti maupun tidak berhenti mengharuskan D' untuk melakukan kebalikannya, ini menimbulkan kontradiksi, sehingga D' tidak dapat bekerja sesuai instruksinya. Penyebabnya tidak lain adalah hipotesis awal kita:

Sehingga kita harus simpulkan bahwa bahwa H0 salah, dan menerima hipotesis alternatifnya.

Konsekuensinya

Program seperti \text{ncek} ini adalah program yang sangat berguna karena kita jadi tidak harus menunggu sangat lama untuk mulai curiga bahwa suatu program tidak akan pernah berhenti. Cukup bertanya pada \text{ncek} apakah program P akan berhenti pada input I, dan \text{ncek} akan memberitahu kita.

Namun hasil pembuktian ini menunjukkan bahwa program seperti itu tidak mungkin dibuat.

Ini juga dapat kita tarik lebih luas lagi artinya. Berarti mungkin akan ada jenis program yang kita pikir cukup masuk akal untuk dibuat, ternyata tidak dapat diwujudkan.

Berikutnya: Apakah permasalahan ini hanya untuk komputer?