Algorithmisch unlösbare Probleme (4)

Indirekter Beweis: Falls das Halteproblem doch algorithmisch lösbar ist:

Dann definieren wir das Programm

H : x $\mapsto$ $\left\{\vphantom{}\right.$minipage0.8 lp0.8falls &P_x(x) (RechnungdesProgrammsmitNummerx fürEingabex $) \textbf{hält}, \\ \textbf{dann} & irgendeine nicht haltende Rechnung (Schle... ...sonst} & ein haltende Rechung (return 0). \end{tabular}\end{minipage} \right.$

Das Programm H hat auch eine Nummer, diese sei n.

Also H = P_n.

Hält H(n)?

Wegen der Fallunterscheidung gilt

H(n) hält $\iff$ H(n) = 0 $\iff$ P_n(n) hält nicht $\iff$ 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.