Orakel-Turingmaschine

Grundidee und Definition

Eine Orakel-Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist. Das Orakel ist eine Black-Box, die auf eine Anfrage in einem Schritt antwortet. Dadurch können Berechenbarkeit und Komplexität untersucht und Hierarchien definiert werden. Geeignete Orakel können die Berechenbarkeit verstärken oder die benötigte Komplexität verringern.

Sei A ⊆ Σ* eine Sprache über dem Alphabet Σ. Eine Orakel-Turingmaschine mit Orakel A ist eine Turingmaschine M mit einem zusätzlichen Eingabeband, dem Orakelband, sowie drei ausgezeichneten Zuständen qⱼ, qₙ und q₍?₎. Schreibt M ein Wort w ∈ Σ* auf das Orakelband und wechselt in q₍?₎, antwortet das Orakel unmittelbar: Der Nachfolgezustand ist qⱼ, falls w ∈ A gilt, und qₙ andernfalls. Anschließend wird das Orakelband gelöscht.

Für Klassen von Sprachen T und K bezeichnet Tᴷ die Klasse der Sprachen, die von einer Turingmaschine M mit Orakel A akzeptiert werden, wobei L(M) ∈ T und A ∈ K gilt. T und K können beispielsweise einelementige Klassen, P, NP oder die Klasse aller rekursiv aufzählbaren Sprachen sein.

Pˢᴬᵀ ist die Klasse der Sprachen, die von einer deterministischen, polynomiell zeitbeschränkten Turingmaschine mit Orakel SAT akzeptiert werden. NPᴺᴾ ist die Klasse der Sprachen, die von einer nichtdeterministischen, polynomiell zeitbeschränkten Turingmaschine mit einem Orakel aus NP akzeptiert werden. Solche Klassen werden unter anderem zur Definition der Polynomialzeithierarchie verwendet.

Wichtige Eigenschaften

Für zwei Komplexitätsklassen T und K und eine Sprache L ∈ K gilt Tᴷ = Tᴸ, wenn L K-vollständig bezüglich einer Reduktion ≼ ist und die zugrunde liegende Klasse von Turingmaschinen diese Reduktion berechnen kann. Daher gilt beispielsweise Pᴺᴾ = Pˢᴬᵀ, weil SAT bezüglich Polynomialzeitreduktion NP-vollständig ist.

Eine Orakel-Turingmaschine besitzt mindestens die Fähigkeiten ihrer gewöhnlichen Turingmaschine, ihres Orakels und der Komplementsprache des Orakels. Deshalb gelten für alle Klassen T und K:

• T ⊆ Tᴷ
• K ⊆ Tᴷ
• coK ⊆ Tᴷ

Die letzte Eigenschaft folgt daraus, dass man die Antworten qⱼ und qₙ vertauscht interpretiert. Insbesondere gilt Tᴷ = Tᶜᴷ.

Ist das Orakel selbst in polynomialer Zeit berechenbar, bringt es keinen zusätzlichen Vorteil: Es gilt Pᴾ = P und NPᴾ = NP, weil die Turingmaschine die Antwort selbst berechnen kann. Diese Aussage lässt sich nicht allgemein auf nichtdeterministische Komplexitätsklassen übertragen. Dafür wäre insbesondere K = coK erforderlich. Aus NPᴺᴾ = NP würde beispielsweise die bislang ungeklärte Beziehung coNP = NP folgen, da das Komplement von SAT in NP läge.

Orakel und Halteproblem

Das Orakel ist in keiner Weise beschränkt; auch nicht entscheidbare Sprachen können als Orakel dienen. Daher kann das Halteproblem als Orakel verwendet werden. Eine Turingmaschine mit diesem Halteorakel kann das Halteproblem gewöhnlicher Turingmaschinen ohne Orakel lösen.

Dies widerspricht nicht der Unentscheidbarkeit des Halteproblems. Das Unentscheidbarkeitsergebnis besagt lediglich, dass keine Turingmaschine ohne Orakel das Problem löst. Für Turingmaschinen, die selbst ein Halteorakel besitzen, ist das entsprechende Halteproblem jedoch ebenfalls nicht durch solche Halteorakel-Turingmaschinen lösbar.

Die Konstruktion immer stärkerer Orakel-Turingmaschinen führt zur arithmetischen Hierarchie und zu den Turinggraden.

Relative Berechenbarkeit

Viele Sätze der Berechenbarkeitstheorie übertragen sich auf Orakel-Turingmaschinen. Dazu gehören insbesondere das Sₘₙ-Theorem, die daraus folgenden Rekursionssätze sowie die Unentscheidbarkeit des Orakel-Halteproblems. Dieses Gebiet wird relative Berechenbarkeit oder auf Englisch relativized recursion theory genannt.

Seien A, B ⊆ ℕ Mengen natürlicher Zahlen. A heißt berechenbar in B, wenn es eine Turingmaschine mit Orakel für B gibt, die die charakteristische Funktion χ_A berechnet; dadurch entscheidet sie A. Genau dann gilt auch A ≼ₜ B, das heißt, A lässt sich auf B Turing-reduzieren.

A heißt rekursiv aufzählbar in B, wenn eine Turingmaschine mit Orakel für B die partielle charakteristische Funktion χ_Aᵇ berechnet und damit A aufzählt. Relative Berechenbarkeit impliziert relative Aufzählbarkeit, die Umkehrung gilt im Allgemeinen nicht. A ist genau dann in B berechenbar, wenn sowohl A als auch das Komplement Ā in B aufzählbar sind.

Die relative Aufzählbarkeit ist nicht mit der aufzählbaren Reduktion zu verwechseln. Die aufzählbare Reduktion ist echt schwächer als relative Aufzählbarkeit und im Allgemeinen unvergleichbar mit der Turing-Reduktion.