4.3 Variationen: Mehrband-Maschinen, nichtdeterministische Maschinen

Turingmaschinen mit mehreren Bändern

Im letzten Teilkapitel ist Ihnen bestimmt aufgefallen, dass es auffallend lästig ist, selbst für einfache Sprachen wie \begin{align*} \{a^n b^n c^n \ | \ n \geq 0 \} \end{align*} oder \begin{align*} \{wcw \ | \ w \in \{a,b\}^*\} \end{align*} Turingmaschinen zu programmieren. Ein Grund dafür ist, dass die Maschine nur an einer Position des Bandes lesen und schreiben kann und man deswegen ständig zwischen verschiedenen Stellen hin- und herfahren muss. Es bietet sich daher an, an etwas allgemeineres Modell einer Rechenmaschine zu definieren, das dann auch leichter zu programmieren ist. Dies ist die Mehrband-Turingmaschine.

Eine Mehrband-Turingmaschine ist wie eine Turingmaschine, nur dass sie statt einem \(k\) viele Bänder und somit auch \(k\) viele Schreib-Lese-Köpfe hat. Die Zustandsübergangsfunktion \(\delta\) hat somit auch die Signatur \begin{align*} \delta : Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \lsr^k \end{align*}

carry1, 0, 0, _ 
carry0, 0, 0, 1, <, <, < 

carry1, 0, 1, _ 
carry1, 0, 1, 0, <, <, < 

Berechnete Sprache, berechnete Funktion. Die Begriffe des Akzpetierens und Ablehnens definieren wir genau wie für die Einband-Turingmaschinen. Eine formale Definition der Konfiguration ersparen wir uns jedoch. Wenn unsere Mehrband-Turingmaschine nicht nur akzeptieren / ablehnen, sondern etwas berechnen soll, also eine Funktion \begin{align*} f : \Sigma_1 \rightarrow \Sigma_2 \ , \end{align*} dann bauen wir sie per Konvention so, dass sie ein designiertes Ausgabeband hat, auf dem nach Abschluss der Berechnung das Ausgabewort \(f(x)\) steht.

Einband-Maschinen können Mehrband-Maschinen simulieren

Es stellt sich heraus, dass mehrere Bänder zwar ein praktisches Feature sind, aber nicht wirklich mehr Ausdruckskraft verlangen; was eine Mehrband-Turingmaschine schafft, schafft eine Einband-Turingmaschine auch.

Beweis. Der erste Trick ist, dass wir die \(k\) Bänder von \(M\) "zusammenkleben" in ein neues Band, in welcher jede Zelle \(k\) Symbole enthalten kann:

