Algorithmisch unlösbare Probleme (3)

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

Dann definieren wir das Programm $H: x \mapsto$ falls $P_x(x)$ (Das Programm mit Nummer $x$, gestartet mit Eingabe $x$) hält, dann irgendeine nicht haltende Rechnung (Schleife), sonst 0.

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: $H$ ist gar nicht programmierbar!