Die Universelle Registermaschine

Bei einem echten Computer sind auch die Programme selber Daten. Das macht auch Sinn: Man möchte nicht jedes mal die Maschine neu verlöten müssen, wenn man etwas anderes ausführen will.

Ähnliches kann man mit Registermaschinen machen: Man kann eine Registermaschine angeben, die in Zahlen codierte andere Registermaschinen "simuliert".

Es gibt viele Methoden, wie man das bewerkstelligen kann. Zum Verständnis reicht es, sich die generelle Methodik anzueignen.

Zahlenfolgen

Es ist möglich, mittels der cantorschen Paarungsfunktion, zwei natürliche Zahlen bijektiv auf eine natürliche Zahl abzubilden. Wir definieren $\pi(k_1, k_2) = \frac{1}{2}(k_1+k_2)(k_1+k_2+1)+k_2$.

TODO

Um nun eine endliche Folge von Zahlen zu codieren, können wir "schachteln": $a_1,\ldots,a_n$ wird codiert zu $\pi(a_1, \pi(a_2, \ldots))$. Alle Operationen, die wir brauchen, um ein $a_i$ aus solch einer codierten Folge auszulesen, sind in Registermaschinen implementierbar.

Programme

Die Programme selbst kann man nun als Folge von Befehlen codieren: Wir codieren R[i]++ als $\pi(0,i)$ und R[i]-- als $\pi(1,i)$. Statt Sprungmarken benutzen wir jetzt den Index des Befehls in der codierten folge, und codieren goto i mit $\pi(2,i)$ und if R[i]==0 then goto j mit $\pi(3,\pi(i, j))$. End codieren wir mit $\pi(4,0)$. Damit hat jeder Befehl einen eindeutigen Code. Das Programm codieren wir jetzt einfach als Folge dieser codes.

Programmzustände

Der Zustand eines Programms besteht aus dem aktuellen Index $i$ des Befehls, und dem Inhalt von dessen Registern. Wir können den gesamten Zustand also einfach speichern als $\pi(i, \pi(R_1, \pi(R_2, \ldots)))$.

Ausführung

Enthalte nun $R_0$ den Programmcode, und $R_1$ den aktuellen Zustand des Programms. Einen Schritt vorangehen tun wir so:

• Sei $c = \left<R_1\right>_0$ das erste Element des Programmzustands. Es sagt uns, bei welchem Befehl von $R_0$ wir sind. Sei $d = \left<R_0\right>_c$.
  • Ist $\pi_1(d) = 0$, so sei $k = \pi_2(d)+1$. Sei weiterhin $r = \left<R_1\right>_k$. $r$ ist der Wert des $k-1$-ten Registers in dem simulierten Programm. Wir ersetzen es nun in $R_1$ durch $r+1$, und ersetzen außerdem $\left<R_1\right>_0$ durch $\left<R_1\right>_0+1$, damit das Programm zur nächsten Anweisung weiterläuft.
  • Analog gehen wir vor, wenn $\pi_1(d)=1$ ist, nur dass wir vom codierten Register $1$ abziehen.
  • Ist $\pi_1(d)=2$, so sei $i = \pi_2(d)$, und wir setzen $\left<R_1\right>_0$ auf $i$.
  • Ist $\pi_1(d)=3$, so sei $i = \pi_1(\pi_2(d))$ und $j = \pi_2(\pi_2(d))$. Wir überprüfen, ob $\left<R_1\right>_{i+1} = 0$ ist. Falls ja, setzen wir $\left<R_1\right>_0$ auf $j$. Andernfalls setzen wir $\left<R_1\right>_0$ auf $\left<R_1\right>_0+1$.
  • Ist $\pi_1(d)=4$, sind wir bei einer End-Anweisung angekommen. In $R_1$ sind nun alle Register codiert, die potentiell Endergebnisse haben, und wir können sie, je nach dem wie wir wollen, auslesen.

Alle Operationen sind, wenn auch aufwendig, mit Registermaschinen machbar. Somit ist es möglich, eine universelle Registermaschine zu schreiben.