Alternierende Turingmaschine

In der theoretischen Informatik ist eine alternierende Turingmaschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle und universelle Zustände aufgeteilt. Erste akzeptieren eine Eingabe, wenn es eine mögliche Berechnung gibt, die akzeptiert, während zweite nur dann akzeptieren, wenn alle möglichen Berechnung akzeptieren.

Informelle Beschreibung

Da es sich bei alternierenden Turingmaschinen um nichtdeterministische Maschinen handelt, gibt es für jede Konfiguration der Maschine mehrere Möglichkeiten, die Berechnung fortzusetzen. Um Klassen wie NP zu definieren, geht man davon aus, dass eine Eingabe akzeptiert wird, wenn eine Berechnung existiert, die diese akzeptiert. Um dann andererseits Maschinen für coNP Probleme zu definieren, geht man davon aus, dass ein Wort nur dann akzeptiert wird, wenn alle möglichen Berechnungen akzeptieren.

Alternierende Maschinen kombinieren diese beiden Modi, indem die Zustände in existentielle und universelle Zustände aufgeteilt werden. Hat eine Konfiguration einen existentiellen Zustand, dann wird sie als akzeptierend angesehen, sobald nur eine Nachfolger-Konfiguration akzeptiert, während eine Konfiguration mit einem universellen Zustand nur akzeptiert, wenn alle Nachfolger-Konfigurationen akzeptieren. Eine Eingabe wird akzeptiert, wenn die dazugehörige Anfangskonfiguration akzeptiert.

Formale Definition

Eine alternierende Turing-Maschine mit k-Bändern ist ein Tupel $A=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,g)$ mit

• $Q$ ist eine endliche nichtleere Menge (Menge der Zustände)
• $\Sigma$ ist eine endliche nichtleere Menge (Eingabealphabet)
• $\Gamma$ ist eine endliche nichtleere Menge (Bandalphabet), wobei $\Gamma \supseteq \Sigma$
• $\delta \subseteq Q\times \Gamma ^{k}\times Q\times \Gamma ^{k}\times \{L,N,R\}^{k}$ ist die Übergangsrelation
• $q_{0}\in Q$ ist der Startzustand
• $\square \in \Gamma$ ist das Blank-Symbol
• $g\colon Q\rightarrow \{\wedge ,\vee ,\operatorname {accept} ,\operatorname {reject} \}$ eine Funktion, die jedem Zustand einen Typ zuordnet

Akzeptanz von Eingaben

Nun betrachtet man eine Konfiguration $C$ einer solchen Maschine mit Zustand $q\in Q$:

• Wenn $g(q)=\operatorname {accept}$, dann ist $C$ eine akzeptierende (End)Konfiguration.
• Wenn $g(q)=\operatorname {reject}$, dann ist $C$ eine nicht-akzeptierende (End)Konfiguration.
• Wenn $g(q)=\wedge$, dann ist $C$ eine akzeptierende Konfiguration genau dann, wenn alle Nachfolger Konfigurationen akzeptierende Konfigurationen sind. Anderenfalls ist $C$ eine nicht-akzeptierende Konfiguration.
• Wenn $g(q)=\vee$ dann ist $C$ eine akzeptierende Konfiguration, wenn es eine akzeptierende Nachfolger Konfiguration gibt. Anderenfalls ist $C$ eine nicht-akzeptierende Konfiguration.

Eine alternierende Turing-Maschine akzeptiert eine Eingabe genau dann, wenn die Anfangskonfiguration eine akzeptierende Konfiguration ist.

Komplexitätstheorie

Wie bei deterministischen und nicht deterministischen Turingmaschinen kann man auch für Alternierende Turingmaschinen Zeit und Platzkomplexität definieren.

