Alternierende Turingmaschine

Rechnermodell der theoretischen Informatik. Eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert.

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

Bearbeiten

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

Bearbeiten

Eine alternierende Turing-Maschine mit k-Bändern ist ein Tupel   mit

  •   ist eine endliche nichtleere Menge (Menge der Zustände)
  •   ist eine endliche nichtleere Menge (Eingabealphabet)
  •   ist eine endliche nichtleere Menge (Bandalphabet), wobei  
  •   ist die Übergangsrelation
  •   ist der Startzustand
  •   ist das Blank-Symbol
  •   eine Funktion, die jedem Zustand einen Typ zuordnet

Akzeptanz von Eingaben

Bearbeiten

Nun betrachtet man eine Konfiguration   einer solchen Maschine mit Zustand  :

  • Wenn  , dann ist   eine akzeptierende (End)Konfiguration.
  • Wenn  , dann ist   eine nicht-akzeptierende (End)Konfiguration.
  • Wenn  , dann ist   eine akzeptierende Konfiguration genau dann, wenn alle Nachfolger Konfigurationen akzeptierende Konfigurationen sind. Anderenfalls ist   eine nicht-akzeptierende Konfiguration.
  • Wenn   dann ist   eine akzeptierende Konfiguration, wenn es eine akzeptierende Nachfolger Konfiguration gibt. Anderenfalls ist   eine nicht-akzeptierende Konfiguration.

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

Komplexitätstheorie

Bearbeiten

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   und   berücksichtigt.

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

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

Komplexitätsklassen

Bearbeiten

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

  •   Alternierender logarithmischer Platz
  •   Alternierende Polynomialzeit
  •   Alternierender polynomieller Platz
  •   Alternierende exponentielle Zeit

Zusammenhang mit anderen Maschinenmodellen

Bearbeiten

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

 
 

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

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

Begrenzte Alternierungen

Bearbeiten

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   (bzw.  ) als die Menge aller Sprachen, die von einer ATM in Zeit   entschieden werden, deren Anfangszustand ein existentieller (bzw. universeller) Zustand ist, und auf jedem möglichen Berechnungspfad höchstens   Mal zwischen existentiellen und universellen Zuständen wechselt.[1]

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

  •  
  •  

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • 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.

Einzelnachweise

Bearbeiten
  1. Barak, Boaz.: Computational complexity : a modern approach. Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4, S. 99–100 (Draft [PDF; abgerufen am 31. August 2020]).