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.