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).

Wir werden sie als Programmcode – ähnlich zu Programmiersprachen – mit Sprunganweisungen darstellen.

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$. Wir können also die Kurzschreibweise if R_i > R_j then goto A einführen, ohne dass das resultierende Maschinenmodell stärker würde.

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

TODO Das ist falsch, weil R[1] immer dekrementiert wird. Man will R[1] kopieren und dann den kopierten Wert immer addieren. Selbes für Division.

   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: if R[1] > R[0] then goto Done
   R[0] -= R[1]
   R[2]++
   goto Start
   
   Done: End

Damit können wir auch den Rest der Division berechnen, da dieser einfach a - b * a/b ist, wobei / die Division ohne Rest ist.

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 g(v)$.

Das heißt, das erste Zeichen unseres codierten Wortes kriegen wir heraus, indem wir den Modulus des Codes bezüglich $n$ berechnen. Ein weiteres Zeichen anhängen können wir, indem wir den code mit $n$ multiplizieren und das Zeichen aufaddieren. Beide Operationen sind, wie man an obigen Beispielen sieht, in polynomieller Zeit mit Registermaschinen möglich.

Vergleiche sind ebenfalls möglich. Damit ist es offensichtlich möglich, einen Zweikellerautomaten zu simulieren.