Halteproblem, nicht berechenbare Mengen: gemeinsamer mathematischer Beweis?

29

Es ist bekannt, dass wir mit einer abzählbaren Menge von Algorithmen (gekennzeichnet durch eine Gödel-Zahl) nicht alle Teilmengen von N berechnen können (einen binären Algorithmus erstellen, der die Zugehörigkeit prüft).

Ein Beweis könnte wie folgt zusammengefasst werden: Wenn wir könnten, wäre die Menge aller Teilmengen von N zählbar (wir könnten jeder Teilmenge die Gödel-Zahl des Algorithmus zuordnen, der sie berechnet). Da dies falsch ist, beweist es das Ergebnis.

Dies ist ein Beweis, den ich mag, da er zeigt, dass das Problem äquivalent zu den nicht abzählbaren Teilmengen von N ist.

Jetzt möchte ich beweisen, dass das Stopp-Problem nicht mit demselben Ergebnis lösbar ist (Unzählbarkeit von N Teilmengen), weil ich denke, dass dies ein sehr nahes Problem ist. Kann man das so beweisen?

computability halting-problem Weier
quelle
Es ist klar, dass beide Ergebnisse mit derselben Technik (Diagonalisierung) bewiesen werden können. Ich glaube jedoch nicht, dass es möglich ist, die Unentscheidbarkeit des Halteproblems zu beweisen, indem man einfach die Unzählbarkeit der Familie von Teilmengen von ℕ verwendet, da es bei ersterer um den Vergleich zwischen RE und R geht , die beide zählbare Familien von R sind Teilmengen von ℕ.
Tsuyoshi Ito
Es gibt nur unzählige Programme mit Zugang zum Orakel, die wiederum durch eine Gödelzahl gekennzeichnet sind. Das Problem des Anhaltens ist jedoch in dieser abzählbaren Menge enthalten.
David Harris

Antworten:

42

e:A→(A⇒B)f:B→B

Eine nette Einführung in diese Ideen finden Sie in diesem Blog-Beitrag von Andrej Bauer .

Neel Krishnaswami
quelle
7
das ist ziemlich ordentlich. Mir war nicht klar, dass es tatsächlich ein formelles Argument gab, das sie vereinte.
Suresh Venkat
8
Ich habe inzwischen gelernt zu vermuten, dass es, wenn es gleich aussieht und gleich riecht, ein kategorisches Argument darüber gibt, in welchem ​​Sinne es dasselbe ist.
Vijay D
2
IMO, die zwei wirklich schönen Dinge an Lawvere's Theorem sind: (a) es ist eine positive Aussage und keine negative Aussage, und (b) der Beweis besteht aus einem halben Dutzend Zeilen einfacher Lambda-Kalkül-Berechnungen.
Neel Krishnaswami
6
Als ich die Frage las, dachte ich mir, dass jemand Lawvere Fixpunktsatz erwähnen sollte. Stellen Sie sich meine Freude vor, wenn ich die Antwort lese :-)
Andrej Bauer
1
Das epimorphe Sein ist nicht die richtige Bedingung. Sie brauchen Punkt-Surjektivität, die die Bedingung des epimorphen Seins weder impliziert noch impliziert. Siehe Bemerkung 2.3 ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem
fhyve