Das Problem sind nun die Köpfe. Wenn wir diese Idee naiv umsetzen würden, hätte unsere Maschine \(M'\) zwar ein Band, dafür drei Köpfe auf diesem:

Wir lösen dies, indem wir die Kopfpositionen in das Band selbst reinschreiben:

Das neue Bandalphabet ist also nicht \(\Gamma^k\) sondern \((\Gamma \times \{\texttt{head}, \texttt{nohead}\} )^k\). Wo steht nun aber denn der Kopf von \(M'\)? Jetzt kommt der schwierige Teil: um einen Schritt von \(M\) zu simulieren, muss \(M'\) von ganz links nach ganz rechts laufen und alle Informationen über die \(k\) \(M\)-Köpfe sammeln. Dann von rechts nach links gehen und die ausführen.

Wir müssen also die Zustandsmenge deutlich erweitern; so muss sie speichern können, ob wir ein Symbol bereits gelesen haben; ob wir ein Symbol bereits geschrieben haben und ob wir den Kopf bereits entsprechend verschoben haben. Für eine Rechtsverschiebung müssen wir uns zusätzlich noch merken, dass wir sie gerade durchführen und für welches Band. All dies ist viel, aber immer noch endlich. Wir können alles in einer endlichen Zustandsmenge \(Q'\) speichern.

Wenn der \(M\)-Zustand (der natürlich auch im \(M'\)-Zustand gespeichert ist), accept erreicht hat, dann macht \(M'\) noch eine Aufräumphase, in welcher sie alle Symbole, die nicht zum Ausgabeband gehören, durch \(\square\) ersetzt. Dann wechselt sie in ihren eigenen akzeptierenden Zustand accept'.

\(\square\)

Einfügen versus Überschreiben

name: replace_b_by_c
init: init 
accept: accept 

init, a
init, a, > 

init, b
init, c, > 

init, _ 
accept, _, > 

Ungleich schwieriger ist die Aufgabe, jedes \(b\) durch ein \(bc\) zu ersetzen, weil wir hier etwas einfügen wollen. Auf einer Einband-Turingmaschine müssen wir für jedes \(b\) alles, was rechts davon kommt, um eine Zelle nach rechts verschieben. Meinen Quelltext finden sie in replace-b-by-bc.txt. Können wir unserer Turingmaschine die Funktionalität geben, eine Zelle einzufügen und alles von Kopf bis zum linken Ende um eins nach links zu verschieben bzw. das analoge, aber nach rechts? Wir sind freie Menschen, wir können definieren, was wir wollen, müssen uns aber zwei Fragen stellen:

1. Ist das immer noch ein plausibles Modell einer Rechenmaschine? Ist also unser neue Funktionalität physikalisch realisierbar?
2. Verleiht es wirklich neue Funktionalität, oder ist es nur Syntaxzucker?

In diesem Fall ahnen Sie es wohl bereits: es ist nur Syntaxzucker. Die Funktionalität des Einfügens/Verschiebens können wir leicht mit zwei Bändern simulieren. Wir halten uns einfach an die Konvention, dass auf Band 1 der Kopf immer auf dem linkesten Zeichen steht und auf Band 2 der Kopf jenseits des rechtesten. \begin{align*} \delta(q,x) = (r,y,\texttt{R}) \end{align*} wird dann

q, x, _
r, _, x, >, > 

q,  x, _ 
r', x, _, -, - 

r', _, c
r,  c, _   // für jedes Zeichen c
                            

Nehmen Sie die Beispielmaschine go-left-go-right.txt, geben Sie sie auf turingmachinesimulator.com ein und starten Sie sie mit dem Eingabewort \(xxx\).

Ein neues Zeichen links vom Kopf einfügen ist nun einfach: aus \begin{align*} \delta(q,x) = \textnormal{Zustand $r$, schreibe $y$ und füge $z$ links vom Kopf ein} \end{align*} wird

q,   x, _ 
r'', _, z, >, > 

r'', c, _ 
r,   c, y, -, > // für jedes Zeichen c 

Sie können sich meine Implementierung in insert-z-before-y.txt ansehen. Geben Sie beispielsweise xxyxyyxx als Eingabewort ein.

Wir können von nun an also so tun, als hätten unsere Turingmaschinen die Möglichkeit, zusätzliche Zellen einzufügen. In einer konkreten Implementierung müssten wir dafür allerdings jedes Band durch zwei Bänder ersetzen. Alternativ können Sie sich eine Turingmaschine vorstellen, die statt \(k\) Bändern einfach \(2k\) Stapel hat.

Die Dictionary-Maschine

Ein fundamentale Datenstruktur beim Programmieren sind Dictionaries, die Key-Value-Paare speichern:

python -i                        
dict = {"karl" : 42, "eva" : 35, "werner" : 20}
dict["eva"]
35

Im Zweifelsfall sind diese als Hashmaps oder Rot-Schwarz-Bäume oder B-Bäume implementiert. Hier interessiert uns nicht so sehr die Laufzeit, sondern einfach die Funktionalität. Können wir für Dictionaries eine Turingmaschine implementieren?

Nichtdeterministische Turingmaschinen

Bereits im Kapitel über reguläre Sprachen haben wir gesehen, dass Nichtdeterminismus hilfreich ist, wenn wir Dinge beschreiben wollen, auch wenn es kein realistisches Modell für Rechenmaschinen darstellt. Die Sprache aller Wörter über $\{a,b\}$, die das Teilwort \(aababaa\) enthalten, kann man beispielsweise leicht mit dem folgenden Automaten beschreiben:

Andererseits haben wir für endliche Automaten gezeigt, dass die deterministischen und nichtdeterministischen Varianten tatsächlich gleichmächtig sind (Potenzmengenkonstruktion). Für die Kellerautomaten, die für kontextfreie Sprachen relevant sind, galt das nicht (einen Beweis haben wir allerdings in der Vorlesung nicht durchgenommen). Wie sieht es nun für Turingmaschinen aus?

Um nichtdeterministische Turingmaschinen zu definieren, müssen wir die Zustandsübergangsfunktion \(\delta\) zu einer Zustandsübergangsrelation machen. Statt \(\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \lsr\) also nun \begin{align*} \delta \subseteq (Q \times \Gamma) \times (Q \times \Gamma \times \lsr) \ . \end{align*} Und statt \(\delta(q,x) = (r,y,\texttt{D})\) schreiben wir nun \((q,x) \step{\delta} (r,y,\texttt{D})\). Wir beschränken uns zunächst auf Einband-Turingmaschinen. Für Konfigurationen \(C \in \Gamma^* \times Q \times\Gamma^*\) haben wir keine erweiterte Zustandsübergangsfunktion \(\delta(C) = C'\), wo \(C'\) die Folgekonfiguration ist, sondern eine erweiterte Zustandsübergangsrelation: \begin{align*} C \Step{} C' \end{align*} Wobei nun dank Nichtdeterminismus mehrere Folgekonfigurationen \(C'\) geben kann (oder eben mal auch gar keine). Wir schreiben \begin{align*} C \Step{}^* C' \end{align*} wenn wir von \(C\) in einer Folge von Schritten nach \(C'\) kommen können, also \begin{align*} C = C_0 \Step{} C_1 \Step{} C_2 \Step{} \dots \Step{} C' \end{align*} Wir sagen auch: Die Konfiguration \(C'\) ist von \(C\) aus erreichbar.

