Indirekter Beweis: Falls das Halteproblem doch algorithmisch lösbar ist:
Dann definieren wir das Programm
H : x
minipage0.8
lp0.8falls &P_x(x)
(RechnungdesProgrammsmitNummerx
fürEingabex
Das Programm H hat auch eine Nummer, diese sei n.
Also H = Pn.
Hält H(n)?
Wegen der Fallunterscheidung gilt
H(n) hält H(n) = 0
Pn(n) hält nicht
H(n) hält nicht!
Das ist ein Widerspruch, d. h. (wenigstens) eine Annahme war falsch:
Die Funktion H ist völlig korrekt definiert, aber es gibt keinen Algorithmus, der H berechnet.