Die Universelle Registermaschine: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) |
Css (Diskussion | Beiträge) |
||
| Zeile 11: | Zeile 11: | ||
'''TODO''' | '''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. | + | 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. |
[[Kategorie:TODO]] | [[Kategorie:TODO]] | ||
Version vom 14. August 2018, 19:18 Uhr
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.
