8.4 Turing-Maschinen codieren

Wir haben mit der Turingmaschine ein einfaches aber doch sehr mächtiges Modell einer Rechenmaschine kennengelernt. Sie haben vielleicht mittlerweile - auch durch Ihre Programmiererfahrung - das Gefühl, das man im Prinzip alles, was man überhaupt programmieren kann, auch auf einer Turingmaschine hinkriegt. Versetzen Sie sich nun in die Lage der Menschen vor ungefähr 100 Jahren. Damals gab es durchaus Rechenmaschinen. Maschinen zum Addieren und sogar zum Multiplizieren gibt es schon seit dem 17. Jahrhunder (Wikipedia: Mechanical calculator). Leider musste man für jede Aufgabe eine neue Maschine erfinden und auch bauen. Zahlen addieren? Maschine bauen. Multiplizieren? Neue Maschine bauen. Verschlüsselung brechen? Neue Maschine bauen. Und so weiter.

Die Idee einer programmierbaren Maschine, die erstmals circa 1834 mit Charles Babbage aufkam, ist, dass man neben den Eingabedaten (z.B. die zu multiplizierenden Zahlen) auch die Rechenvorschrift (das Programm) als Eingabe übergibt. Hätte man so eine Maschine, dann müsste man nicht für jede neue Aufgabe eine neue Maschine entwerfen; man könnte eine Maschine bauen und sie für die jeweilige Aufgabe programmieren, indem ihr auf einem separaten Eingabeband die Rechenvorschrift überreicht. Von heute aus gesehen ist diese Idee nicht mehr allzu überraschend, weil diese Maschinen überall anzutreffen sind. Damals aber war es revolutionär. Um dies, zumindest auf dem Papier, in die Realität zu übersetzen, müssen wir zwei Fragen beantworten.

1. Wie können wir eine Rechenvorschrift (d.h. ein Programm) so codifizieren, dass wir es im Prinzip als eine Zeichenkette aufschreiben und einer Maschine übergeben können?
2. Welche Maschine könnte so eine Rechenvorschrift lesen und sie an gegebenen Eingabedaten dann auch ausführen?

Es stellt sich heraus, dass wir beide Antworten (beinahe) schon kennen. Eine beliebige Rechenvorschrift können wir, da sind wir uns mittlerweile recht sicher, als Turingmaschine $M$ implementieren. Diese können wir über einem Alphabet codieren und erhalten ein Wort $\text{enc}(M)$. Wie tun wir das? Nun ja, auf turingmachinesimulator.com haben wir das bereits getan: eine Turingmaschine mit Alphabet $\mathrm{\Sigma }$ können wir dort als String über dem Alphabet $$\begin{array}{r}\mathrm{\Sigma }\cup \{a,\dots ,z,A\dots ,Z,0,\dots ,9\}\cup \{\mathtt{\text{<}},\mathtt{\text{-}},\mathtt{\text{>}},\mathtt{\text{,}},\mathtt{\text{\_}},\mathtt{\text{n}},\dots \}\end{array}$$ codieren. Codierung ist im Prinzip kein Problem, wir werden aber ein paar Subtilitäten ansprechen.

Punkt 2 ist schwieriger. Können wir eine Maschine bauen, die als eingabe (1) die Codierung $\text{enc}(M)$ einer Turingmaschine und (2) ein Eingabewort $w\in {\mathrm{\Sigma }}^{\ast }$ entgegennimmt und dann die Berechnung $M(x)$ simuliert bzw. zu dem Ergebnis gelangt, zu dem auch $M(x)$ gelangen würde? Die Programmierer von turingmachinesimulator.com haben dies offensichtlich geschafft: sie haben eine Maschine "gebaut" (also wohl einen Server gemietet und eine Webseite mit viel Javascript programmiert), der eine Turingmaschine in einer spezifischen Codierung und ein Eingabewort einliest und dann diese simuliert.

