Halteproblem/Registermaschine/Unentscheidbarkeit/Fakt/Beweis
Wir nehmen an, dass es ein Registerprogramm gibt, dass die in Frage stehende Menge entscheidet, also stets anhält und angesetzt auf eine Zahl genau dann die Ausgabe liefert, wenn für ein Programm ist (also wenn die Programmnummer eines Registerprogramms ist) und wenn dieses Programm , angesetzt auf , anhält. Wir entwickeln aus ein Programm , das genau dann die Ausgabe hat, wenn für ein Programm ist und wenn , angesetzt auf , anhält. Dies ergibt einen Widerspruch zu Fakt.
Dazu wird folgendermaßen konstruiert: Wenn keine Programmnummer ist, so hält das Programm mit der Ausgabe an (hier gibt es also keinen Unterschied zu ). Wenn eine Programmnummer ist, so wird das Programm aufgestellt, das dem Programm die -fache Inkrementierung des ersten Registers voranstellt und dessen (in einem bedingten Sprungbefehl in einer Befehlszeile) adressierte Befehlszeilennummern sich um erhöhen. Für die Programmnummer wird nun mittels überprüft, welche Ausgabe , angesetzt auf , besitzt. Aufgrund der Konstruktion von besitzt bei Eingabe die Ausgabe genau dann, wenn bei Eingabe von die Ausgabe besitzt.
