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.

Beispiele

Die folgenden Beispiele brauchen wir auch für später.

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

Ähnlich kann man prüfen, ob $R_i > R_j$. Addition geht mit einer einfachen Schleife:

   Start: if R[1] == 0 then goto Done
   R[0]++
   R[1]--
   goto Start

   Done: End

Addition geht durch wiederholte Inkrementierung

   Start: if R[1] == 0 then goto Done
   R[0]++
   R[1]--
   goto Start
   
   Done: End

Subtraktion analog, wobei man definiert, dass $a-b=0$ für $a<b$

   Start: if R[1] == 0 then goto Done
   R[0]--
   R[1]--
   goto Start
   
   Done: End

Wir können nun die Kurzschreibweisen R[i]+=R[j] und R[i]-=R[j] einführen, um vom Register R[i] den Wert von R[j] abzuziehen. Damit können wir zum Beispiel Multiplikation definieren

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

Division die den Rest verwirft können wir analog definieren mittels wiederholter Subtraktion

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

Turingmaschinen sind Register-Mächtig

Dass man jede Registermaschine auch als Turingmaschine umbauen kann, sieht man leicht: Haben wir $n$ Register, so können wir diese einfach eine $n$-Band-Turingmaschine ersetzen, auf der wir die Zahlen unal speichern, und ein bisschen Logik einbauen für den Nullfall.

Registermaschinen sind Turing-Mächtig

Wir zeigen, dass Registermaschinen äquivalent zu Zweikellerautomaten sind. Damit ist auch gezeigt, dass sie Turingmächtig sind.

Sei ein Alphabet ${\cal L}=\{a_1,\ldots,a_n\}$ gegeben, und sei $g(a_i):=i$. Dem Wort $a_{k_1}\ldots a_{k_q}$ ordnen wir eineindeutig die Zahl $\sum\limits_{i=0}^{q-1} n^i \cdot g(a_{k_i})$ zu, dem Wort $\varepsilon$ die Zahl $0$, und nennen diese Funktion auch $g$. Offensichtlich ist damit $g(a_j v) = j + n\cdot v$.