Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

Eine Orakel-Turingmaschine ist eine Turingmaschine M, die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine black box vorstellen, die von M befragt werden kann und ein Problem in einem Schritt löst. Dadurch sind Orakel-Turingmaschinen in der Lage, Probleme einer gegebenen Komplexitätsklasse in konstanter Zeit zu entscheiden.

Inhaltsverzeichnis 1 Definition 2 Eigenschaften 2.1 Halteproblem 3 Literatur

Definition

Sei eine Sprache über dem Alphabet Σ. 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 auf das Orakelband und geht in den Zustand q_? über, so befragt M das Orakel: Der Nachfolgezustand von q_? sei q_j falls gilt und andernfalls q_n. Anschließend wird das Orakelband gelöscht.

Die Sprache A kann natürlich eine höhere Komplexität haben als die Sprache, die M selbst berechnen kann, ohne das Orakel zu befragen.

Die Sprache, die M akzeptiert, ist Parser-Fehler (Unbekannter Fehler\text): L(M^A):=\{w|M \text{ akzeptiert } w \text{ mit Orakel } A\} .

Sei K eine Komplexitätsklasse (wie NP) und A eine Sprache. Dann seien:

• P^A: = {L(M^A) | M ist eine deterministische, polynomiell zeitbeschränkte Orakel-Turingmaschine mit Orakel A}
• NP^A: = {L(M^A) | M ist eine nichtdeterministische, polynomiell zeitbeschränkte Orakel-Turingmaschine mit Orakel A}
• 
• 

Diese Komplexitätsklassen werden unter anderem dazu genutzt, um die Polynomialzeithierarchie zu definieren. Ähnlich lassen sich für andere Komplexitätsklassen C die Begriffe C^A und C^K definieren.

Eigenschaften

Es gilt offensichtlich P^P = P, denn anstatt für Problem aus ein Orakel zu befragen, kann eine deterministische polynomiell beschränkte Turingmaschine das Problem selbst berechnen.

Weiterhin gilt (Beweis: Sei . Dann entscheidet die determinstische Turingmaschine, die bei Eingabe w das Wort w auf das Orakelband schreibt, in den Zustand q_? übergeht und genau dann akzeptiert, wenn der Nachfolgezustand q_j ist, in Linearzeit die Sprache L).

Halteproblem

Die Definition der Orakel-Turingmaschine setzt nicht voraus, dass das Orakel A entscheidbar oder gar semi-entscheidbar ist. Also gibt es Orakel-Turingmaschinen, die das Halteproblem von Turingmaschinen (ohne Orakel) lösen können. Allerdings lassen sich für diese Maschinen wiederum nicht entscheidbare Halteprobleme konstruieren.

Literatur

Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Oldenbourg, München/Wien 2000

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Orakel-Turingmaschine, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.

, ISBN 3486254952.

Christos Papadimitriou: Computational Complexity. Addison-Wesley, 1994

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Orakel-Turingmaschine, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.

.

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Orakel-Turingmaschine, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.