Orakel-Turingmaschine

Orakel-Turingmaschine

Eine Orakel-Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine black box vorstellen, die von der Turingmaschine befragt werden kann und ein Problem in einem Schritt löst. Der Begriff der Orakel-Turingmaschine dient in der Theoretischen Informatik dazu, Hierarchien von Berechenbarkeiten und Komplexitäten zu definieren und deren Eigenschaften zu studieren.

Durch geeignete Orakel kann man die Berechenbarkeit verstärken oder die Komplexität verringern. Zum Beispiel können Turingmaschinen mit dem Halteproblem als Orakel das Halteproblem für Turingmaschinen lösen. Turingmaschinen mit SAT als Orakel können jedes Problem aus NP in polynomialer Zeit lösen. Orakel werden auch verwendet, um Nichtdeterminismus deterministisch zu modellieren. Eine nichtdeterministische Turingmaschine kann nämlich als Schar von deterministischen Orakel-Turingmaschinen wiedergegeben werden. Der Scharparameter, das Orakel, drückt dabei die Folge der nichtdeterministischen Entscheidungen aus.

Inhaltsverzeichnis

Definition

Sei A\subseteq \Sigma^* eine Sprache über dem Alphabet \!\ \Sigma. Eine Orakel-Turingmaschine mit Orakel \!\ A ist eine Turingmaschine \!\ M mit einem zusätzlichen Eingabeband (Orakelband) und drei ausgezeichneten Zuständen: q_j,~ q_n,~ q_?. Schreibt \!\ M ein Wort w\in\Sigma^* auf das Orakelband und geht in den Zustand \!\ q_? über, so befragt \!\ M das Orakel: Der Nachfolgezustand von \!\ q_? sei \!\ q_j falls w\in A gilt und andernfalls \!\ q_n. Anschließend wird das Orakelband gelöscht.

Wenn \!\ T und \!\ K Klassen von Sprachen sind, dann bezeichnet \!\ T^K die Klasse der Sprachen, die von Turingmaschine \!\ M mit Orakel \!\ A akzeptiert werden, wobei L(M)\in T und A\in K sind. Typische Klassen sind einelementige Klassen, Komplexitätsklassen wie P oder NP, oder auch die Klasse aller rekursiv aufzählbaren Sprachen.

Beispiele:

  • \!\ P^{SAT} bezeichnet die Klasse der Sprachen, die von einer deterministischen, polynomiell zeitbeschränkten Turingmaschine mit Orakel \!\ SAT akzeptiert werden.
  • \!\ NP^{NP} bezeichnet die Klasse der Sprachen, die von einer nichtdeterministischen, polynomiell zeitbeschränkten Turingmaschine mit Orakel aus der Klasse \!\ NP akzeptiert werden.

Diese Komplexitätsklassen werden unter anderem dazu genutzt, um die Polynomialzeithierarchie zu definieren.

Eigenschaften

  • Für zwei Komplexitätsklassen T, K und eine Sprache L \in K gilt TK = TL, falls folgende Bedingungen erfüllt sind:
    1. L ist K-vollständig bezüglich einer Reduktion \preceq
    2. Die T zugrundeliegende Klasse von Turingmaschinen ist mächtig genug, die Reduktion \preceq zu berechnen

     Beispielsweise gilt PNP = PSAT, da SAT NP-vollständig bezüglich Polynomialzeitreduktion ist.

  • Jede Orakel-Turingmaschine hat mindestens die Fähigkeiten seiner Turingmaschine, seines Orakels und der Komplementsprache seines Orakels. Es gilt daher T \subseteq T^K, K \subseteq T^K und coK \subseteq T^K für alle Klassen T und K. Letztere Eigenschaft ergibt sich, wenn man die Zustände qj und qn vertauscht interpretiert. Insbesondere gilt also TK = TcoK
  • Für jede mittels deterministischer Turingmaschine definierte Komplexitätsklasse K und jede Oberklasse T \supseteq K gilt stets TK = T, denn anstatt das Orakel zu befragen, kann eine Turingmaschine die Antwort selbst berechnen. Auf diese Weise zeigt man z.B. PP = P und NPP = NP. Die Aussage lässt sich nicht auf nichtdeterministische Komplexitätsklassen verallgemeinern. Grund dafür ist die notwendige Eigenschaft K = coK der Orakelklasse K. Beispielsweise würde aus NPNP = NP die bisweilen ungeklärte Beziehung coNP = NP folgen (\overline{SAT} \in NP).

Zum Halteproblem

Man beachte, dass das Orakel in keiner Weise beschränkt ist. Auch Sprachen, die nicht entscheidbar sind, kommen als Orakel in Frage. Also kann man zum Beispiel das Halteproblem als Orakel verwenden. Solche Halteorakel-Turingmaschinen können offensichtlich das Halteproblem von Turingmaschinen (ohne Orakel) lösen. Das steht natürlich nicht im Widerspruch zum Unentscheidbarkeitresultat des Halteproblems, denn dieses besagt ja nur, dass es keine Turingmaschine ohne Orakel gibt, die das Problem löst. Allerdings ist auch das Halteproblem von Halteorakel-Turingmaschinen nicht durch Halteorakel-Turingmaschinen lösbar.

Die Konstruktion von immer stärkeren Orakel-Turingmaschinen führt zur arithmetischen Hierarchie.

Literatur


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Orakel — Die Delphische Sibylle in der Sixtinischen Kapelle Das Orakel (lat. oraculum, „Götterspruch“) bezeichnet eine mit Hilfe eines Rituals oder eines Mediums gewonnene transzendente, häufig göttliche Offenbarung, die der Beantwortung von Zukunfts oder …   Deutsch Wikipedia

  • Nichtdeterministische Turingmaschine — Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der Theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet. Inhaltsverzeichnis 1 Informelle Beschreibung 2 Formale Definition …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Orakelmaschine — Eine Orakel Turingmaschine ist eine , die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine black box vorstellen, die von der Turingmaschine befragt werden kann und ein Problem in einem Schritt löst. Der Begriff der… …   Deutsch Wikipedia

  • Orakelturingmaschine — Eine Orakel Turingmaschine ist eine , die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine black box vorstellen, die von der Turingmaschine befragt werden kann und ein Problem in einem Schritt löst. Der Begriff der… …   Deutsch Wikipedia

  • PH (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie)… …   Deutsch Wikipedia

  • Polynomiale Hierarchie — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie)… …   Deutsch Wikipedia

  • Polynomialzeithierarchie — Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie) ist die vermutete Struktur von Komplexitätsklassen zwischen NP und PSPACE. Der Grundgedanke hinter der Polynomialzeithierarchie ist die Frage, ob durch die Hinzunahme von Orakeln,… …   Deutsch Wikipedia

  • P!=NP — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia

  • P/NP-Problem — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”