Wikipedia · einfach zusammengefasst · Stand
Nichtdeterministische Turingmaschine
Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine …
Inhalt5 Abschnitte
Grundidee und Arbeitsweise
Eine nichtdeterministische Turingmaschine (NTM oder NDTM) ist ein theoretisches Modell der Informatik. Anders als eine deterministische Turingmaschine (DTM) verwendet sie keine Übergangsfunktion, sondern eine Übergangsrelation.
Bei einer DTM legen der aktuelle Zustand und das gelesene Bandsymbol eindeutig fest, welches Symbol geschrieben wird, wohin sich der Lese-/Schreibkopf bewegt und in welchen Zustand die Maschine wechselt. Bei einer NTM können zu derselben Situation mehrere mögliche Übergänge gehören. Deshalb kann sie für eine Eingabe viele mögliche Läufe haben. Dies lässt sich so deuten, als wähle sie zufällig einen Lauf aus oder führe alle möglichen Läufe parallel aus.
Eine Eingabe wird akzeptiert, wenn mindestens einer dieser Läufe akzeptierend endet. Da dieses Verhalten nach heutigem Kenntnisstand nicht unmittelbar realisierbar ist, ist die NTM ein theoretisches Maschinenmodell. Sie ist besonders in der Komplexitätstheorie wichtig.
Formaler Aufbau und Konfigurationen
Eine NTM ist das 7-Tupel M=(Q,Σ,Γ,δ,q₀,□,F). Dabei ist Q eine endliche, nichtleere Zustandsmenge, Σ ein endliches, nichtleeres Eingabealphabet und Γ ein endliches, nichtleeres Bandalphabet mit Γ ⊃ Σ. Der Startzustand ist q₀∈Q, das Blank-Symbol erfüllt □∈Γ\Σ, und F⊆Q ist die Menge der Endzustände.
Die Übergangsrelation ist δ⊆((Q\F)×Γ)×(Q×Γ×{L,N,R}). Sie ordnet einem Zustand und einem gelesenen Symbol möglicherweise mehrere Möglichkeiten zu: neuer Zustand, zu schreibendes Symbol sowie Kopfbewegung nach links (L), ohne Bewegung (N) oder nach rechts (R).
Eine Konfiguration hat die Form (u,q,a,v), wobei u,v∈Γ* , q∈Q und a∈Γ. Sie beschreibt den Zustand q, das unter dem Kopf gelesene Symbol a, den endlichen relevanten Bandinhalt links davon u und rechts davon v. Nicht aufgeführte Bandfelder enthalten Blank-Symbole. Die Konfigurationsübergangsrelation ⇒M beschreibt einen einzelnen erlaubten Schritt entsprechend einer Regel aus δ; beim Bewegen des Kopfes werden die linken beziehungsweise rechten Bandteile angepasst.
Für ein Eingabewort w∈Σ* ist die Anfangskonfiguration c₀=(ε,q₀,□,w). Eine Konfiguration (u,q,a,v) ist eine Endkonfiguration, wenn q∈F. Sie ist akzeptierend, wenn außerdem a≠□ gilt; bei a=□ ist sie nicht akzeptierend.
Läufe, Entscheidung und akzeptierte Sprache
Ein endlicher Lauf auf w ist eine Folge c₀,c₁,…,cₙ von Konfigurationen. Er beginnt mit der Anfangskonfiguration, endet in einer Endkonfiguration und jeder Schritt erfüllt cᵢ₋₁⇒M cᵢ. Der Lauf ist akzeptierend, wenn seine Endkonfiguration akzeptierend ist; andernfalls ist er nicht akzeptierend.
Ein unendlicher Lauf ist entsprechend eine unendliche Folge von Konfigurationen mit erlaubten Übergängen. Eine NTM heißt Entscheider, wenn sie keinen unendlichen Lauf besitzt.
Für einen Entscheider M ist die akzeptierte Sprache definiert durch L_M={w∈Σ* | es gibt einen akzeptierenden Lauf von M auf w}. Entscheidend ist also die Existenz mindestens eines akzeptierenden Laufs.
Beziehung zu deterministischen Turingmaschinen
Jede DTM kann als NTM aufgefasst werden, weil ihre Übergangsfunktion eine spezielle Übergangsrelation ist. NTM sind daher mindestens so mächtig wie DTM.
Umgekehrt kann eine DTM jede von einer NTM erkannte Sprache erkennen. Sie simuliert dazu alle möglichen Übergänge der NTM, indem sie bei mehreren Möglichkeiten Kopien des simulierten Zustands erzeugt und diese parallel simuliert. Wird ein Problem von einer NTM in polynomieller Zeit gelöst, kann eine DTM es in exponentieller Zeit lösen. Nach dem Satz von Savitch gibt es außerdem eine DTM, die das Problem mit polynomiellem Speicheraufwand löst.
Bedeutung für P, NP und Komplexitätsklassen
Als effizient lösbar gelten Probleme, die in Polynomialzeit entschieden werden können. Probleme, die eine DTM in Polynomialzeit entscheidet, gehören zur Klasse P. Viele praktisch bedeutsame Probleme sind bisher nicht als Probleme in P nachgewiesen worden, lassen sich aber auf einer NTM in polynomieller Zeit entscheiden. Sie gehören zur Klasse NP.
Würde ein allgemeines Verfahren gefunden, das jede NTM in Polynomialzeit durch eine DTM simuliert, dann lägen diese Probleme ebenfalls in P. Es würde P=NP gelten. Dies ist bis heute nicht gelungen; die Frage heißt P-NP-Problem.
Nichtdeterministische Turingmaschinen dienen auch zur Definition weiterer Komplexitätsklassen. NTIME bezeichnet die Menge aller Zeitkomplexitätsklassen, die auf NTM zurückgeführt werden. NSPACE ist analog die Menge der Raumkomplexitätsklassen dieses Maschinentyps.
