Gibt es ein Ergebnis in der Berechenbarkeitstheorie, das sich nicht relativiert?

Ich habe Andrej Bauers Artikel Erste Schritte in der Theorie der synthetischen Berechenbarkeit gelesen . Abschließend stellt er fest, dass

Unsere Axiomatisierung hat ihre Grenzen: Sie kann keine Ergebnisse in der Berechenbarkeitstheorie nachweisen, die sich nicht auf Orakelberechnungen relativieren lassen. Dies liegt daran, dass die Theorie in einer Variante der effektiven Topos interpretiert werden kann, die aus teilweise rekursiven Funktionen mit Zugriff auf ein Orakel aufgebaut sind.

Dies ließ mich über nicht-relativierende Ergebnisse in Bezug auf die Berechenbarkeit nachdenken. Alle Ergebnisse, die ich aus der Berechenbarkeitstheorie kenne, lassen sich auf die Berechnung mit Orakeln relativieren.

Gibt es Ergebnisse in der Berechenbarkeitstheorie , die sich nicht relativieren lassen? Dh Ergebnisse, die für die Berechenbarkeit gelten, aber für die Berechenbarkeit in Bezug auf ein Orakel nicht gelten?

Mit Ergebnis meine ich einen bekannten Satz in der Berechenbarkeitstheorie, nicht irgendeine erfundene Aussage. Wenn der Begriff der Relativierung für das Ergebnis keinen Sinn ergibt, dann ist er nicht das, wonach ich suche.

Es ist auch interessant zu wissen, ob das Ergebnis in der Sprache der Synthetic Computability Theory angegeben werden kann oder nicht.

computability relativization Anonym
quelle

Jeder kennt nicht-relativierende Ergebnisse in der Komplexitätstheorie wie IP = PSPACE. Ich frage nach Ergebnissen der nicht-relativierenden Berechenbarkeitstheorie , nicht nach Ergebnissen der Komplexitätstheorie .

Anonym

@Erfan: Ihre Kommentare sind für die Frage nicht relevant. Meine Frage betrifft die Berechenbarkeitstheorie, Sie sprechen von der Komplexitätstheorie. Ich suche nach nicht reletivierenden Ergebnissen, der Zeithierachiesatz relativiert sich. Wenn Sie eine Frage zum Zeithierarchiesatz und zur Relativierung haben, können Sie eine separate Frage stellen.

Anonym

Relevantes Material: Die von H. Rogers formulierte Homogenitätsvermutung wurde in Richard A. Shore widerlegt; Die Homogenitätsvermutung (1979): Es gibt einen Turing-Grad so dass nicht isomorph zu (die Struktur von Turing-Graden mit partiellen Graden) order ). Eine ähnliche Frage finden Sie auf lo.logic

a

$\mathbf{a}$

D (\geq a)

$\mathcal{D}(\geq \mathbf{a})$

D

$\mathcal{D}$

\leq_{T}

$\leq_{T}$

Marzio De Biasi

Gute Frage :-)

Andrej Bauer

@ Marzio: Interessant. "" " Dies bedeutet, dass es in der Sprache einen Satz erster Ordnung der nur was für die Turing - Grade zutrifft, aber falsch ist, wenn Sie den Satz für einige (und natürlich) auf die Turing - Grade relativieren , in der Turing Grad arbeiten entspricht alle Turing - Maschinen den Zugriff auf zu geben als Orakel.) Daher ist der Nachweis , dass wahr kann , ist nicht zu relativieren . $\varphi$ $\leq_T$ $\geq_Tx$ $x$ $\geq_Tx$ $x$ $\varphi$ $x$ "Aber ist nicht wirklich ein Ergebnis in Berechenbarkeitstheorie wird es für ein Meta-Theorem erfunden.

φ

$\varphi$

Anonymous

Antworten:

Higman's Embedding Theorem: Die endlich erzeugten rechnerisch dargestellten Gruppen sind genau die endlich erzeugten Untergruppen endlich dargestellter Gruppen. Darüber hinaus ist jede rechnerisch dargestellte Gruppe (auch die zählbar erzeugten) eine Untergruppe einer endlich dargestellten Gruppe.

Beachten Sie, dass diese Aussage könnte relativieren: „Die -computably präsentierte Gruppen (mit etwas Orakel ) sind genau die endlich erzeugten Untergruppen von endlich präsentierten Gruppen“ , aber es funktioniert nicht, wie man , dass für einige unberechenbare nachweisen kann gibt es -berechenbar dargestellte Gruppen, die nicht berechenbar dargestellt werden. $O$ $O$ $O$ $O$

In der Tat denke ich, dass jedes nicht-relativierende Ergebnis der Berechenbarkeitstheorie etwas von diesem Geschmack haben muss, da ein Teil des Ergebnisses oder sein Beweis irgendwie die wahre Berechenbarkeit von der Berechenbarkeit mit einem Orakel "festnageln" muss . In diesem Fall ist es die Endlichkeit, die die "tatsächliche Berechenbarkeit" ausmacht. Beachten Sie, dass dieses Ergebnis, wie von Scott Aaronson gefordert, nicht mit den üblichen Berechnungsmodellen (Turing-Maschine, RAM usw.) übereinstimmt, aber nicht relativiert wird (auch hier, weil alle üblichen Modelle der "tatsächlichen" Berechnung einige gemeinsam haben gemeinsame "Endlichkeitseigenschaft"). $O$

