Gibt es einen versteckten Zusammenhang zwischen der Existenz unzähliger Mengen und der Unentscheidbarkeit des Halteproblems?

9

Da beide Beweise das diagonale Argument verwenden, frage ich mich, ob es einen obskuren Zusammenhang zwischen der Existenz unzähliger unendlicher Mengen und der Unentscheidbarkeit des Halteproblems gibt. Wäre das Stoppproblem entscheidbar, wenn alle Sätze abzählbar wären?

halting-problem Lenar Hoyt
quelle
10
Ja, das diagonale Argument!
Mahdi Cheraghchi
1
@MCH Mein Gedanke war, dass es neben dem diagonalen Argument, das beide verbindet, vielleicht eine andere Charakterisierung gibt. Diese Frage ist für SE vielleicht zu verschwommen.
Lenar Hoyt
4
Dies kann eine teilweise Verknüpfung sein: Es ist klar, dass die Menge aller Sprachen über ein bestimmtes Alphabet unzählig ist. Der Satz aller Turingmaschinen ist jedoch zählbar. Dies impliziert direkt die Existenz unentscheidbarer Probleme. Diese Argumentation impliziert jedoch nichts über das Stoppproblem.
042
9
Es gibt sicherlich satztheoretische Modelle von ZFC, bei denen alle Mengen zählbar sind (obwohl nicht innerhalb des Modells), aber das Stoppproblem ist immer unentscheidbar. Siehe diese MathOverflow-Frage .
Peter Shor
4
Bitte, bitte, bitte sagen Sie von nun an Unentscheidbarkeit.
Vijay D

Antworten:

14

Es ist keine versteckte Verbindung, sondern eine, die mit der Sprache der Kategorietheorie explizit gemacht wurde und auch eine sehr natürliche Frage ist, die gestellt und studiert werden muss. Es gibt einiges an Material zu diesem Thema.

Vijay D.
quelle