Orakel-Turingmaschine

Maschine in der theoretischen Informatik

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 (vergleiche Pfad (Stochastik)).

Definition

Bearbeiten

Sei   eine Sprache über dem Alphabet  . Eine Orakel-Turingmaschine mit Orakel   ist eine Turingmaschine   mit einem zusätzlichen Eingabeband, dem Orakelband, und drei ausgezeichneten Zuständen:  . Schreibt   ein Wort   auf das Orakelband und geht in den Zustand   über, so befragt   das Orakel: Der Nachfolgezustand von   sei   falls   gilt und andernfalls  . Anschließend wird das Orakelband gelöscht.

Wenn   und   Klassen von Sprachen sind, dann bezeichnet   die Klasse der Sprachen, die von Turingmaschine   mit Orakel   akzeptiert werden, wobei   und   sind. Typische Klassen sind einelementige Klassen, Komplexitätsklassen wie P oder NP, oder auch die Klasse aller rekursiv aufzählbaren Sprachen.

Beispiele:

  •   bezeichnet die Klasse der Sprachen, die von einer deterministischen, polynomiell zeitbeschränkten Turingmaschine mit Orakel   akzeptiert werden.
  •   bezeichnet die Klasse der Sprachen, die von einer nichtdeterministischen, polynomiell zeitbeschränkten Turingmaschine mit Orakel aus der Klasse   akzeptiert werden.

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

Eigenschaften

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

     Beispielsweise gilt  , da    -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  ,   und   für alle Klassen   und  . Letztere Eigenschaft ergibt sich, wenn man die Zustände   und   vertauscht interpretiert. Insbesondere gilt also  
  • Es gilt   und  , da die Turingmaschine anstatt das Orakel zu befragen, sich die Antwort des Orakels selber berechnen kann. Die Aussage lässt sich nicht auf nichtdeterministische Komplexitätsklassen verallgemeinern. Grund dafür ist die notwendige Eigenschaft   der Orakelklasse  . Beispielsweise würde aus   die bislang ungeklärte Beziehung   folgen  .

Zum Halteproblem

Bearbeiten

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 und den Turinggraden.

Relative Berechenbarkeit

Bearbeiten

Wie oben bereits erwähnt übertragen sich die meisten Theoreme der Berechenbarkeitstheorie auch auf Orakel-Turingmaschinen. Allen voran das Smn-Theorem zusammen mit den daraus folgenden Rekursionssätzen sowie die Unentscheidbarkeit des (Orakel-)Halteproblems. Man spricht dann auch von relativer Berechenbarkeit (am. engl.: relativized recursion theory), dies spiegelt sich auch in den folgenden Definitionen wider:

Seien   Mengen natürlicher Zahlen.

  • Die Menge   heiße berechenbar in   falls es eine Turingmaschine mit Orakel für   gibt, die die charakteristische Funktion   berechnet, also   entscheidet.

Dies ist per Definition genau dann der Fall, wenn sich   auf   Turing-reduzieren lässt,  .

  • Die Menge   heiße entsprechend rekursiv aufzählbar in  , falls es eine Turingmaschine mit Orakel für   gibt, die die partielle charakteristische Funktion   berechnet, also   aufzählt.

Offenbar impliziert die relative Berechenbarkeit die relative Aufzählbarkeit, die Umkehrung gilt im Allgemeinen nicht. Allerdings ist auch hier   genau dann berechenbar in  , wenn sowohl   als auch sein Komplement   aufzählbar in   sind.

Hinweis: Relative Aufzählbarkeit sollte nicht mit der aufzählbaren Reduktion verwechselt werden. Letztere ist echt schwächer als relative Aufzählbarkeit und im Allgemeinen unvergleichbar mit der Turing-Reduktion.

Literatur

Bearbeiten
  • Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, Cambridge, Massachusetts 1987, ISBN 0-262-68052-1, S. 145–149.