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

Aus Wikiversity
Beweis

Wir nehmen an, dass es ein Programm 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 ab, indem wir den letzten Befehl von (also den Haltebefehl) durch den Programmabschnitt (mit der relativen Nummerierung und einem neuen Register )

  1. Gehe zu
  2. Halte an

ersetzen. Dies bedeutet, dass das Programm genau dann in eine Endlosschleife hineinkommt und nicht anhält, wenn das Programm die Ausgabe hat. Daher gilt die Äquivalenz, dass ein Programm bei Eingabe der eigenen Programmnummer genau dann anhält, wenn bei Eingabe der Programmnummer von nicht anhält. Diese Äquivalenz ergibt bei Anwendung auf das Programm einen Widerspruch.