Nichtdeterministische Turingmaschinen

Autor: Anton Krohmer

In dieser Unit werden wir die nichtdeterministischen Turingmaschinen (NTMs) kennenlernen. Dabei müssen wir uns von Anfang an klar machen: Eine NTM kann man physikalisch nicht bauen, wie es für eine TM, DFA oder sogar NFA gehen würde. In diesem Sinne ist sie für den größten Teil der Weltbevölkerung uninteressant. In der theoretischen Informatik ist die NTM jedoch eine der wichtigsten Maschinenmodelle überhaupt, weil sie uns dabei hilft, schwere Probleme zu beschreiben. Wir haben schwere Probleme schon in der Form von nicht berechenbaren Sprachen gesehen; viele Sprachen sind jedoch entscheidbar, aber die entsprechenden Algorithmen sind so langsam, dass man sie nicht für Eingebagrößen jenseits \(n \geq 50\) in einer Lebenszeit lösen kann. Interessanterweise ist für viele Probleme auch unklar, ob es überhaupt bessere Ansätze gibt als die naiven Algorithmen. Diese Wissenslücke wird meist durch die Frage \(\mathsf P\) vs \(\mathsf{NP}\) auf einen Punkt gebracht. Dieser Frage wollen wir uns in der Unit nähern.

Voraussetzungen

Diese Unit baut auf den beiden Units für Turing Maschinen und Endlichen Automaten auf. Wenn du diese noch nicht kennst, dann arbeite zuerst die durch.

Formale Definition

Wir beginnen mit der formalen Definition einer nichtdeterministischen Turingmaschine. Dies ist einfach nur eine Verknüpfung der Konzepte der Turingmaschine und des Nichtdeterminismus, die du beide bereits schon kennst. Schauen wir es uns an:

Eine (\(k\)-Band) nichtdeterministische Turingmaschine ist ein Tupel \(M = (Q, \Sigma, \Gamma, \square, q_0, F, \delta)\), wobei

• \(Q\) eine endliche, nichtleere Menge an Zuständen,
• \(\Gamma\) eine endliche, nichtleere Menge an Symbolen für das Bandalphabet,
• \(\Sigma \subset \Gamma\) eine endliche, nichtleere Menge an Symbolen für das Eingabealphabet,
• \(\square \in \Gamma \setminus \Sigma\) das Blank-Symbol (einziges Symbol, das unendlich oft auf dem Band stehen darf),
• \(q_0 \in Q\) der Startzustand,
• \(F \subseteq Q\) die akzeptierenden Zustände und
• \(\delta \subseteq (Q \times \Gamma^k) \times (Q \times \Gamma^k \times \{ L, S, R\}^k)\) eine Relation namens Übergangsrelation ist.

Wir beobachten, dass diese Definition in allen Punkten mit der Definition der deterministischen Turingmaschine übereinstimmt, bis auf den Letzten. Statt einer Übergangsfunktion haben wir nun eine Übergangsrelation. Wie sich das auf die Berechnung auswirkt, hast du bereits bei den deterministischen Automaten gesehen. Die Turingmaschine kann damit in mehreren Zuständen gleichzeitig sein.

Im Gegensatz zu DFAs/NFAs ist die Turingmaschine aber mächtiger: Sie kann auf das Band schreiben. Dies hat aber zum Nachteil, dass die Konfiguration einer NTM deutlich komplizierter wird vorher. Für einen NFA mussten wir uns nur merken, in welchen Zuständen wir uns befinden. In einer NTM müssen wir uns dazu noch zu jedem Zustand merken, was die NTM auf das Band geschrieben hat! Dies kann auch von nichtdeterministischen Entscheidungen abhängen, welche wiederum von dem Bandinhalt abhängen können. Daher müssen müssen wir den Konfigurationsbegriff erweitern.

Berechnungspfad und Konfiguration

