Nichtdeterministische Turingmaschine

Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.

Informelle Beschreibung

Eine deterministische Turingmaschine (im Folgenden DTM) hat eine Übergangsfunktion, die für einen gegebenen Zustand und ein Symbol unter dem Lesekopf drei Dinge spezifiziert: das Symbol, das auf das Band geschrieben werden soll, die Richtung, in die der Lesekopf bewegt werden soll, und den Zustand, in den gewechselt werden soll.

Eine NTM unterscheidet sich von einer DTM dadurch, dass der aktuelle Zustand und das aktuelle Bandsymbol diese drei Dinge nicht mehr eindeutig festlegen, vielmehr gibt es mehrere mögliche Übergänge. Die NTM hat also für jede Eingabe nicht etwa einen eindeutigen Lauf, sondern viele verschiedene mögliche Läufe. (Das kann so interpretiert werden, dass sie zufällig einen der möglichen Läufe ausführt, oder aber so, dass sie alle möglichen Läufe parallel ausführt.) Sie akzeptiert die Eingabe, sofern es einen akzeptierenden Lauf gibt.

Da dieses Verhalten nach heutigem Kenntnisstand nicht ohne Weiteres realisierbar ist, handelt es sich um ein theoretisches Maschinenmodell. Trotzdem hat dieses Modell aus verschiedenen Gründen eine große Bedeutung für die theoretische Informatik, insbesondere für den Bereich der Komplexitätstheorie.

Formale Definition

Eine nichtdeterministische Turingmaschine (kurz: NTM) ist ein 7-Tupel $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)$ , wobei

Zustandsmenge: $Q\neq \emptyset$ ist eine endliche nichtleere Menge
Eingabealphabet: $\Sigma \neq \emptyset$ ist eine endliche nichtleere Menge
Bandalphabet: $\Gamma \neq \emptyset ,\Gamma \supset \Sigma$ ist eine endliche nichtleere Menge
Übergangsrelation: $\delta \subseteq ((Q\setminus F)\times \Gamma )\times (Q\times \Gamma \times \{L,N,R\})$
Startzustand: $q_{0}\in Q$
Blank-Symbol: $\square \in \Gamma \setminus \Sigma$
Menge der Endzustände: $F\subseteq Q$

Eine Konfiguration der NTM $M$ ist ein 4-Tupel $(u,q,a,v)$ , wobei $u\in \Gamma ^{\star }$ , $q\in Q$ , $a\in \Gamma$ und $v\in \Gamma ^{\star }$ (für eine Definition von $\Gamma ^{\star }$ siehe Kleenesche Hülle). Intuitiv bedeutet eine Konfiguration $(u,q,a,v)$ , dass sich die NTM $M$ im Zustand $q$ befindet, das Feld, auf dem sich der Schreib/Lese-Kopf befindet, das Symbol $a$ enthält, das unendliche Band links vom Schreib/Lese-Kopf den Inhalt $u$ hat (wobei unendlich viele Blank-Symbole links von $u$ nicht mit einbezogen werden) und rechts vom S/L-Kopf den Inhalt $v$ aufweist (auch hier wird wieder nur der endliche Teil betrachtet, der alle Nicht-Blank-Symbole enthält). Die Menge der Konfigurationen von $M$ sei mit $\operatorname {conf} (M)$ bezeichnet. Wir definieren eine binäre Relation $\Rightarrow _{M}$ auf $\operatorname {conf} (M)$ (genannt Konfigurationsübergangsrelation) wie folgt:

Für zwei Konfigurationen $c_{1}=(u_{1},q_{1},a_{1},v_{1})$ und $c_{2}=(u_{2},q_{2},a_{2},v_{2})$ gilt $c_{1}\Rightarrow _{M}c_{2}$ genau dann, wenn eine der folgenden Bedingungen erfüllt ist ( $\varepsilon$ steht hier für das leere Wort):

$u_{1}=u_{2}$ , $v_{1}=v_{2}$ und $(q_{1},a_{1},q_{2},a_{2},N)\in \delta$ oder
es gibt ein $a\in \Gamma$ , so dass $u_{1}=u_{2}=\varepsilon$ , $av_{1}=v_{2}$ , $a_{2}=\square$ und $(q_{1},a_{1},q_{2},a,L)\in \delta$ oder
es gibt ein $a\in \Gamma$ , so dass $u_{1}=u_{2}a_{2}$ , $av_{1}=v_{2}$ und $(q_{1},a_{1},q_{2},a,L)\in \delta$ oder
es gibt ein $a\in \Gamma$ , so dass $u_{1}a=u_{2}$ , $v_{1}=v_{2}=\varepsilon$ , $a_{2}=\square$ und $(q_{1},a_{1},q_{2},a,R)\in \delta$ oder
es gibt ein $a\in \Gamma$ , so dass $u_{1}a=u_{2}$ , $v_{1}=a_{2}v_{2}$ und $(q_{1},a_{1},q_{2},a,R)\in \delta$ .

