Nichtdeterministische Turingmaschine

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Informelle Beschreibung[Bearbeiten]

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. 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[Bearbeiten]

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_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_2a_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_1a=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_1a=u_2, v_1 = a_2v_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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Quellenhinweis[Bearbeiten]

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