Gibt es eine Turing-Maschine, die bei allen Eingaben anhält, aber diese Eigenschaft ist aus irgendeinem Grund nicht nachweisbar?
Ich frage mich, ob diese Frage untersucht wurde. Beachten Sie, dass "unbeweisbar" ein "eingeschränktes" Beweissystem bedeuten kann (das im schwachen Sinne der Meinung ist, dass die Antwort ja sein muss). Ich interessiere mich natürlich für die bestmögliche Antwort, dh eine, die nicht nachweislich bei allen Eingaben in der ZFC-Mengen-Theorie oder was auch immer zum Stillstand kommt .
Mir ist aufgefallen, dass dies für die Ackermann-Funktion zutreffen könnte, aber ich bin bei den Details verschwommen. Wikipedia scheint diesen Aspekt nicht klar zu beschreiben.
Antworten:
Ja. Die Turing-Maschine, die die Goodstein-Sequenz beginnend mit ihrer Eingabe berechnet und endet, wenn die Sequenz Null erreicht. Es endet immer, aber dies kann in der Peano-Arithmetik nicht bewiesen werden. Ich bin mir sicher, dass es für ZFC oder jedes andere System, das Sie wählen könnten, äquivalente Dinge gibt.
Siehe Kap. 3 von Scott Aaronsons Umfrage zur Unabhängigkeit von P = NP für eine Darstellung des Hartmanis-Hopcroft-Ergebnisses und von Zitaten in ihren Originalarbeiten.
quelle
quelle
Einige in PA nicht beweisbare, aber wahre Theoreme können in Turing-Maschinen umgewandelt werden. Zum Beispiel gibt es eine (verstärkte) Version von Ramseys Theorem , die in PA nicht beweisbar ist, und wir können eine Maschine konstruieren, die nur nach dem richtigen sucht .N
quelle