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(3,0)$. Damit hat jeder Befehl einen eindeutigen Code. Das Programm codieren wir jetzt einfach als Folge dieser codes.