Turingmaschinen, deren Beendigung nicht beweisbar ist?

Ich habe eine naive Frage: Gibt es eine Turing-Maschine, deren Beendigung wahr ist, aber durch keine natürliche, konsistente und endlich axiomatisierbare Theorie bewiesen werden kann? Ich bitte eher um einen bloßen Existenznachweis als um ein konkretes Beispiel.

Dies könnte einen Zusammenhang mit der Ordnungsanalyse haben . In der Tat können wir für eine Turing-Maschine als die kleinste Ordnungszahl einer konsistenten Theorie definieren, die ihre Beendigung (oder das Infimum dieser Ordnungszahlen) beweist. Ich denke, es wäre äquivalent zu fragen, ob es gibt, so dass . $M$ $O(M)$ $M$ $O(M) \geq \omega_1^{CK}$

turing-machines proof-theory halting-problem Super 8
quelle

Sollte die Quantifizierung nicht umgekehrt funktionieren? Das einfache Hinzufügen von TM X-Halts als Axiom wäre für jedes X konsistent, das tatsächlich bei allen Eingaben anhält (und endlich, wenn Sie dies nur für das betreffende TM tun). Wie wäre es mit einem TM, das bei umgekehrten Quantifizierern anhält, wenn die Eingabe kein Konsistenznachweis für das axiomatische System ist und ansonsten in eine Endlosschleife eintritt?

Yonatan N

Ihr Vorschlag ist interessant, danke. Ich war mir Ihrer Besorgnis bei der Formulierung der Frage bewusst, deshalb habe ich den Anforderungen "natürlich" hinzugefügt. Das Problem ist natürlich, ob wir eine formale Definition von "Natürlichkeit" geben können, die diese künstliche Konstruktion ausschließen würde.

Super8

Ich denke, die Antwort ist nein, denn wenn es anhält, lässt man die Maschine einfach laufen und sie wird in einer endlichen Anzahl von Schritten anhalten, und das ist ein Beweis, und diese Tatsache kann in jedes einigermaßen leistungsfähige Beweissystem umgewandelt werden. Auf der anderen Seite denke ich, dass es möglich ist, das unbeweisbare Thm von Godel in eine nicht anhaltende Maschine zu codieren / umzuwandeln / zu übersetzen, für die das Nicht-Anhalten nicht beweisbar ist. Diese Frage ist ähnlich, gibt es ein TM, das bei allen Eingaben anhält, aber die Eigenschaft ist nicht nachweisbar cs.se

vzn

M

$M$

G (n)

$G(n)$

n

$n$

0

$0$

M

$M$

Danke, ich kannte diese Einträge nicht. Was ich frage, ist jedoch stärker. Ich möchte, dass keine vernünftige Theorie (und keine spezifische Theorie wie PA) widerlegbar ist . Ich bin mir nicht sicher, ob die Frage eine eindeutige Antwort hat.

Super8

Antworten:

$\Sigma^0_1$ $\Sigma^0_1$ $\Sigma^0_1$

$\Pi^0_2$ $Q$

Kaveh
quelle

Ja, ich habe nach Totalität gesucht, da das Problem für eine feste Eingabe natürlich trivial ist. Ich werde über Ihre Behauptung nachdenken und wie ich sie beweisen kann, aber an diesem Punkt sehe ich nicht, wie die Berücksichtigung von "rechnerisch axiomatisierbaren" Theorien das oben genannte Problem ausschließt? Auch in Ihrer Aussage hängt das TM von der betrachteten Theorie ab. Können wir meine stärkere Aussage durch eine Art Diagonalisierung erhalten?

Super8

Hier ist ein einfacher Weg: Die Menge der nachweislich insgesamt berechenbaren Funktionen einer solchen Theorie ist ce, die Menge der insgesamt berechenbaren Funktionen ist nicht ce, oder Sie können alternativ gegen die nachweislich Gesamtfunktionen der Theorie diagonalisieren.

Kaveh

σ

$\sigma$

α

$\alpha$

T (α, σ)

$\mathcal{T}(\alpha,\sigma)$

α

$\alpha$

M

$M$

O (M)

$O(M)$

α

$\alpha$

M

$M$

T (α, σ)

$\mathcal{T}(\alpha,\sigma)$ (dh das Notationssystem kann frei gewählt werden). Ist diese Definition sinnvoll?

Super8

@ Super8, ich bin mir nicht sicher. Im Allgemeinen ist die Zuordnung von Ordnungszahlen zu Theorien nicht kanonisch, es gibt verschiedene Möglichkeiten, dies zu tun. Sie können mit einer schwachen Theorie wie PRA beginnen und Induktion über berechenbare Ordnungszahlen mit schönen Grundsequenzen usw. hinzufügen, aber ich bin mir nicht sicher, warum Sie dies tun möchten.

Kaveh

Ok, ich hatte das Problem nicht erkannt, ich werde dann versuchen, selbst eine bessere Definition zu finden.

Super8

Ich bin kein Logikexperte, aber ich glaube, die Antwort ist nein . Wenn die Turing-Maschine anhält und das System stark genug ist, sollten Sie in der Lage sein, den vollständigen Berechnungsverlauf der Turing-Maschine auf ihre Eingabe zu schreiben. Wenn man überprüft, dass das Ergebnis der Berechnung eine abschließende Folge von Übergängen ist, kann man sehen, dass die Maschine anhält. Unabhängig davon, wie Sie Turing-Maschinen in Ihrer Theorie formalisieren, sollten Sie in jeder vernünftigen Theorie zeigen können, dass eine Maschine, die anhält, tatsächlich anhält. Stellen Sie sich analog vor, Sie wollen beweisen, dass eine endliche Summe gleich dem ist, was sie ist. beweisen Sie beispielsweise, dass 5 + 2 + 3 + 19 + 7 + 6 = 42 oder 5 + 5 + 5 = 15. So wie dies immer möglich ist, solange die Anzahl der Schritte endlich ist, beweist dies auch das Ergebnis einer endlichen Berechnung.

Nur als zusätzlicher offensichtlicher Punkt - selbst wenn Ihre Theorie inkonsistent ist, können Sie dennoch zeigen, dass die Maschine anhält, auch wenn dies nicht der Fall ist, da Sie jede wff in einer inkonsistenten Theorie beweisen können, unabhängig davon, ob dies der Fall ist oder nicht eigentlich wahr.

Philip White
quelle

Ich stimme Ihrem ersten Punkt zu, siehe meine Antwort unten. In Bezug auf Ihren zweiten Punkt wird eine inkonsistente Theorie auch die Beendigung eines (tatsächlich nicht endenden) TM beweisen, woraus sich die Beschränkung auf konsistente Theorien ergibt.

Super8

Ich denke, wir sagen dasselbe; Mir ist gerade aufgefallen, dass Sie in der Frage "konsequent" gesagt haben. Tut mir leid, dass Sie das verpasst haben. Ich denke, Kavehs Antwort deckt alle die gleichen Dinge ab und ist sowieso eleganter geschrieben.

Philip White