Gibt es eigentlich einen universellen Begriff der Berechenbarkeit?

Vor ein paar Wochen bin ich auf diesen großartigen Beitrag von JDH gestoßen und er beschäftigt mich seitdem. Die TL;DR für den Beweis ist, dass wir die Ausgaben jeder Funktion in die Axiome einer Mengenlehre codieren können, sodass wir einfach eine einzelne Turing-Maschine benötigen, die als cleverer „Parser“ fungieren kann, der die Informationen aus den Axiomen extrahieren kann und die gewünschte Funktion berechnen - das verstehe ich (zumindest konzeptionell und etwas formal).

Was mich jedoch verwirrt, sind die philosophischen Implikationen, die dies für Konzepte der Berechenbarkeit hat ... Ich glaubte, dass es in gewissem Sinne einen universellen Begriff der Berechenbarkeit gab (dh es gab Probleme, die entweder entscheidbar sind oder nicht), aber dies deutet darauf hin Solche Vorstellungen hängen vom mengentheoretischen Hintergrund für Ihre Berechnung ab - zum Beispiel diskutiert dieser Beitrag von Scott Aaronson die Arbeit eines seiner Studenten, der zeigt, dass es eine bestimmte Turing-Maschine gibt, deren Verhalten unabhängig von ZFC ist (was wiederum implizit vorschlägt, dass das Verhalten platonisch ist, wir es aber einfach nicht beweisen können).

Verzeihen Sie mir den Mangel an Klarheit in meiner Frage, aber: Gibt es eine Möglichkeit, dies zu lösen? Warum gibt es scheinbar unberechenbare Probleme (deren Beweis der Unberechenbarkeit oft Widerspruchsbeweise scheinbar ohne Bezugnahme auf irgendeinen mengentheoretischen Hintergrund verwendet, zB das Halteproblem), die von einer Turing-Maschine berechnet werden können, ohne (offiziell) ein Orakel zu verwenden ? Hat dies Auswirkungen auf die Church-Turing-These, da vermutlich kein Mensch die Busy Beaver-Funktion zuverlässig berechnen könnte, während der universelle Algorithmus (wenn er in das richtige Universum gestellt wird) dies kann?

Antworten (1)

Möglicherweise haben Sie einen der Schlüsselaspekte dieses Beitrags von Hamkins missverstanden. Sein Satz besagt nicht, dass jede Funktion berechenbar ist (trotz des Titels).

Es besagt stattdessen, dass Sie jede gegebene Funktion in einem sorgfältig ausgewählten Universum berechnen können, das heißt in einem sorgfältig ausgewählten Modell der Mengenlehre. Das Universum, in dem Sie es berechnen können, hängt von der Funktion ab. Es gibt viele, viele, viele verschiedene Modelle der Mengentheorie, dh viele verschiedene mengentheoretische Universen (so wie es viele, viele, viele verschiedene Modelle der Gruppentheorie gibt, dh viele verschiedene Gruppen). Die Funktion, die Ihnen gegeben wurde, kann in einigen Modellen berechenbar und in anderen nicht berechenbar sein. Alle Theoremgarantien sind die Existenz eines Modells, in dem die gegebene Funktion berechenbar ist.

Wäre es nicht hilfreich, parallele Berechnungen in diesem Universum durch serielle Berechnungen zu ersetzen, die gleichzeitig über mehrere Universen fortschreiten?
Selbst zu sagen, dass "Sie es berechnen können" in einem sorgfältig ausgewählten Universum, scheint hier gefährlich suggestiv zu sein. Was das wirklich bedeutet, ist, dass es einen bestimmten arithmetischen Satz gibt, der (a) wenn er in den tatsächlichen ganzen Zahlen interpretiert wird, die Behauptung ausdrückt, dass die angegebene Turing-Maschine diese und jene Ausgabe für diese und jene Eingabe liefert, und (b) den Satz trifft zufällig auf das sorgfältig ausgewählte Universum zu.
Ihr Kommentar "gefährlicher Vorschlag" ist passend, danke. Aber wahrscheinlich kann ich den feineren Aspekten dieses Problems nicht gerecht werden, also denke ich, dass ich meine Antwort so belasse, wie sie ist, in der Hoffnung, dass das OP die gefährlichen Gewässer erkennen kann, in die ihr Posten tritt.
@Lee Mosher: Tut mir leid, dass ich so lange frage, nachdem diese Frage gestellt wurde, aber könnten Sie mir erklären, wie sich dies auf Dinge wie das Halteproblem auswirkt? Funktioniert der Beweis nur aufgrund bestimmter (versteckter/impliziter) Annahmen, die auf einem Standardmodell von ZFC oder so beruhen?
@IskyMathews: Es hat nicht wirklich Auswirkungen auf das Halteproblem. Wenn Sie die Konstruktion auf die Haltefunktion anwenden, erhalten Sie ein spezielles Universum, das (a) nicht standardmäßige ganze Zahlen und (b) eine Turing-Maschine enthält, sodass das Ergebnis, von dem das spezielle Universum glaubt, dass seine Turing-Maschine die Anzahl von ergibt Eine standardmäßige endliche Turing-Maschine, die in Ihre Welt passt , wird übereinstimmen, ob diese Maschine beendet wird, wenn sie in Ihrer Welt ausgeführt wird. Diese Antwort kann falsch sein, wenn es darum geht, die Maschine in der speziellen Welt selbst zu betreiben, und Sie haben garantiert nichts über Maschinen mit nicht standardmäßigen Nummern.
Gibt es eigentlich einen universellen Begriff der Berechenbarkeit?
AntwortenHierDatenschutz-Bestimmungen1y, 0v