Wie führt der Einsatz von Orakel-Turing-Maschinen nicht zu Widersprüchen?

Wie können wir sicherstellen, dass wir bei der Verwendung von Orakel-Turing-Maschinen weiterhin fundierte und gültige Aussagen zu Komplexitätsklassen treffen? Nach meinem Verständnis (basierend auf den Definitionen in einführenden Lehrbüchern zu diesem Thema) können Orakel-Turing-Maschinen den Mitgliedschaftsstatus einer Zeichenfolge in Bezug auf eine Orakel-Sprache in einem Berechnungsschritt bestimmen. Es ist jedoch nachweislich unmöglich, die häufig verwendeten Orakelsprachen in konstanter Zeit zu lösen (zum Beispiel ein EXPTIME-vollständiges Orakel). Für mich scheint dies "die Tür zu öffnen" für Widersprüche, und schließlich folgt alles aus einem Widerspruch.

Es gibt verschiedene Möglichkeiten, dies zu betrachten.

Eine davon ist, dass Implikation in Beweisen eine Art Funktion ist, die einen Beweis für etwas als Eingabe nimmt und einen Beweis für etwas anderes ausgibt.

Wir können Funktionen schreiben, die mit Werten arbeiten, die wir nicht haben.

Betrachten wir zum Beispiel die Haltezahl , die nicht berechenbar ist. Ich kann die Funktion schreiben$h$

$haltingPlusOne : \{h \} \rightarrow \mathbb{N}$

.$haltingPlusOne(x) = x + 1$

Diese Funktion nimmt die Halting-Nummer als Eingabe und gibt die Halting-Nummer plus eins zurück. Dies ist eindeutig eine genau definierte Funktion: Wenn wir ihr den richtigen Input geben, gibt sie den richtigen Output. Die Tatsache, dass wir nicht die richtige Eingabe finden können, macht eine Transformation nicht weniger gültig.

Ich sehe Beweise mit Orakeln als ähnlich. Es handelt sich im Grunde genommen um Funktionen, die besagen, dass ich eine Turing-Maschine habe, die das Problem löst , und ich werde als Ausgabe einen Beweis für einen Satz geben.$X$

Es ist auch wichtig zu wissen, dass, wenn wir etwas sagen wie "Es gibt keine Turing-Maschine, die das Stoppproblem entscheiden kann", das heißt, dass es kein TM gibt, das der Standarddefinition eines TM entspricht, das das Stoppproblem entscheidet.

Ein Orakel sagt im Grunde: "Angenommen, wir haben ein TM, das der normalen Definition entspricht, außer dass wir auch ein Problem lösen können." Es gibt also keinen Widerspruch, da wir nicht davon ausgehen, dass ein normales TM das Problem akzeptiert, sondern dass ein spezielles TM das Problem akzeptiert.

Stellen Sie sich das in einer sehr informellen Analogie so vor. Wenn ich Ihnen beweisen kann, dass kein Mensch ohne Supermächte fliegen kann, gibt es keinen Widerspruch, der besagt, dass es einen Superhelden gibt, der fliegen kann.

Diese Orakel sind rein logische Objekte. Wir wissen nicht, wie wir physische Maschinen bauen sollen, die sie emulieren, wie wir es mit Turing-Maschinen können, aber soweit wir wissen, gibt es keinen inhärenten Widerspruch zwischen ihren Definitionen und unseren Grundaxiomen. Als logische Objekte existieren diese Orakel. Wir wissen, dass es sich nicht um Standard-Turing-Maschinen, Lambda-Kalkül-Begriffe oder partiell-rekursive Funktionen handelt. Die Church-Turing-These besagt, dass es kein leistungsfähigeres Modell gibt, aber es ist kein Theorem, es ist nur eine Vermutung und zu informell, um jemals wirklich bewiesen zu werden.

$A$$B$$B=B^A$

Was bringt es dann, ein Oracle TM zu verwenden? Ich würde sagen, es erlaubt uns hauptsächlich theoretische Überlegungen zum (Grad) der Härte von Problemen. Das Orakel kann sogar unentscheidbar sein. In diesem Fall können Sie eine ganze Hierarchie unentscheidbarer Probleme definieren (Turing-Grad). Wenn Ihr Orakel das Halteproblem ist, können Sie Ihr Orakel-TM natürlich nicht in ein traditionelles TM umwandeln.

Das Orakel-TM-Konzept ist auch wichtig, um eine starke Form von Reduktionen (Turing-Reduktionen) zu definieren.

$\sf P$$\sf NP$

$w$$|w|$