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 
 
 Vorlesung Komplexitätstheorie WS 09/10, Prof. Dr. Thomas Schwentick

Automatentheorie