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

Beweis

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

Zur bewiesenen Aussage