Ich entschuldige mich, wenn diese Frage schon einmal gestellt wurde, aber ich konnte kein Duplikat finden.
Ich habe gerade The Annotated Turing gelesen und bin etwas verwirrt.
Nach meinem Verständnis besteht das Entscheidungsproblem darin, ob ein Algorithmus existiert oder nicht, der bestimmen kann, ob eine Aussage beweisbar ist. In der Arbeit definiert Turing eine K- Maschine, die alle nachweisbaren Formeln beweist. Dies scheint fast eine Lösung für das Problem zu sein, aber später schreibt Turing:
Wenn die Negation dessen, was Gödel gezeigt hat, bewiesen wurde, dh wenn für jedes A entweder A oder -A nachweisbar ist, dann sollten wir eine sofortige Lösung des Entscheidungsproblems haben. Denn wir können eine Maschine K erfinden , die nacheinander alle nachweisbaren Formeln beweist. Früher oder später wird K entweder A oder -A erreichen . Wenn es A erreicht , wissen wir, dass A beweisbar ist. Wenn es -A erreicht , wissen wir, dass A nicht beweisbar ist , da K konsistent ist (Hilbert und Ackermann, S.65) .
Der Satz von Gödel zeigte, dass einige Aussagen wahr, aber nicht beweisbar sind. Ich glaube, ich verstehe nicht, wie Gödels Ergebnis verhindert, dass Turings K- Maschine eine Lösung für das Entscheidungsproblem darstellt. Ist es genauso einfach, dass es eine Formel gibt, auf die die K- Maschine niemals stoßen wird, so dass sie für immer weiterläuft und niemals zu dem Schluss kommt, dass die Formel nicht beweisbar ist?
Antworten:
Was Gödel gezeigt hat, ist, dass es keine endliche Axiomatisierung erster Ordnung der Theorie der natürlichen Zahlen gibt. Dies bedeutet, dass das entsprechende Beweissystem nicht alle wahren Aussagen über die natürlichen Zahlen beweisen kann, wenn Sie eine endliche Liste von Axiomen und Schemata erster Ordnung angeben. Zum Beispiel wird es nicht in der Lage sein, seine eigene Konsistenz zu beweisen (dies ist Gödels zweiter Unvollständigkeitssatz). (Ein Beweissystem ist konsistent, wenn es eine Aussage und ihre Umkehrung nicht beweist.)
Turings Maschine, wenn sie auf ein bestimmtes endliches Proofsystem erster Ordnung angewendet wirdΠ wird somit weder die Aussage beweisen können, dass Π ist konsequent noch seine Negation.
Dies ist natürlich kein Beweis dafür, dass das Entscheidungsproblem selbst unlösbar ist; Vielleicht gibt es einen ganz anderen Ansatz, der funktioniert. Turing konnte zeigen, dass tatsächlich kein (berechenbarer) Ansatz funktioniert.
quelle