Um den Wert einer Konfiguration zu berechnen, müssen nicht zwangsläufig alle Nachfolger ausgewertet werden. Eine existentielle Konfiguration ist sicher akzeptierend, sobald ein Nachfolger akzeptiert (unabhängig von den Wert der restlichen Nachfolger), und eine universelle Konfiguration ist nicht-akzeptierend, sobald ein Nachfolger nicht akzeptiert. Bei einer effizienten Berechnung müssen also nicht alle Konfigurationen ausgewertet werden, und dies wird auch in den folgenden Definitionen von $ATIME$ und $ASPACE$ berücksichtigt.

Eine ATM $A$, die eine Sprache $L$ entscheidet, entscheidet diese in Zeit $t(n)$, wenn für jede Eingabe $x$ alle Berechnungspfade aus ausgewerteten Konfigurationen nicht länger sind als $t(|x|)$. Die Menge aller Sprachen, die von einer ATM in Zeit $t(n)$ entschieden werden können, wird als $ATIME(t(n))$ notiert.

Eine ATM $A$, die eine Sprache $L$ entscheidet, entscheidet diese in Platz $s(n)$ wenn für jede Eingabe $x$ alle ausgewerteten Konfigurationen auf allen Bändern nicht mehr als $s(|x|)$ Zellen benutzen. Die Menge aller Sprachen, die von einer ATM in Platz $s(n)$ entschieden werden können, wird als $ASPACE(s(n))$ notiert.

Komplexitätsklassen

Folgende unter (log n)-Reduktionen abgeschlossene Komplexitätsklassen über ATMs sind üblich:

• $ALOGSPACE=ASPACE(\log n)$ Alternierender logarithmischer Platz
• $AP=\bigcup _{k>0}ATIME(n^{k})$ Alternierende Polynomialzeit
• $APSPACE=\bigcup _{k>0}ASPACE(n^{k})$ Alternierender polynomieller Platz
• $AEXPTIME=\bigcup _{k>0}ATIME(k^{n})$ Alternierende exponentielle Zeit

Zusammenhang mit anderen Maschinenmodellen

Es gelten folgende Zusammenhänge zwischen alternierender und deterministischen Komplexität:

$ATIME(f(n))\subseteq SPACE(f(n))\qquad \qquad f(n)\geq n$

$ASPACE(f(n))=\bigcup _{c>0}TIME(c^{f(n)})\qquad \qquad f(n)\geq \log {n}$

Insbesondere korrespondieren die oben definierten Komplexitätsklassen mit den üblichen deterministischen Komplexitätsklassen:

• ALOGSPACE = Ptime
• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE

Weiter kann man ATMs auch verwenden, um die Klasse LOGCFL zu charakterisieren.

Begrenzte Alternierungen

Man kann auch alternierende Turingmaschinen betrachten, die nur eine begrenzte Anzahl an Wechseln zwischen existentiellen und universalen Zuständen durchführen können. Man definiert $\Sigma _{i}TIME(t(n))$ (bzw. $\Pi _{i}TIME(t(n))$) als die Menge aller Sprachen, die von einer ATM in Zeit $t(n)$ entschieden werden, deren Anfangszustand ein existentieller (bzw. universeller) Zustand ist, und auf jedem möglichen Berechnungspfad höchstens $i-1$ Mal zwischen existentiellen und universellen Zuständen wechselt.

Alternierende Turingmaschinen mit begrenzten Alternierungen haben einen engen Bezug zur Polynomialzeithierarchie. Es gilt nämlich:

• $\Sigma _{i}^{p}=\bigcup _{k\in \mathbb {N} }\Sigma _{i}TIME(n^{k})$
• $\Pi _{i}^{p}=\bigcup _{k\in \mathbb {N} }\Pi _{i}TIME(n^{k})$

Siehe auch

• Turingmaschine
• Nichtdeterministische Turingmaschine
• Orakel-Turingmaschine

Literatur

• A. K. Chandra, D. C. Kozen, L. J. Stockmeyer: Alternation. In: Journal of the ACM. Volume 28, Issue 1, 1981, S. 114–133.
• Alternation. In: Christos Papadimitriou: Computational Complexity. 1. Auflage. Addison-Wesley, 1993, ISBN 0-201-53082-1, Kapitel 16.2, S. 399–401.