Alternierende Turingmaschine

In der theoretischen Informatik ist eine alternierende Turing-Maschine (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. Erstere akzeptieren eine Eingabe, wenn es eine mögliche Berechnung gibt, die akzeptiert, während zweitere nur dann akzeptieren, wenn alle möglichen Berechnung akzeptieren.

Informelle Beschreibung

Da es sich bei alternierenden Turing Maschinen 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)
• Σ ist eine endliche nichtleere Menge (Eingabealphabet)
• Γ 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$ ist das Blank-Symbol ($\square \in \Gamma$)
• $g: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 nicht Nachfolger akzeptiert. Bei einer effizienten Berechnung müssen also nicht alle Konfigurationen ausgewertet werden, 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

Zusammengang 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

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

Siehe auch

• Turingmaschine
• Nichtdeterministische Turingmaschine
• Orakel-Turingmaschine

Referenzen

• 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, S. Kapitel 16.2, S. 399–401.