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)\le 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(c(P),\ell )$  als anhaltendes Programm erfasst.

Zur bewiesenen Aussage