Die Anfangskonfiguration von $M$ auf dem Eingabewort $w\in \Sigma ^{\star }$ ist die Konfiguration $c_{0}=(\varepsilon ,q_{0},\square ,w)$ . Eine Konfiguration $c=(u,q,a,v)$ heißt Endkonfiguration, wenn $q\in F$ . Ist $c$ eine Endkonfiguration, dann heißt sie akzeptierende Endkonfiguration, wenn $a\neq \square$ , ansonsten heißt sie nicht-akzeptierende Endkonfiguration.

Ein endlicher Lauf von $M$ auf dem Eingabewort $w$ ist eine endliche Sequenz $c_{0},c_{1},\ldots ,c_{n}$ von Konfigurationen, wobei $c_{0}$ die Anfangskonfiguration auf $w$ ist, $c_{n}$ eine Endkonfiguration und für jede natürliche Zahl $i$ mit $1\leq i\leq n$ gilt: $c_{i-1}\Rightarrow _{M}c_{i}$ . Ein endlicher Lauf auf $w$ heißt akzeptierend, wenn $c_{n}$ akzeptierend ist, ansonsten heißt er nicht-akzeptierend.

Ein unendlicher Lauf von $M$ auf Eingabe $w$ ist eine unendliche Sequenz $c_{0},c_{1},c_{2},\ldots$ von Konfigurationen, wobei $c_{0}$ die Anfangskonfiguration auf $w$ ist und für jede natürliche Zahl $i$ mit $1\leq i$ gilt: $c_{i-1}\Rightarrow _{M}c_{i}$ .

Ein Entscheider ist eine NTM, die keinen unendlichen Lauf hat. Sei $M$ ein Entscheider. Die von $M$ akzeptierte Sprache $L_{M}\subseteq \Sigma ^{\star }$ ist definiert als $L_{M}=\left\{w\in \Sigma ^{\star }\mid \right.$ es gibt einen akzeptierenden Lauf von $M$ auf $\left.w\right\}$ .

Äquivalenz zu Deterministischen Turingmaschinen

Da jede (deterministische) Übergangsfunktion einer DTM als Übergangsrelation einer NTM aufgefasst werden kann, sind NTM mindestens so mächtig wie DTM, da sie diese komplett enthalten. Umgekehrt kann auch jede von einer NTM erkannte Sprache von einer DTM erkannt werden. Die DTM simuliert alle Übergänge der NTMs, indem sie mehrere Kopien des simulierten Zustands erstellt, sofern mehrere Übergänge möglich sind; diese werden dann parallel simuliert. Kann z. B. ein Problem von einer NTM in polynomieller Zeit gelöst werden, so kann es von einer deterministischen Turingmaschine in exponentieller Zeit gelöst werden. Es gibt dann auch eine DTM, die das Problem mit polynomiellem Speicheraufwand löst (Satz von Savitch).

Bedeutung in der Komplexitätstheorie

Die Bedeutung nichtdeterministischer Turingmaschinen erklärt sich wie folgt: Man betrachtet ein Problem nur dann als effizient lösbar, wenn es sich in Polynomialzeit entscheiden lässt. Auf deterministischen Turingmaschinen werden alle Probleme, für die dies gilt, der Klasse P zugerechnet. Es gibt jedoch eine recht große Anzahl von praktisch sehr bedeutsamen Problemen, für die noch nicht gezeigt werden konnte, ob sie in P liegen. Wie sich herausgestellt hat, lassen sich zahlreiche dieser Probleme auf einer nichtdeterministischen Turingmaschine in polynomieller Zeit entscheiden, sie liegen in NP. Die Tatsache, dass so viele wichtige, aber deterministisch bisher nicht effizient lösbare Probleme in dieser Klasse liegen, hat die Hoffnung genährt, durch eine Untersuchung des nichtdeterministischen Turingmaschinentyps Hinweise auf eine effizientere Lösung dieser Probleme zu erhalten. Ließe sich etwa ein allgemeines Verfahren finden, mit dem eine nichtdeterministische Turingmaschine durch eine deterministische in Polynomialzeit simuliert werden kann, so wäre für alle genannten Probleme gezeigt, dass sie in P liegen und damit effizient lösbar sind. Die Klassen P und NP wären dann identisch. Dies ist aber bis heute nicht gelungen. Die Fragestellung ist auch als P-NP-Problem bekannt.

Mittels nichtdeterministischer Turingmaschinen werden neben NP eine Reihe bedeutsamer Komplexitätsklassen definiert. Die Menge aller Zeitkomplexitätsklassen, die auf nichtdeterministische Turingmaschinen zurückgeführt werden, heißt NTIME. Analog ist NSPACE die Menge aller Raumkomplexitätsklassen dieses Maschinentyps.

Siehe auch

Literatur

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3., aktualisierte Auflage. Pearson Studium, München 2011, ISBN 978-3-86894-082-4, 8.4.4 Nichtdeterministische Turing-Maschinen (englisch: Introduction to Automata Theory, Languages, and Computation. 2007. Übersetzt von Sigrid Richter und Ingrid Tokar).
Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 3.2 Nichtdeterministische Turingmaschinen und die Klasse NP.

Quellenhinweis

Dies ist eine freie, nicht-vollständige Übersetzung des Eintrags in der Englischen Wikipedia. Für Quellenangaben vgl. dort.