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 manchmal $R_{\mbox{in}}$ und $R_{\mbox{out}}$ oder Ähnliches (wie genau man die Register bezeichnet ist ja auch nicht so wichtig).

Es haben sich zwei verschiedene Darstellungen für Registermaschinen eingebürgert, die eine als Graph mit Übergangskanten, die andere als Programmcode – ähnlich zu Programmiersprachen – mit Sprunganweisungen. Wir schauen uns erst die Darstellung mit Sprunganweisungen an.

Es gibt für jedes Register R[i] die Programmbefehle R[i]++ und R[i]--. R[i]++ erhöht das Register 1, R[i]-- senkt es um $1$ ab falls es $>0$ ist, und lässt es gleich, falls es $0$ ist. Weiterhin gibt es Anweisungen if R[i]==0 then goto A, wobei A eine Sprungmarke ist. Die Anweisung springt zur betreffenden Sprungmarke, je nach dem, ob das angegebene Register $0$ ist, oder nicht. Sprungmarken notiert man vor dem Befehl, mit einem Doppelpunkt dahinter. Weiterhin gibt es den befehl End, der das Programm beendet (natürlich könnte man diesen Befehl auch weglassen, und einfach vereinbaren, dass das Programm endet, sobald es hinter die letzte Programmzeile läuft, alles äquivalente Definitionen), und ein unconditionalles goto, das immer springt.

Der folgende Code überprüft, ob $R_0 \ge R_1$, und falls ja, setzt er $R_2$ auf $1$:

   Start: if R[1]==0 then goto Yes
   if R[0] == 0 then goto No
   R[1]--
   R[0]--
   goto Start
   
   No: End
   
   Yes: R[2]++
   End