In diesem Teilkapitel werden wir sehen, wie wir eine Turingmaschine $M$ über einem fixen, nicht von $M$ abhängigen Alphabet codieren können. Im nächsten Teilkapitel werden wir uns überlegen, wie man einen Turingmaschinen-Simulator selbst als Turingmaschine implementieren kann. Also eine Turingmaschine $U$, die als Input Wörter der Form $$\begin{array}{r}c\mathrm{\#}x\end{array}$$ entgegennimmt und dann

1. ablehnt, falls $c$ keine gültige Codierung einer Turingmaschine $M$ ist,
2. ansonsten, falls also $c=\text{enc}(M)$, dann
   1. akzeptiert falls $M(x)$ akzeptiert;
   2. ablehnt, falls $M(x)$ ablehnt
   3. nicht terminiert, falls $M(x)$ nicht terminiert.

Falls wir bei $M$ nicht nur an Akzeptieren / Ablehnen interessiert sind, sondern am Ergebnis der Berechnung, dann hätten wir gerne, dass $U(\text{enc}(M)\mathrm{\#}x)$ am Ende den gleichen Bandinhalt hat wie $M(x)$ am Ende; hierbei gibt es allerdings eine Schwierigkeit mit den Details der Codierung, die wir gleich ansprechen werden.

Die Codierung

Zuerst müssen wir uns auf ein Eingabealphabet $\mathrm{\Sigma }$ einigen. Im Ernstfall genügt immer $\mathrm{\Sigma }=\{0,1\}$, allerdings gibt es keinen Grund, für die Definitionen nicht allgemeine endliche Alphabete $\mathrm{\Sigma }$ zuzulassen. Wir wollen nun ein Codierungsalphabet $\mathrm{\Lambda }$ und eine Codierungsfunktion $\text{enc}$, so dass $$\begin{array}{r}\text{enc}(M)\in {\mathrm{\Lambda }}^{\ast }\end{array}$$ für jede Turingmaschine $M$ mit Eingabealphabet $\mathrm{\Sigma }$ gilt.

Erster, zum scheitern verurteilter Versuch. Sei $M$ eine Turingmaschine mit Eingabealphabet $\mathrm{\Sigma }$, Arbeitsalphabet $\mathrm{\Gamma }$, Zustandsmenge $Q$, Startzustand $q_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}$, akzeptierendem Zustand $q_{\mathrm{y}\mathrm{e}\mathrm{s}}$ und Übergangsfunktion $\delta$. Wir codieren $M$ wie folgt: wenn $$\begin{array}{r}\delta (q,x)=(r,y,\mathtt{\text{R}})\\ \delta (q,y)=(s,z,\mathtt{\text{L}})\\ \dots \end{array}$$ dann schreiben wir in der Codierung $$\begin{array}{r}{q}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\mathrm{\#}{q}_{\mathrm{y}\mathrm{e}\mathrm{s}}\mathrm{\#}qxryR\mathrm{\#}qyszL\mathrm{\#}\dots \end{array}$$ Unser Codierungsalphabet ist also $$\begin{array}{r}\mathrm{\Lambda }:=Q\cup \mathrm{\Gamma }\cup \{\mathrm{\#},\mathtt{\text{L}},\mathtt{\text{S}},\mathtt{\text{R}}\}.\end{array}$$ Sehen Sie das Problem? Das Codierungsalphabet ist nicht uniform: wir brauchen, abhängig von der Zustandsmenge $Q$ und dem Bandalphabet $\mathrm{\Gamma }$ jeweils neue Alphabete. Wir wollen aber ein $\mathrm{\Lambda }$, da für alle Turingmaschinen mit Eingabealphabet $\mathrm{\Sigma }$ funktioniert.

Zweiter, erfolgreicher Versuch.

Wir müssen also die Zustandsmenge $Q$ und die Zeichen $\mathrm{\Gamma }\setminus \mathrm{\Sigma }$ erst einmal selbst codieren, beispielsweise über dem Alphabet $\{0,1\}$. Die $\delta$-Tabelle der Turingmaschine für $\{a^n{b}^n{c}^n\}$

würde dann zu folgender Tabelle:

Wenn wir dies nun als ein Wort in obigen Schema schreiben, können wir für eine Tabellenzelle $\delta (q,x)=(r,y,R)$ nicht einfach $qxryR$ schreiben, auch nicht einfach die Codierungen zusammenschreiben: in diesem Falle würde nämlich $\delta (00,0)=(11,0,\mathtt{\text{R}})$ zu $000110\mathtt{\text{R}}$ und wir würden nicht mehr erkennen, wo welches Zeichen beginnt und aufhört. Wir brauchen ein Separatorzeichen, beispielsweise ein Komma. Aus Gründen, die später klar werden werden, schließen wir die Codierung der Turingmaschine mit einem $\mathtt{\text{;}}$ ab. Die Codierung der obigen Maschine ist dann also

00#100#00,a,01,1,S#00,b,L#00,c,L#00,1,L#00,0,11,0,R#01,a,R#01,b,10,1,S#01,1,R#10,b,R#10,c,00,1,S#10,1,R#11,1,R#11,0,100#;

In dieser Codierung behalten wir zwei Konventionen bei: wenn eine Regel "fehlt", also beispielsweise für $\delta (10,a)$ die Zelle leer ist, dann soll das in den Zustand $q_{\mathrm{n}\mathrm{o}}$ führen; wenn in der Zelle nur ein Richtungszeichen, also beispielsweise 01,1,R steht, dann ist das eine Abkürzung für $$\begin{array}{r}\delta (01,1)=(01,1,\mathtt{\text{R}}),\end{array}$$ also #01,1,01,1,R#

Wir können nun jede Turingmaschine über dem Alphabet $\mathrm{\Sigma }$ codieren als Wort über dem Alphabet $$\begin{array}{r}\mathrm{\Lambda }:=\mathrm{\Sigma }\cup \{0,1,\mathtt{\text{\#}},\mathtt{\text{,}},\mathtt{\text{L}},\mathtt{\text{S}},\mathtt{\text{R}},\mathtt{\text{;}}\}\end{array}$$