Registermaschine/Haltende Programme/Aufzählbar/Fakt/Beweis

Aus Wikiversity
Beweis

Die Idee für ein algorithmisches Aufzählverfahren geht so: Zu jeder natürlichen Zahl berechnet man sämtliche Programme mit . Jedes dieser Programme lässt man, angesetzt auf , Schritte (also Befehlszeilenwechsel) lang laufen. Wenn anhält, so druckt man aus. Wenn all diese Programme Schritte gelaufen sind, so erhöht man auf . Da ein jedes anhaltendes Programm nach einer gewissen Laufzeit anhält, wird es bei als anhaltendes Programm erfasst.