Eine Konfiguration einer nichtdeterministischen Turingmaschine beschreibt deren Zustand während einer Berechnung komplett. Wir definieren daher die Konfiguration als \(C = (q, (p_1, x_1), \ldots, (p_k, x_k)) \in Q \times (\mathbf{N} \times \Gamma^*)^k, \) wobei \(q\) der derzeitige Zustand der NTM ist, \(p_i \leq |x_i|\) die Position des Lesekopfes auf Band \(i\), und \(x_i\) der Inhalt des Bandes \(i\) ist (ausgenommen die führenden bzw. folgenden Blank-Zeichen). Die Startkonfiguration auf Eingabe \(x\) einer NTM nennen wir \(SC(x)\).

Wir wollen nun betrachten, wie man von einer Konfiguration in die nächste gelangen kann. In einer DTM war dies immer eindeutig: Gegeben einen Zustand und ein Zeichen auf dem Band, konnte man an der Übergangsfunktion ablesen, was der Nachfolgezustand (und damit die Nachfolgekonfiguration) ist. In einer NTM kann es nun mehrere Nachfolgezustände geben. Dies überträgt sich damit direkt auf die Konfigurationen.

Sei \(C= (q, (p_1, x_1), \ldots, (p_k, x_k)) \) und \(C' = (q', (p'_1, x'_1), \ldots, (p'_k, x'_k))\), und seien die Wörter auf den Bändern \(x_i = u_i\alpha_iv_i\) mit \(|u_i| = p_i-1\) und \(\alpha_i \in \Sigma\) für alle \(i \leq k\); das heißt, jeder Lesekopf \(i\) in \(C\) steht auf Zeichen \(\alpha_i\). Dann nennen wir \(C'\) einen Nachfolger von \(C\), falls es in einem Berechnungsschritt von \(C\) erreicht werden kann. Es kann auch mehrere Nachfolger von \(C\) geben, da die Turingmaschine nichtdeterministisch ist. Formal bedeutet dies, dass falls \(((q,\alpha_1,\ldots, \alpha_k),(q', \beta_1, \ldots, \beta_k, r_1, \ldots, r_k)) \in \delta\), dann gilt für alle \(1 \leq i \leq k\), \[ x'_i = u_i\beta_iv_i\] und \[ p'_i = \begin{cases} p_i-1 \text{ falls } r_i = L, \\ p_i+1 \text{ falls } r_i = R, \end{cases}\] es sei denn, \(p_i = 1\) und \(r_i = L\) oder \(p_i = |x_i|\) und \(r_i = R\). In den letzteren beiden Fällen besucht \(M\) eine neue Zelle. Daher muss in diesen Fällen \(x_i\) um ein Symbol erweitert werden. Falls \(p_i = 1\) und \(r_i = L\), dann \[ x'_i = \square \beta_i v_i\] und \[ p'_i = 1.\] Falls \(p_i = |x_i|\) und \(r_i = R\), dann \[ x'_i = u_i \beta_i \square \text{ und } p'_i = |x_i| + 1.\]

Wir schreiben \(C \vdash_M C'\) um zu sagen, dass \(C'\) ein (möglicher) Nachfolger von \(C\) ist. Ein Berechnungspfad \(\sigma\) ist eine Folge von Konfigurationen, die mit der Startkonfiguration beginnt: \(\sigma := SC(x) \vdash \ldots \vdash C_m\). Eine Konfiguration, die keinen Nachfolger hat, ist haltend.

Der entscheidende Unterschied ist nun: Eine NTM \(M\) akzeptiert \(x\), falls es einen Berechnungspfad gibt, der in \(SC(x)\) beginnt und in einer haltenden Konfiguration \(C_m = (q, (p_1, x_1), \ldots, (q_k, x_k))\) endet, und \(q \in F\) ein akzeptierender Zustand ist. Da es teils mehrere Nachfolger für eine Konfiguration gibt, spricht man auch von einem Berechnungsbaum.

Zeit- und Platzverbrauch

