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

Definition

Turingmaschine mit Zusatzeingabe

Eine Turingmaschine mit Zusatzeingabe ist ein 5-Tupel M = (Q,Σ,Γ,δ,s), wobei

Zustandsmenge

$Q\not= \emptyset$ eine endliche nicht-leere Menge von Zuständen,

Arbeitsalphabet

Γ das Arbeitsalphabet mit dem leeren Zeichen $\sqcup \in \Gamma$, dem linken Rand $\triangleright \in \Gamma$ und dem Trennsymbol $\#$,

Eingabealphabet

$Sigma \subseteq \Gamma\setminus \{\triangleright,\sqcup,\# \}$ das Eingabealphabet,

Überführungsfunktion

$\delta: Q \times \Gamma \rightarrow (Q \cup \{+,-\}) \times \Gamma \times \{\leftarrow,\downarrow,\rightarrow\}$ die Überführungsfunkiton und

Startzustand

$s \in Q$ ein ausgezeichneter Startzustand.

Die Überführungsfunktion wird eingeschränkt, damit der linke Rand nicht überschrieben werden kann. Es gilt also für alle $q\in Q: \delta(q,\triangleright) = (q',\triangleright,d)$ mit $q'\in Q$ und $d \in \{\downarrow,\rightarrow\}$.

Konfiguration

Eine Konfiguration von M ist ein 4-Tupel (q,u,σ,v) mit $q \in Q \cup \{+,-\}$ der aktuelle Zustand, $u \in \Gamma^*$ der String links vom Kopf, $\sigma\in\Gamma$ das Zeichen am Kopf und $v \in \Gamma^*$ der String rechts vom Kopf.

Nachfolgekonfiguration

Sind K = (q,u,σ,v) und K' = (q',u',σ',v') zwei Konfigurationen, dann ist K' die Nachfolgekonfiguration von K (schreibe $K\vdash K'$) genau dann, wenn δ(q,σ) = (q',τ,d) mit

• $d = \downarrow, u' = u,v'=v,\sigma'=\tau$, oder
• $d = \leftarrow, u'\sigma' = u, v'=\tau v$, oder
• $d = \rightarrow, u' = u\tau, \sigma' v' = v$, oder
• $d = \rightarrow, u' = u\tau, v = v' = \epsilon$ und $\sigma' = \sqcup$.

Schreibe $K \vdash^* K'$ für Konfigurationen K und K', wenn es eine Konfigurationenfolge $K_1,\ldots,K_m$ gibt mit $K\vdash K_1 \vdash \ldots \vdash K_m \vdash K'$.

Berechnung

Die Startkonfiguration von M bei Eingabe $(x,y) \in \Sigma^*$ ist $K_0 = (s,\epsilon, \triangleright,x\# y)$. Eine Konfiguration K_m = (q,u,σ,v) heißt Haltekonfiguration, falls $q \in \{+,-\}$. Dann heißt die Konfigurationenfolge $K_0,\ldots,K_m$ Berechnung von M, falls $K_i \vdash K_{i+1}$ für alle $i \in \{0, \ldots, m-1\}$. M akzeptiert die Eingabe, falls K_m = ( + ,u,σ,v) und lehnt ab, falls K_m = ( − ,u,σ,v).

Laufzeit

Sei $K_0, \ldots, K_m$ eine Berechnung von M bei Eingabe x, dann ist die Laufzeit t_M(x) = m. Falls keine Berechnung zur Eingabe x existiert (die Turingmaschine also nicht hält), gilt $t_M(x) = \bot$.

Bei Turingmaschinen betrachtet man als Eingabegröße die Länge des Eingabestrings. Eine Funktion $T:\mathbb{N} \rightarrow \mathbb{N}$ heißt dann Zeitschranke von M, falls $t_M(x) \in \mathcal{O}(T(|x|))$ für alle $x \in \Sigma^*$ gilt.

erzeugte Sprache

Jede Turingmaschine mit Zusatzeingabe M erzeugt eine Sprache $L(M) = \{x \in \Sigma^* \mid M \text{ akzeptiert } x\}$ – die Menge der von M 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 k-String-Turingmaschine M = (Q,Σ,Γ,δ,s) mit Zusatzeingabe unterscheidet sich in den folgenden Begriffen von der Turingmaschine mit Zusatzeingabe:

Überführungsfunktion

$\delta : Q\times \Gamma^k \rightarrow (Q\cup \{+,-\}) \times \Gamma^k \times \{\leftarrow, \downarrow, \rightarrow\}^k$ Der nächste Zustand hängt von dem aktuellen Zustand und dem aktuellen Zeichen aller Bänder ab.

String-Zeiger-Beschreibung

$(u,\sigma,v), u,v\in \Gamma^*,\sigma\in\Gamma$ ist ein Hilfsbegriff und gibt an, dass der Lese-/Schreibkopf auf dem Zeichen σ steht, links davon der String u und rechts davon v.

Konfiguration

$(q,s_1,\ldots,s_k)$ besteht aus einem Zustand $q\in Q$ und einer String-Zeiger-Beschreibung $s_1,\ldots,s_k$ für jedes Band mit s_i = (u_i,σ_i,v_i).

Startkonfiguration

$K_0 = (s,(\varepsilon,\triangleright,x\# y), (\varepsilon,\triangleright,\varepsilon), \ldots, (\varepsilon,\triangleright,\varepsilon))$ bei Eingabe $x\# y$.

Nachfolgekonfiguration

$K'=(q',s_1',\ldots,s_k')$ ist Nachfolgekonfiguration von $K=(q,s_1,\ldots,s_k)$, falls $\delta(q,\sigma_1, \ldots,\sigma_k) = (q',\tau_1,\ldots,\tau_k,d_1,\ldots,d_k)$ und für alle i gilt:

• $d_i = \downarrow, u_i' = u_i,v_i'=v_i,\sigma_i'=\tau_i$, oder
• $d_i = \leftarrow, u_i'\sigma_i' = u_i, v_i'=\tau_i v_i$, oder
• $d_i = \rightarrow, u_i' = u_i\tau_i, \sigma_i' v_i' = v_i$, oder
• $d_i = \rightarrow, u_i' = u_i\tau_i, v_i = v_i' = \epsilon$ und $\sigma_i' = \sqcup$.

Äquivalenz zur 1-String-Turingmaschine mit Zusatzeingabe

Passend zur Church-Turing-These, bzw. deren erweiterten Version, gibt es zu jeder k-String-Turingmaschine mit Zusatzeingabe M und Zeitschranke T, eine 1-String-Turingmaschine mit Zusatzeingabe, die L(M) mit Zeitschranke $\mathcal{O}(T^2)$ 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 k-String-Turingmaschine mit Zusatzeingabe und nur-lesen Eingabeband ist eine k-String Turingmaschine mit Zusatzeingabe M = (Q,Σ,Γ,δ,s) und der Einschränkung von δ durch: Ist $\delta(q,\sigma_1,\ldots,\sigma_k) = (q',\sigma_1', \ldots, \sigma_k', d_1, \ldots, d_k)$, so ist σ₁ = σ₁' (das Eingabeband wird nicht verändert) und falls $\sigma_1 = \sqcup$, dann ist $d_1=\leftarrow$ (die Turingmaschine kann nicht über den rechten Rand der Eingabe hinaus laufen).

Speicherplatzaufwand

Der Speicherplatzaufwand einer k-String-Turingmaschine mit Zusatzeingabe und nur-lesen Eingabeband M bei Eingabe $x\# y$ und Haltekonfiguration $(q,(u_1,\sigma_1,v_1),\ldots,(u_k,\sigma_k,v_k))$ ist $s_M(x\# y) = \Sigma_{i=2}^k |u_i\sigma_iv_i|$.

Eine Funktion $S:\mathbb{N} \rightarrow \mathbb{R}$ ist dann eine Platzschranke für M, falls $s_M(x) \in \mathcal{O}(S(|x|))$.

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 M bei Eingabe x 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 x genau dann, wenn es eine akzeptierende Berechnung bei Eingabe x 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) für Zeitschranken f gebildet.

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

$\mbox{NP} = \bigcup_{k \in \mathbb{N}} \mbox{NTIME}\left(n^k\right)$

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

$\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}\left(2^{n^k}\right).$

NSPACE

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

NSPACE_k(S) ist die Menge aller Sprachen L, für die es eine k-String-Turingmaschine mit Zusatzeingabe und nur-lesen Eingabeband gibt, die L mit Platzschranke S entscheidet und damit wird dann $\mbox{NSPACE}(S) = \bigcup_{k\geq 2}\mbox{NSPACE}_k(S)$ gebildet.

Darüber werden die Klassen

• NL, logarithmischer Platz, mit NL = NSPACE(log n),
• NPSPACE, polynomieller Platz, mit $\mbox{NPSPACE} = \bigcup_{k \in \mathbb{N}} \mbox{NSPACE}\left(n^k\right)$ und
• NEXPTIME, exponentieller Platz, mit $\mbox{NEXPTIME} = \bigcup_{k \in \mathbb{N}} \mbox{NSPACE}\left(2^{n^k}\right)$ gebildet.

Literatur

• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. 1 Auflage. Cambridge University Press, 2009, ISBN 0521424267.
• Vorlesung Komplexitätstheorie WS 09/10, Prof. Dr. Thomas Schwentick