Halteproblem/Registermaschine/Eingabe der Programmnummer/Unentscheidbarkeit/Fakt/Beweis

Beweis

Wir nehmen an, dass es ein Programm ${}U$ gibt, das diese Menge entscheidet (der erste Teilaspekt, ob es sich überhaupt um ein valides Programm handelt, ist entscheidbar). Wir ändern dieses Programm zu einem Programm ${}U^{\prime }$ ab, indem wir den letzten Befehl von ${}U$ (also den Haltebefehl) durch den Programmabschnitt (mit der relativen Nummerierung und einem neuen Register ${}R_{i}$)

1. ${}C(1,3)$
2. Gehe zu ${}5$
3. ${}i+$
4. ${}C(1,3)$
5. Halte an

ersetzen. Dies bedeutet, dass das Programm ${}U'$ genau dann in eine Endlosschleife hineinkommt und nicht anhält, wenn das Programm ${}U$ die Ausgabe ${}0$ hat. Daher gilt die Äquivalenz, dass ein Programm ${}P$ bei Eingabe der eigenen Programmnummer ${}c(P)$ genau dann anhält, wenn ${}U'$ bei Eingabe der Programmnummer ${}c(P)$ von ${}P$ nicht anhält. Diese Äquivalenz ergibt bei Anwendung auf das Programm ${}P=U'$ einen Widerspruch.

Zur bewiesenen Aussage