Wie für DTMs wollen wir nun für NTMs den Zeit- bzw- Platzverbrauch einer Maschine definieren. Es ergibt sich hier aber eine interessante Beobachtung: Je nach Berechnungspfad kann der Zeit- bzw. Platzverbrauch der NTM variieren! Wir entscheiden uns für die folgende Definition: \(\mathrm{Time}_M(x)\) sei die Länge des kürzesten akzeptierenden Pfades in dem Berechnungsbaum von \(M\) auf Eingabe \(x\), wenn solch ein Pfad existiert. Anderenfalls setzen wir \(\mathrm{Time}_M(x) = \infty\). Dann können wir damit den Zeitverbrauch in Abhängigkeit der Eingabelänge \(n\) definieren: \[\mathrm{Time}_M(n) = \max\{ \mathrm{Time}_M(x) \mid |x| = n, \quad x\in L(M) \}.\]

Falls es kein \(x \in L(M)\) mit Länge \(n\) gibt, dann setzen wir \(\mathrm{Time}_M(n) = 0\). Beachte: Dies ist unterschiedlich zu der Definition im deterministischen Fall, wo \(\mathrm{Time}_M(n)\) das Maximum über alle Eingaben der Länge \(n\) war. Sei \(t\colon \mathbb N \to \mathbb N\) eine beliebige Funktion. Wir sagen, dass die NTM \(M\) schwach \(t\)-zeitbeschränkt ist, wenn \(\mathrm{Time}_M(n) \leq t(n)\) für alle \(n\) gilt. Eine alternativer (und vielleicht intuitiverer) Ansatz, wäre es zu sagen, dass \(M\) stark \(t\)-zeitbeschränkt ist, wenn alle Berechnungspfade auf allen \(x\) höchstens Länge \(t(|x|)\) haben. Man kann aber zeigen, dass dies für vernünftige Funktionen \(t\) tatsächlich äquivalent zu schwach \(t\)-zeitbeschränkt ist.

Es verbleibt, die Komplexitätsklassen für NTMs zu definieren. Sei \(t\colon \mathbb N \to \mathbb N\). Dann definieren wir \[\mathsf{NTime}(t) := \{ L \mid \exists \text{ eine schwach } t\text{-zeitbeschränkte NTM } M \text{ mit } L = L(M)\}.\]

In einer ähnlichen Art und Weise lässt sich der Platzverbrauch beschreiben. Wir definieren \(\mathrm{Space}_M(x)\) für ein \(x\in L(M)\) als das Minimum vom Platzverbrauch über alle akzeptierenden Konfigurationspfade von \(M\). Dann schreiben wir \[\mathrm{Space}_M(n) = \max\{ \mathrm{Space}_M(x) \mid |x|=n, \quad x\in L(M). \}\] Falls es für ein \(n\) kein \(x \in L(M)\) mit \(|x| = n\) gibt, schreiben wir \(\mathrm{Space}_M(n) = 0\). Sei \(s\colon \mathbb N \to \mathbb N\) eine beliebige Funktion. Wir sagen, dass \(M\) schwach \(s\)-platzbeschränkt ist, wenn \(\mathrm{Space}_M(n) \leq s(n)\) für alle \(n\) gilt. Die Definition von stark \(s\)-Platzbeschränktheit ist analog. \[\mathsf{NSpace}(s) := \{L \mid \exists \text{ eine schwach } s\text{-platzbeschränkte NTM } M \text{ mit } L = L(M) \}. \]

Ein Beispiel

Betrachten wir die arithmetische Formel \[x_1 + 2x_2(1-x_1) + x_3.\] Wir möchten wissen, ob man die Werte 0 und 1 so zu den Variablen zuweisen kann, dass die Formel zu 1 evaluiert. Man könnte beispielsweise \(x_1 := 1, x_2:= 0, x_3:= 0\) wählen. Es gibt aber nicht immer eine solche Zuweisung: Die Formel \(x_1(1-x_1)\) evaluiert immer zu \(0\).

