imported>Meinichselbst: Parameter fix

2025-09-13T19:16:01Z

Parameter fix

Neue Seite

Eine '''Orakel-Turingmaschine''' ist eine [[Turingmaschine]], die mit einem ''Orakel'' verbunden ist. Bildhaft kann man sich ein Orakel als eine [[Black Box (Systemtheorie)|''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 [[Theoretische Informatik|Theoretischen Informatik]] dazu, [[Hierarchie]]n 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 [[Erfüllbarkeitsproblem der Aussagenlogik|SAT]] als Orakel können jedes Problem aus [[NP (Komplexitätsklasse)|NP]] in [[Polynomialzeit|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 ==
Sei <math>A\subseteq \Sigma^*</math> eine [[Formale Sprache|Sprache]] über dem Alphabet <math>\Sigma</math>.
Eine Orakel-Turingmaschine mit Orakel <math>A</math> ist eine Turingmaschine <math>M</math> mit einem zusätzlichen Eingabeband, dem ''Orakelband,'' und drei ausgezeichneten Zuständen: <math>q_j,~ q_n,~ q_?</math>. Schreibt <math>M</math> ein [[Wort (Theoretische Informatik)|Wort]] <math>w\in\Sigma^*</math> auf das Orakelband und geht in den Zustand <math>q_?</math> über, so befragt <math>M</math> das Orakel: Der Nachfolgezustand von <math>q_?</math> sei <math>q_j</math> falls <math>w\in A</math> gilt und andernfalls <math>q_n</math>. Anschließend wird das Orakelband gelöscht.

Wenn <math>T</math> und <math>K</math> Klassen von Sprachen sind, dann bezeichnet <math>T^K</math> die Klasse der Sprachen, die von Turingmaschine <math>M</math> mit Orakel <math>A</math> akzeptiert werden, wobei <math>L(M)\in T </math> und <math>A\in K</math> sind. Typische Klassen sind einelementige Klassen, [[Komplexitätsklasse]]n wie P oder [[NP (Komplexitätsklasse)|NP]], oder auch die Klasse aller [[rekursiv aufzählbar]]en Sprachen.

Beispiele:
* <math>P^{SAT}</math> bezeichnet die Klasse der Sprachen, die von einer deterministischen, polynomiell zeitbeschränkten Turingmaschine mit Orakel <math>SAT</math> akzeptiert werden.
* <math>NP^{NP}</math> bezeichnet die Klasse der Sprachen, die von einer nichtdeterministischen, polynomiell zeitbeschränkten Turingmaschine mit Orakel aus der Klasse <math>NP</math> akzeptiert werden.

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

== Eigenschaften ==
* Für zwei Komplexitätsklassen <math>T</math>, <math>K</math> und eine Sprache <math>L \in K</math> gilt <math>T^K = T^L</math>, falls folgende Bedingungen erfüllt sind:
*# <math>L</math> ist <math>K</math>-[[Vollständigkeit (Komplexitätstheorie)|vollständig]] bezüglich einer [[Reduktion (Theoretische Informatik)|Reduktion]] <math>\preceq</math>
*# Die <math>T</math> zugrundeliegende Klasse von Turingmaschinen ist mächtig genug, die Reduktion <math>\preceq</math> zu berechnen
     Beispielsweise gilt <math>P^{NP} = P^{SAT}</math>, da <math>SAT</math> <math>NP</math>-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 <math>T \subseteq T^K</math>, <math>K \subseteq T^K</math> und <math>coK \subseteq T^K</math> für alle Klassen <math>T</math> und <math>K</math>. Letztere Eigenschaft ergibt sich, wenn man die Zustände <math>q_j</math> und <math>q_n</math> vertauscht interpretiert. Insbesondere gilt also <math>T^K = T^{coK}</math>

* Es gilt <math>P^P=P</math> und <math>NP^P=NP</math>, 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 <math>K = coK</math> der Orakelklasse <math>K</math>. Beispielsweise würde aus <math>NP^{NP}=NP</math> die bislang ungeklärte Beziehung <math>coNP = NP</math> folgen <math>(\overline{SAT} \in NP)</math>.

=== 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 [[Arithmetische Hierarchie|arithmetischen Hierarchie]] und den [[Turinggrad]]en.

== Relative Berechenbarkeit ==

Wie [[#Zum Halteproblem|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 [[Rekursionssatz|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 <math>A;B \subseteq \N</math> Mengen [[Natürliche Zahlen|natürlicher Zahlen]].

* Die Menge <math>A</math> heiße ''berechenbar in'' <math>B</math> falls es eine Turingmaschine mit Orakel für <math>B</math> gibt, die die [[Indikatorfunktion|charakteristische Funktion]] <math>\chi_A</math> berechnet, also <math>A</math> [[Entscheidbare Menge|entscheidet]].

Dies ist per Definition genau dann der Fall, wenn sich <math>A</math> auf <math>B</math> [[Turing-Reduktion|Turing-reduzieren]] lässt, <math>A \preceq_T B</math>.

* Die Menge <math>A</math> heiße entsprechend ''rekursiv aufzählbar in'' <math>B</math>, falls es eine Turingmaschine mit Orakel für <math>B</math> gibt, die die [[partielle charakteristische Funktion]] <math>\chi^\bot_A</math> berechnet, also <math>A</math> [[Rekursiv aufzählbare Menge|aufzählt]].

Offenbar impliziert die relative Berechenbarkeit die relative Aufzählbarkeit, die Umkehrung gilt im Allgemeinen nicht.
Allerdings ist auch hier <math>A</math> genau dann berechenbar in <math>B</math>, wenn sowohl <math>A</math> als auch sein [[Komplement (Mengenlehre)|Komplement]] <math>\bar A</math> aufzählbar in <math>B</math> sind.

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

== Literatur ==

* {{Literatur
|Autor = [[John E. Hopcroft]], [[Jeffrey D. Ullman]]
|Titel = Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie
|Verlag = Oldenbourg
|Auflage=4. durchgesehene
|Ort = München u. a.
|Jahr = 2000
|ISBN = 3-486-25495-2
}}
* {{Literatur
|Autor = [[Christos Papadimitriou|Christos H. Papadimitriou]]
|Titel = Computational Complexity
|Verlag = Addison-Wesley
|Ort = Reading MA u. a.
|Jahr = 1994
|ISBN = 0-201-53082-1
}}

* {{cite book |author=Hartley Rogers, Jr. |title=Theory of Recursive Functions and Effective Computability |location=Cambridge, Massachusetts |publisher=McGraw-Hill |page=145–149 |date=1987 |isbn=0-262-68052-1 |language=en}}

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Berechenbarkeitstheorie]]

Orakel-Turingmaschine - Versionsgeschichte

imported>Meinichselbst: Parameter fix