Nichtdeterministische Turingmaschine

Nichtdeterministische Turingmaschine

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

Inhaltsverzeichnis

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 c1 = (u1,q1,a1,v1) und c2 = (u2,q2,a2,v2) gilt c_1\Rightarrow_M c_2 genau dann wenn eine der folgenden Bedingungen erfüllt ist (ε steht hier für das leere Wort):

  • u1 = u2, v1 = v2 und (q_1,a_1,q_2,a_2,n)\in\Delta oder
  • es gibt ein a\in \Gamma, so dass u1 = u2 = ε, av1 = v2, a_2=\square und (q_1,a_1,q_2,a,l)\in\Delta oder
  • es gibt ein a\in \Gamma, so dass u1 = u2a2, av1 = v2 und (q_1,a_1,q_2,a,l)\in\Delta oder
  • es gibt ein a\in \Gamma, so dass u1a = u2, v1 = v2 = ε, a_2=\square und (q_1,a_1,q_2,a,r)\in\Delta oder
  • es gibt ein a\in \Gamma, so dass u1a = u2, v1 = a2v2 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 c0 die Anfangskonfiguration auf w ist, cn 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 cn 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 c0 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

Quellenhinweis

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

Wikimedia Foundation.

См. также в других словарях:

  • Turingmaschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Theoretischen Informatik. Das Modell wurde im… …   Deutsch Wikipedia

  • Turingmaschine mit Zusatzeingabe — Eine Turingmaschine mit Zusatzeingabe ist ein zu Nichtdeterministischen Turingmaschinen äquivalentes Berechnungsmodell der Theoretischen Informatik. Inhaltsverzeichnis 1 Informelle Beschreibung 2 Definition 2.1 Turingmaschine mit Zusatzeingabe …   Deutsch Wikipedia

  • Universelle Turingmaschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Orakel-Turingmaschine — Eine Orakel Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine black box vorstellen, die von der Turingmaschine befragt werden kann und ein Problem in einem Schritt löst. Der… …   Deutsch Wikipedia

  • Alternierende Turingmaschine — In der theoretischen Informatik ist eine alternierende Turing Maschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle… …   Deutsch Wikipedia

  • Turing-Maschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Turingmodell — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • P!=NP — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia

  • P/NP-Problem — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia

  • P=NP — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»