Turingmaschine mit Zusatzeingabe

Eine Turingmaschine mit Zusatzeingabe ist ein zu nichtdeterministischen Turingmaschinen äquivalentes Berechnungsmodell der theoretischen Informatik.

Informelle Beschreibung

Eine Turingmaschine mit Zusatzeingabe ist eine Erweiterung der deterministischen Turingmaschine um eine Zusatzeingabe . Es handelt sich also immer noch um eine Maschine, die auf einem String-Band arbeitet und mit einem Lese-/Schreibkopf den Inhalt Zeichenweise lesen und ändern kann. Dabei werden abhängig vom Zeichen am Lesekopf und dem aktuellen Zustand der Maschine verschiedene Zustände durchlaufen. Jede Turingmaschine kann zwei ausgezeichnete Zustände und annehmen. Wenn eine Turingmaschine in den Zustand wechselt, endet die Berechnung und die Eingabe wurde akzeptiert. Wenn die Turingmaschine in den Zustand wechselt, endet die Berechnung ebenfalls und die Eingabe wird abgelehnt.

Eine Turingmaschine mit Zusatzeingabe bekommt ein String-Tupel als Eingabe. akzeptiert , wenn es eine Zusatzeingabe gibt, so dass die Eingabe akzeptiert. Die Idee hinter dieser Konstruktion ist, dass als Eingabe für ein Problem betrachtet wird und als Lösung. Die Turingmaschine kann dann versuchen zu verifizieren, ob wirklich eine Lösung für ist. In diesem Sinne wird also akzeptiert, wenn es eine Lösung für das (durch konkrete) Problem gibt.

Definition

Turingmaschine mit Zusatzeingabe

Eine Turingmaschine mit Zusatzeingabe ist ein 5-Tupel , wobei

Zustandsmenge
eine endliche nicht-leere Menge von Zuständen,
Arbeitsalphabet
das Arbeitsalphabet mit dem leeren Zeichen , dem linken Rand und dem Trennsymbol ,
Eingabealphabet
das Eingabealphabet,
Überführungsfunktion
die Überführungsfunktion und
Startzustand
ein ausgezeichneter Startzustand ist.

Die Überführungsfunktion wird eingeschränkt, damit der linke Rand nicht überschrieben werden kann. Es gilt also für alle mit und .

Konfiguration

Eine Konfiguration von ist ein 4-Tupel mit der aktuelle Zustand, der String links vom Kopf, das Zeichen am Kopf und der String rechts vom Kopf.

Nachfolgekonfiguration

Sind und zwei Konfigurationen, dann ist die Nachfolgekonfiguration von (schreibe ) genau dann, wenn mit

  • , oder
  • , oder
  • , oder
  • und .

Schreibe für Konfigurationen und , wenn es eine Konfigurationenfolge gibt mit .

Berechnung

Die Startkonfiguration von bei Eingabe ist . Eine Konfiguration heißt Haltekonfiguration, falls . Dann heißt die Konfigurationenfolge Berechnung von , falls für alle . akzeptiert die Eingabe, falls und lehnt ab, falls .

Laufzeit

Sei eine Berechnung von bei Eingabe , dann ist die Laufzeit . Falls keine Berechnung zur Eingabe existiert (die Turingmaschine also nicht hält), gilt .

Bei Turingmaschinen betrachtet man als Eingabegröße die Länge des Eingabestrings. Eine Funktion heißt dann Zeitschranke von , falls für alle gilt.

Erzeugte Sprache

Jede Turingmaschine mit Zusatzeingabe erzeugt eine Sprache – die Menge der von akzeptierten Eingaben.

Mehrstring Turingmaschine

Die Turingmaschine mit Zusatzeingabe lässt sich erweitern, indem man die Benutzung mehrerer String-Bänder erlaubt. Die Maschine hat dann für jedes Band einen eigenen Lese-/Schreibkopf. Die Definition einer -String-Turingmaschine mit Zusatzeingabe unterscheidet sich in den folgenden Begriffen von der Turingmaschine mit Zusatzeingabe:

Überführungsfunktion
Der nächste Zustand hängt von dem aktuellen Zustand und dem aktuellen Zeichen aller Bänder ab.
String-Zeiger-Beschreibung
ist ein Hilfsbegriff und gibt an, dass der Lese-/Schreibkopf auf dem Zeichen steht, links davon der String und rechts davon .
Konfiguration
besteht aus einem Zustand und einer String-Zeiger-Beschreibung für jedes Band mit .
Startkonfiguration
bei Eingabe .
Nachfolgekonfiguration
ist Nachfolgekonfiguration von , falls und für alle gilt:
  • , oder
  • , oder
  • , oder
  • und .

Äquivalenz zur 1-String-Turingmaschine mit Zusatzeingabe

Passend zur Church-Turing-These, bzw. deren erweiterten Version, gibt es zu jeder -String-Turingmaschine mit Zusatzeingabe und Zeitschranke , eine 1-String-Turingmaschine mit Zusatzeingabe, die mit Zeitschranke entscheidet. Man kann also jede Mehrstring-Turingmaschine mit Zusatzeingabe mit polynomiellem Mehraufwand in eine Einstring-Turingmaschine umwandeln.

