Nichtdeterministische Turingmaschine

aus Wikipedia, der freien Enzyklopädie

Eine Nichtdeterministische Turingmaschine (NTM) in der Theoretischen Informatik ist eine Turingmaschine, deren Kontrollmechanismen wie ein Nichtdeterministischer Endlicher Automat (NEA) arbeitet.

Inhaltsverzeichnis 1 Beschreibung 2 Definition 2.1 Definition der Semantik 3 Äquivalenz zu DTMs 4 Bedeutung 5 Vergleich zu anderen Rechner-/Automatenmodellen 6 References

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

[Bearbeiten] Definition

Eine nichtdeterministische Turingmaschine (kurz: NTM ) ist ein Tupel , wobei

• Q ist eine endliche nichtleere Menge (Menge der Zustände)
• Σ ist eine endliche nichtleere Menge (Eingabealphabet)
• Γ ist eine endliche nichtleere Menge (Bandalphabet), wobei
• ist die Übergangsrelation
• ist der Startzustand
• ist das Blank-Symbol ()
• ist die Menge der Endzustände

[Bearbeiten] Definition der Semantik

Eine Konfiguration der NTM M ist ein Tupel (u,q,a,v), wobei , , und (für eine Definition von Γ ^* siehe Kleenesche Hülle). Intuitiv bedeudet 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 aufweißt (auch hier wird wieder nur der endliche Teil betrachtet, der alle Nicht-Blank-Symbole enthält). Die Menge der Konfigurationen von M sei mit conf(M) bezeichnet. Wir definieren eine binäre Relation auf conf(M) (genannt Konfigurationsübergangsrelation) wie folgt:

Für zwei Konfigurationen c₁ = (u₁,q₁,a₁,v₁) und c₂ = (u₂,q₂,a₂,v₂) gilt genau dann wenn eine der folgenden Bedingungen erfüllt ist ( steht hier für das leere Wort):

• u₁ = u₂, v₁ = v₂ und oder
• es gibt ein , so dass , av₁ = v₂, und oder
• es gibt ein , so dass u₁ = u₂a₂, av₁ = v₂ und oder
• es gibt ein , so dass u₁a = u₂, , und oder
• es gibt ein , so dass u₁a = u₂, v₁ = a₂v₂ und .

Die Anfangskonfiguration von M auf dem Eingabewort ist die Konfiguration . Eine Konfiguration c = (u,q,a,v) heißt Endkonfiguration, wenn . Ist c eine Endkonfiguration, dann heißt sie akzeptierende Endkonfiguration, wenn , ansonsten heißt sie nicht-akzeptierende Endkonfiguration.

Ein endlicher Lauf von M auf dem Eingabewort w ist eine endliche Sequenz von Konfigurationen, wobei c₀ die Anfangskonfiguration auf w ist, c_n eine Endkonfiguration und für jede natürliche Zahl i mit gilt: . 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 von Konfigurationen, wobei c₀ die Anfangskonfiguration auf w ist und für jede natürliche Zahl i mit gilt: .

Eine NTM, die keinen unendlichen Lauf hat, nennt sich Entscheider. Sei M ein Entscheider. Die von M akzeptierte Sprache ist definiert als es gibt einen akzeptierenden Lauf von M auf w}.

[Bearbeiten] Äquivalenz zu DTMs

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 einem NTM erkannte Sprache auch von einem DTM erkannt werden. Der DTM simuliert alle Übergänge des NTMs, indem er 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).

[Bearbeiten] Bedeutung

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 die meisten 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.

[Bearbeiten] Vergleich zu anderen Rechner-/Automatenmodellen

Es ist eine allgemeine Fehleinschätzung, dass Quantencomputer NTMs entsprächen. NTMs können NP-vollständige Probleme lösen, Quantencomputer aber nicht.

[Bearbeiten] References

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