Andererseits könnte man argumentieren, dass dies für diese Frage "nicht zählt", da es eher einer Definition der Berechenbarkeit unter Verwendung von Gruppen entspricht als ein "Ergebnis der Berechenbarkeitstheorie". Andererseits ist es eine Definition der Berechenbarkeit, die robust gegenüber dem Modell ist , sich aber nicht relativiert . (Im Gegensatz zu beispielsweise Kleenes Charakterisierung der berechenbaren Funktionen, die sich leicht relativieren lässt, indem einfach die charakteristische Funktion Ihres Orakels zum generierenden Satz von Funktionen hinzugefügt wird. Es scheint keine analoge Operation für Gruppen im Kontext von Higman-Einbettung zu geben.)

Joshua Grochow
quelle

Unterscheidet sich Ihr Beispiel durch Endlichkeit (vs. Unendlichkeit) oder durch Zählbarkeit (vs. Unzählbarkeit)?

András Salamon

Entschuldigen Sie meine Unwissenheit, aber ist Higmans Theorem einheitlich? Kann man also bei einer rechnerisch dargestellten Gruppe eine endlich erzeugte Gruppe, die sie enthält, einheitlich berechnen?

Andrej Bauer

Hoppla, bitte ersetzen Sie in meiner Frage "endlich generiert" durch "endlich präsentiert". Das war ein trivialer Fehler. Ich frage mich, ob wir "endlich präsentiert" durch etwas allgemeineres ersetzen können.

Andrej Bauer

S A T^{O}

$SAT^O$

N P^{O}

$NP^O$

@ AndrewMorgan: Einverstanden. Ich würde denken, dass Knotengattung ein guter Kandidat wäre :).

Joshua Grochow

Darüber habe ich mich auch oft gewundert!

Wenn mit "Ergebnisse in der Berechenbarkeitstheorie" Ergebnisse gemeint sind, die in Bezug auf die Wahl des Maschinenmodells (Turing-Maschinen, RAM-Maschinen usw.) unveränderlich sind, dann kenne ich kein einziges Beispiel für ein solches Ergebnis, und ich Ich hätte mich definitiv daran erinnert, wenn ich einen gesehen hätte.

Das, was ich einer Antwort am nächsten bringen kann, ist: Ich denke, es gibt viele interessante Fragen in der Berechenbarkeitstheorie, die vom Maschinenmodell abhängen könnten. Zum Beispiel: Ist die Busy Beaver-Funktion mit ihrer üblichen Definition in Bezug auf Turing-Maschinen unendlich oft ungerade? Ist der Wert von BB (20) unabhängig von ZFC? Was auch immer die Antworten auf diese Fragen sind, sie könnten für relativierte Analoga der BB-Funktion sicherlich unterschiedlich sein.

Scott Aaronson
quelle

Hier ist ein mehr oder weniger triviales Beispiel: Betrachten Sie das Problem des Anhaltens von Turing-Maschinen, denen der Zugriff auf ein Orakel ausdrücklich (nach Definition des Berechnungsmodells) untersagt ist. Es ist sowohl in Bezug auf kein Orakel als auch in Bezug auf ein triviales Orakel unentscheidbar, und dennoch ist es in Bezug auf ein Orakel in Bezug auf das Stillstandsproblem entscheidbar. (Das Problem selbst ändert sich nicht in Bezug auf ein Orakel, da es nicht auf das Orakel zugreifen kann, aber das (uneingeschränkte) TM, das das Problem entscheidet, wird angesichts des Orakels mächtiger.)

Es gibt auch viele andere Beispiele. Spielen Sie einfach ein wenig mit dem Berechnungsmodell und Sie können andere ähnliche Ergebnisse finden.

Philip White
quelle

Nur neugierig: was genau ist los mit dieser Antwort? Vielleicht glauben die Downvoter nicht, dass es möglich ist, einer Turing-Maschine den Zugang zu einem Orakel zu verwehren, und verlangen eine nähere Erklärung dafür?

Philip White

Es scheint keine sehr faire Definition von Relativierung zu sein, der Maschine zu erlauben, ein Orakel zu haben, aber es dann nicht zu erlauben, das Orakel zu benutzen.

David Eppstein

Interessant, aber nicht das, wonach ich suche. Ich suche ein bekanntes Ergebnis in der Berechenbarkeitstheorie, das nicht relativiert, kein Argument dafür, wie man ein solches Ergebnis aufbereitet.

Anonym

Beachten Sie die folgende Aussage: H (Halteproblem für Turing-Maschinen ohne Orakel) ist nicht berechenbar. Andererseits ist H relativ zu einem haltenden Problemorakel berechenbar. Auch wenn wir dies als einen Weg betrachten, die Aussage zu relativieren, ist es kein interessanter. Wahrscheinlich gibt es einen ähnlichen Weg, eine Aussage zu relativieren, die sie falsch macht. Eine Relativierung bringt nicht nur irgendwo ein Orakel an. Eine Relativierung ist interessant, wenn eine interessante Klasse von Argumenten erhalten bleibt. Wenn also eine Aussage nicht relativiert, wissen wir, dass eine Klasse von Argumenten die Aussage nicht beweisen kann.

Kaveh

Nehmen Sie zB die Relativierungsmethode in BGS. Es ist interessant, weil es einfache Diagonalisierungsargumente beibehält, so dass sie P gegen NP nicht ausgleichen können. Wenn eine Relativierung solche Argumente nicht bewahrt, ist es wahrscheinlich kein interessanter Weg, Aussagen zu relativieren. Eine gute Relativierung sollte so viele bekannte Argumente und nachgewiesene Ergebnisse wie möglich durchhalten. Je weniger sie erhalten bleibt, desto weniger interessant wird sie.

Kaveh