Gegeben eine arithmetische Formel, möchten wir herausfinden, ob es eine solche Zuweisung gibt, sodass die Formel zu 1 evaluiert. Damit die Formeln von (N)TMs verarbeitet werden können, müssen sie als Binärstrings kodiert werden. Wie man das genau macht, ist im Prinzip egal, solange die Kodierung einfach zu berechnen ist. Dies bedeutet für uns, dass man eine Formel der (kodierten) Länge \(\ell\) in Zeit \(\mathcal O(\ell^3)\) evaluieren kann. Du kannst ja mal versuchen, solch eine Kodierung zu finden (oder du glaubst einfach, dass es geht). Sei nun

\[\mathrm{AFSAT} = \{F \mid \text{ es gibt eine } \{0,1\} \text{ Zuweisung von Variablen, sodass } F \text{ zu } 1 \text{ auswertet}\}. \]

Wie schwer ist es, diese Sprache zu entscheiden? Angenommen, \(F\) habe (kodierte) Länge \(n\). Dann hat \(F\) höchstens \(n\) Variablen. Im klassischen, deterministischen Fall könnte man einfach alles durchprobieren: Es gibt maximal \(2^n\) mögliche Zuweisungen, und für jedes davon kann man in \(\mathcal O(n^3)\) Zeit testen, ob \(F\) zu 1 evaluiert oder nicht. Daher gilt: \[\mathrm{AFSAT} \in \mathrm{DTime}(\mathcal O(2^n \cdot n^3)).\] Es ist offen, ob es dafür einen Polynomialzeit-Algorithmus gibt. Vielleicht findest du ihn ja? Eine NTM jedenfalls kann Folgendes machen: Bei dem Lesen der Eingabe schreibt die NTM für jedes Symbol nichtdeterministisch entweder eine 0 oder eine 1 auf das zweite Band. Der Berechnungsbaum hat damit bereits eine Größe von \(2^n\). In jedem Blatt hat die NTM damt einen String der Länge \(n\) auf dem zweiten Band stehen. Wir interpretieren diesen String als Variablenbelegung (und ignorieren überschüssige Bits). Danach kann die NTM (deterministisch) testen, ob die vorliegende Belegung die Formel \(F\) zu 1 evaluieren lässt.

Offenkundig benötigt diese Maschine nicht mehr als \(\mathcal O(n^3)\) Zeit, da die Länge jedes Berechnungspfades durch die Evaluierung der Formel dominiert wird. Außerdem entscheidet die Maschine korrekt, ob \(F \in \mathrm{AFSAT}\) gilt: Wenn es eine Zuweisung von Variablen gibt, dann wird diese Zuweisung als eine der \(2^n\) Bitstrings generiert. Ein solcher Berechnungspfad ist akzeptierend, und damit akzeptiert auch die NTM. Wenn es keine Zuweisung von Variablen gibt, dann wird in allen Berechnungspfaden abgelehnt, und die NTM verwirft die Eingabe. Daher gilt \[\mathrm{AFSAT} \in \mathrm{NTime}(\mathcal O(n^3)). \]

Wie \(\mathrm{AFSAT}\) (welches eher pädagogischen Wert hat) gibt es viele weitere ähnliche, und sehr sehr wichtige Probleme, welche alle die gleiche Eigenschaft haben: Um eine Lösung zu finden, gibt es im Prinzip nichts besseres als alle möglichen Lösungen durchzuprobieren. Wenn es allerdings einen Lösungskandidaten gibt, kann man sehr schnell überprüfen, ob dieser korrekt ist. Diese Klasse von Problemen wird von NTMs eingefangen.

Was haben wir gelernt?

• Nichtdeterministische Turingmaschinen sind ein theoretisches Berechnungsmodell, das physikalisch nicht konstruierbar ist.
• Es gibt nichtdeterministische Übergänge, was bedeutet, dass die NTM von der gleichen Konfiguration in verschiedene Konfigurationen springen kann.
• Wenn es einen oder mehr akzeptierende Konfigurationspfade gibt, akzeptiert die NTM die Eingabe.
• Die NTM verbraucht so viel Platz und Zeit, wie sie auf dem kürzesten akzeptierenden Pfad benötigt.
• Durch Nichtdeterminismus ist es möglich, viele verschiedene Bitstrings auf einmal durchzuprobieren.