Bei der Konstruktion von Turingmaschinen mit Zusatzeingabe und polynomieller Laufzeit spielt es also keine Rolle, ob man sie als Mehrstring- oder Einstring-Turingmaschine definiert. In diesem Fall kann man die Mehrstring-Turingmaschine so definieren, dass die Eingabe auf dem ersten Band steht und die Zusatzeingabe auf dem Zweiten, was die Beschreibung der Turingmaschine erleichtert.

Platzschranke

Bei Mehrstring-Turingmaschinen lässt sich zusätzlich zur Zeitschranke auch eine Platzschranke definieren. Um auch Platzschranken definieren zu können die kleiner als die Eingabelänge sind, muss das Modell so eingeschränkt werden, dass die Eingabe (und die Zusatzeingabe) nicht als Berechnungsplatz benutzt werden können.

Nur-lesen Eingabeband

Eine -String-Turingmaschine mit Zusatzeingabe und nur-lesen Eingabeband ist eine -String Turingmaschine mit Zusatzeingabe und der Einschränkung von durch: Ist , so ist (das Eingabeband wird nicht verändert) und falls , dann ist (die Turingmaschine kann nicht über den rechten Rand der Eingabe hinauslaufen).

Speicherplatzaufwand

Der Speicherplatzaufwand einer -String-Turingmaschine mit Zusatzeingabe und nur-lesen Eingabeband bei Eingabe und Haltekonfiguration ist .

Eine Funktion ist dann eine Platzschranke für , falls .

Raten von Lösungen

Oft spricht man im Zusammenhang mit Nichtdeterminismus vom „raten“. Da es sich hier ebenfalls um eine Form von Nichtdeterminismus handelt (die Wahlfreiheit der Zusatzeingabe) wird oft vom raten der Lösung als Zusatzeingabe gesprochen. Gemeint ist, dass die Turingmaschine mit Zusatzeingabe bei Eingabe die Zusatzeingabe als Lösungskandidat interpretieren kann und ablehnt, falls es sich nicht um eine Lösung handelt. Die Turingmaschine wird also so konstruiert, dass richtig geratene Lösungen akzeptiert werden und alles andere abgelehnt wird. In diesem Sinne kann die Zusatzeingabe/Lösung geraten werden.

Äquivalenz zur nichtdeterministischen Turingmaschine

Die Turingmaschine mit Zusatzeingabe ist äquivalent zur nichtdeterministischen Turingmaschine, bei der die deterministische Turingmaschine durch eine Übergangsrelation statt einer Übungsfunktion erweitert wird. Dadurch kann es von einer Konfiguration der nichtdeterministischen Turingmaschine mehrere gültige Nachfolgezustände geben. Dieses Modell akzeptiert eine Eingabe genau dann, wenn es eine akzeptierende Berechnung bei Eingabe gibt.

Gewissermaßen besteht bei der Turingmaschine mit Zusatzeingabe die Wahlfreiheit in der Zusatzeingabe und bei der nichtdeterministischen Turingmaschine in der Wahl der Nachfolgekonfiguration. Zur Simulation der nichtdeterministischen Turingmaschine durch die Turingmaschine mit Zusatzeingabe können die Zeichen der Zusatzeingabe verwendet werden, um die nächste Konfiguration der nichtdeterministischen Turingmaschine eindeutig (bezogen auf die konkrete Zusatzeingabe) zu bestimmen. Zur Simulation der Turingmaschine mit Zusatzeingabe durch die nichtdeterministische Turingmaschine können die Zeichen der Zusatzeingabe durch die möglichen Nachfolgekonfigurationen bestimmt werden (für jedes mögliche Zeichen der Zusatzeingabe gibt es eine mögliche Nachfolgekonfiguration).

Vorteil gegenüber der nichtdeterministischen Turingmaschine

Die Beschreibung und Formalisierung nichtdeterministischer Turingmaschinen wird durch dieses Modell vereinfacht, da man explizit auf einen Lösungskandidaten (der Zusatzeingabe) zurückgreifen kann.

Besonders bei der Charakterisierung von NP wird die Bedeutung dieses Modells deutlich: Die Menge NP ist intuitiv betrachtet die Menge der Probleme, deren Lösung (gegeben durch die Zusatzeingabe) sich in polynomieller Zeit verifizieren lässt.

Bedeutung in der Komplexitätstheorie

NTIME

Durch die Turingmaschine mit Zusatzeingabe und dem zugehörigen Laufzeitbegriff werden die nichtdeterministischen Zeitklassen NTIME für Zeitschranken gebildet.

Darüber wird auch NP definiert, die Menge aller Sprachen zu denen es eine Turingmaschine mit Zusatzeingabe und polynomieller Laufzeitschranke gibt, so dass ( entscheidet ).

Auch NEXPTIME ist auf diese Weise definiert. Die Menge aller Sprachen zu denen es eine Turingmaschine mit Zusatzeingabe und exponentieller Laufzeitschranke gibt, so dass .

NSPACE

Mit der Erweiterung auf Mehrstring-Turingmaschinen mit Zusatzeingabe und nur-lesen Eingabeband lassen sich die NSPACE-Klassen definieren.

ist die Menge aller Sprachen , für die es eine k-String-Turingmaschine mit Zusatzeingabe und nur-lesen Eingabeband gibt, die mit Platzschranke entscheidet und damit wird dann gebildet.

Darüber werden die Klassen

  • NL, logarithmischer Platz, mit ,
  • NPSPACE, polynomieller Platz, mit und
  • NEXPTIME, exponentieller Platz, mit gebildet.

Literatur