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 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 der 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 nicht etwa einen eindeutigen Lauf, sondern viele verschiedene mögliche Läufe. Sie akzeptiert die Eingabe, sofern sie einen akzeptierenden Lauf findet.

Da dieses Verhalten nach heutigem Kenntnisstand nicht ohne Weiteres realisierbar ist, handelt es sich um ein theoretisches Maschinenmodell. Nichtsdestoweniger 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\supseteq \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$

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₁ = (u₁,q₁,a₁,v₁) und c₂ = (u₂,q₂,a₂,v₂) gilt $c_1\Rightarrow_M c_2$ genau dann wenn eine der folgenden Bedingungen erfüllt ist (ε steht hier für das leere Wort):

• u₁ = u₂, v₁ = v₂ und $(q_1,a_1,q_2,a_2,n)\in\Delta$ oder
• es gibt ein $a\in \Gamma$, so dass u₁ = u₂ = ε, av₁ = v₂, $a_2=\square$ und $(q_1,a_1,q_2,a,l)\in\Delta$ oder
• es gibt ein $a\in \Gamma$, so dass u₁ = u₂a₂, av₁ = v₂ und $(q_1,a_1,q_2,a,l)\in\Delta$ oder
• es gibt ein $a\in \Gamma$, so dass u₁a = u₂, v₁ = v₂ = ε, $a_2=\square$ und $(q_1,a_1,q_2,a,r)\in\Delta$ oder
• es gibt ein $a\in \Gamma$, so dass u₁a = u₂, v₁ = a₂v₂ 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₀ 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₀ 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

Intuitiv scheint es, als seien NTMs ausdrucksstärker als DTMs, da sie viele mögliche Läufe haben, von denen nur einer erfolgreich enden muss; jedoch kann jede von einer NTM erkannte Sprache auch 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, dass 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

• Deterministische Turingmaschine (DTM)
• linear beschränkte Turingmaschine (LBA)
• Turingmaschine mit Zusatzeingabe
• Orakel-Turingmaschine

Quellenhinweis

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