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

9

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.

Ari
quelle
2
Wenn das Orakel "wirklich" Zeit gebraucht hat, ist dies nur ein Faktor für die Laufzeit der gesamten Maschine. Die Annahme konstanter Kosten (dh wie oft Sie das Orakel benötigen) erleichtert den Vergleich von Algorithmen, die Orakel verwenden. (Die Frage, ob die erhaltenen Ergebnisse in der Realität relevant sind, ist eine, die Sie in TCS immer sehen und / oder ignorieren.)T
Raphael
@Raphael Mit "Sie" im Kommentar in Klammern meinen Sie Komplexitätstheoretiker im Allgemeinen oder mich im Besonderen?
Ari
Das Vorherige. In gewisser Weise beides.
Raphael
ein fortgeschrittenes Thema. Versuchen Sie, mit Fortnow zu beginnen, der zustimmt, dass sie manchmal "missbraucht" werden und die Gegend untersuchen. Die selbstkonsistente Art, diese Ergebnisse zu sehen, ist wie eine "bedingte" Behauptung. Ähnlich wie viele Ergebnisse in der Mathematik auf der Grundlage der Riemannschen Hypothese usw. bedingt bewiesen werden
vzn

Antworten:

8

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 schreibenh

haltingPlusOne:{h}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.

jmite
quelle
n+1=nn1
1
Die Sache ist, die Aussagen sind nicht falsch, wir können sie einfach nicht konstruieren. Der Schlüssel ist, dass Orakel keine Turing-Maschinen sind, das heißt nicht, dass sie nicht existieren.
Jmite
"finde den richtigen Eingang" "finde den richtigen Ausgang" ?
2

EINB.B.=B.EIN

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.

P.N.P.

w|w|

A.Schulz
quelle