Für ein Eingabewort \(x\) sei \(C_x := \qstart x\) die Startkonfiguration. Eine nichtdeterministische Turingmaschine akzeptiert \(x\), wenn es eine akzeptierende Endkonfiguration \(C_{\rm accept}\) gibt mit \begin{align*} C_x \Step{}^* C_{\rm accept} \end{align*} wenn es also (mindestens) eine akzeptierende Konfiguration gibt, die von \(C_x\) aus erreichbar ist. Dabei kann es mehrere erreichbare akzeptierende Konfigurationen geben, Es kann sogar eine ablehnende Konfiguration \(C_x \Step{}^* C_{\rm reject}\) geben. Spielt keine Rolle: solange es einen Weg \(C_x \Step{}^* C_{\rm accept}\) gibt, sagen wir, dass \(M\) das Eingabewort akzeptiert.

Deterministische Turingmaschinen simulieren nichtdeterministische

Sind nun nichtdeterministische Turingmaschinen inhärent mächtiger? Können Sie das Teilsummenproblem auch mit einer deterministischen lösen? Klar! Hier ist mein Code in Elm, einer funktionalen Programmiersprache: er probiert alle Möglichkeiten durch.

module SubsetSum exposing (..)


subsetSum : List Int -> Int -> Bool
subsetSum prices amount =
    case ( prices, amount ) of
        ( [], 0 ) ->
            True

        ( x :: rest, _ ) ->
            subsetSum rest amount || subsetSum rest (amount - x)

        ( [], _ ) ->
            False

Auf einer deterministischen Turingmaschine wäre das deutlich anstrengender, aber irgendwie auch möglich. Können wir jede nichtdeterministische Turingmaschine deterministisch simulieren, indem wir "alles ausprobieren"? Ja, in der Tat!

Beweis. Als erstes führen wir eine kosmetische Änderung unserer nichtdeterministischen Maschine durch: wir wollen, dass es für jedes \((q,c)\) genau zwei Möglichkeiten gibt, also \begin{align*} (q,c) & \rightarrow (q_1, c_1, D_1) \\ (q,c) & \rightarrow (q_2, c_2, D_2) \ , \end{align*} außer wenn \(q \in \{\texttt{reject},\texttt{accept}\}\); dann gibt es gar keine Möglichkeit. Dies ist einfach: sollte es mehr als zwei Möglichkeiten geben, so führen wir Zwischenzustände ein:

Auf der Menge der Konfigurationen schaut das dann noch intuitiver aus:

Sollte ein Paar \((q,c)\) weniger als zwei Folgemöglichkeiten geben, so erfinden wir einfach neue, die jedoch direkt nach reject führen. Es sollte klar sein, dass diese Änderungen rein kosmetisch sind und nichts an der Funktionsweise von \(M\) ändern.

Nun bauen wir \(M\) um und geben ihr ein zweites Band. Auf diesem Band soll ein Wort in \(\{0,1\}^*\) stehen. Wir machen \(M\) deterministisch mit der folgenden Regel: wenn Du im Zustand \(q\) bist und auf dem ersten Band ein \(c\) hast und auf dem zweiten Band eine \(0\) liest, nimm den oberen Pfeil, der von \(q,c\) ausgeht; wenn Du eine \(1\) liest, nimm den unteren Pfeil.

Falls wir auf dem zweiten Band einem anderen Zeichen begegnen (\(\square\) oder sonst etwas, das weder 0 noch 1 ist), dann lehnen wir sofort ab. Wir haben nun eine deterministische Turingmaschine \(M''\), die jedoch nicht das gleiche tut wie \(M\). Aber: wenn \(x \in L(M)\), dann gibt es ein Wort \(z \in \{0,1\}^*\), das wir auf das zweite Band schreiben könnten, so dass \(M''\) das Eingabewort \(x\) akzeptiert. Im Gegenzug: wenn \(x \not \in L(M)\), dann können wir auf das zweite Band schreiben, was wir wollen, \(M''\) wird immer ablehnen.

Nun bauen wir schlussendlich eine Maschine \(M'\), die in einer Endlosschleife alle möglichen \(z \in \{0,1\}^*\) aufzählt, auf das zweite Band schreibt, und \(M''\) neustartet. Geht das? Wir können zum Beispiel \(i = 1,2,3,4,\dots\) hochzählen, binär schreiben und die führende 1 löschen. Überzeugen Sie sich, dass in dieser Reihe wirklich alle \(z \in \{0,1\}^*\) vorkommen.

\(\square\)