Registermaschinen

Ein Maschinenmodell das näher an dem ist, was moderne Computer tun, sind Registermaschinen.

Statt einem Speicherband hat man mehrere Register, das sind Zahlenvariablen, die natürliche Zahlen beinhalten können, und es gibt Befehle zum Inkrementieren, Dekrementieren, auf null prüfen, und Sprunganweisungen.

Wir nennen diese Register $R_0, R_1, \ldots$. Üblicherweise nutzen wir ein Register als Eingabe und ein Register als Ausgabe, der Übersichtlichkeit nennen wir sie $R_{\mbox{in}}$ und $R_{\mbox{out}}$.