Nachweis der Unentscheidbarkeit nicht durch Reduzierung des Halteproblems

13

Der übliche Weg, die Unentscheidbarkeit zu beweisen, ist die Reduktion von einem RE-vollständigen Problem, wie dem Halteproblem, der Gültigkeit in der Logik erster Ordnung, der Erfüllbarkeit von Diophantin-Gleichungen usw.

Es ist bekannt, dass es rekursiv aufzählbare, aber unentscheidbare Probleme gibt, die nicht RE-vollständig sind, sondern künstliche Konstruktionen (dh Mengen, die nur zum Anzeigen dieses "Dichte" -Ergebnisses definiert wurden).

Wie würde man es angehen, die Unentscheidbarkeit zu beweisen, ohne ein RE-vollständiges Problem zu lösen? Diagonalisierung?

David Monniaux
quelle
4
Vielleicht ist die richtige Frage: "Was sind die verschiedenen direkten Methoden, um Unentscheidbarkeit zu beweisen?"
Suresh Venkat
Das Unvollständigkeitstheorem von Godel wird als ein "anderer Weg" angesehen. Ein weiterer Beweis für die Diagonalisierung beruht darauf, dass die Anzahl der Programme / Eingabepaare abzählbar ist, die Sprachen jedoch unzählbar sind mit den ganzen Zahlen. siehe auch dieses Q / A zu Lawvere-Fixpunktsatz
vzn
6
@vzn: Ich halte Gödel Unvollständigkeit im Wesentlichen für den gleichen Beweis ...
Joshua Grochow
Nur aus Neugier, für welche Art von Problem oder Sprache versuchen Sie Unentscheidbarkeit zu beweisen? Ich denke, dass es viele bekannte, unentscheidbare Probleme gibt (siehe zum Beispiel eine kleine Liste auf Wikipedia), die Sie reduzieren können. Daher frage ich mich, ob mindestens eines Ihrer Probleme ähnlich ist oder ob es ein völlig neues Problem ist.
Marzio De Biasi

Antworten:

10

Man kann ziemlich direkt zeigen, dass die Kolmogorov-Komplexität nicht berechenbar ist, siehe zB Sipser, 3. Auflage, Problem 6.23.

Bjørn Kjos-Hanssen
quelle
Dies sollte sich auch direkt aus Chaitins Unvollständigkeitssatz ergeben , dessen Beweis ziemlich ähnlich ist.
Yonatan N
Ausgehend von den vorherigen Problemen scheint es mir, dass Sipser den Studenten vorschlägt, die Unentscheidbarkeit des Halteproblems für diesen Beweis heranzuziehen. Vielleicht lohnt es sich daher, in der Antwort den direkten Beweis der Unberechenbarkeit zu skizzieren.
Usul
Ein Vergleich mit den Übungen 6.24 und 6.25 hilft auch.
Bjørn Kjos-Hanssen
2
Ich hielt es für erwähnenswert, darauf hinzuweisen, dass der Beweis, dass K nicht berechenbar ist, im Wesentlichen auch Diagonalisierung ist, da der OQ speziell nach der Diagonalisierung gefragt hat. (Tatsächlich ist es im Grunde die selbe, einfache Vanille-Diagonalisierung, die verwendet wird, um HALT als unberechenbar zu beweisen. Dies ist das Gleiche wie Cantors ursprünglicher Beweis über Kardinalitäten. Versionen von Russells Paradoxon ...
Joshua Grochow
10

Überlegen Sie, wie ich das Problem der beständigen Vermutung bezeichne.

Als Eingabe wird eine Beschreibung einer Turingmaschine :M

  • Wenn auf einem leeren Band akzeptiert, müssen Sie akzeptieren.M

  • M

  • M

(Natürlich ist dies keine richtige Sprache, sondern eher ein Vergleich der Berechenbarkeit eines Versprechensproblems.)

Nun, durch eine Modifikation von Turings Originalbeweis, ist es ziemlich einfach zu zeigen, dass das beständige Raten unentscheidbar ist (ich werde das als Übung für Sie belassen).

EINEIN

Scott Aaronson
quelle
Danke, aber ... wieder ein Diagonalisierungsnachweis. ;-) Mein Problem ist, dass ich etwas habe, das ich für unentscheidbar halte (im Grunde haben die Leute seit über 35 Jahren immer nach heuristischen Algorithmen oder Algorithmen gesucht, die für Unterklassen gültig sind, um es zu lösen), für das es aber anscheinend keine "offensichtlichen" gibt. Verkleinerungen von wieder noch ein nettes Diagonalisierungsargument ...
David Monniaux
Beachten Sie, dass es keine "natürlichen" Probleme gibt, von denen bekannt ist, dass sie unentscheidbar sind, die jedoch keine (bekannte) Turing-Reduktion auf das Halteproblem aufweisen. Insbesondere besteht der einzige "empfohlene" Ansatz, um zu zeigen, dass etwas unentscheidbar ist, darin, es auf ein anderes unentscheidbares Problem zu reduzieren (z. B. Semi-
Unification
cody: Das habe ich auch gedacht. Aber wenn Sie bereit sind, allgemeinere Aufgaben als die Entscheidung für eine Sprache zu berücksichtigen, dann ist KONSTANTES RATEN ein ziemlich natürliches Gegenbeispiel! (Übrigens, ich nehme an, Sie meinten, die bekannten, unentscheidbaren Probleme auf Ihr Problem zu reduzieren, anstatt umgekehrt.)
Scott Aaronson
5

Wenn Sie nach einem Beweis suchen, der weder a) eine Reduzierung eines bekannten vollständigen Problems noch b) eine einfache Diagonalisierung (auf die Ihre verschiedenen Kommentare hinweisen) ist, dann haben Sie meines Erachtens kein Glück. Alle Beweise, die mir bekannt sind, sind nicht durch Reduktion entstanden - auch nicht durch die anderen hervorragenden Antworten von Aaronson und Kjos-Hanssen -, sondern durch eine einfache Diagonalisierung.

Und all diese Diagonalisierungen sind im Wesentlichen der gleiche Beweis . Einige von ihnen sind geringfügige Varianten des Beweises, die geringfügig stärkere / schwächere Aussagen ergeben, aber die Beweise selbst sind typischerweise nur geringfügige Abweichungen. (Und all diese Beweise sind im Wesentlichen die gleichen wie Cantors ursprünglicher Beweis über Kardinalitäten, der den Beweisen für die Unvollständigkeit von Gödel und Chaitin entspricht, die alle nur Theorem-Versionen von Russells Paradoxon sind ... So sehr, dass auf einen Ich habe mich gefragt, ob man einen Satz, der besagt, dass es im Wesentlichen nur einen solchen Beweis gibt, auf irgendeine Art und Weise in umgekehrter Mathematik formalisieren kann.)

Es kann jedoch erwähnenswert sein, dass es Beweise für andere Aussagen - typischerweise mit einem anderen Geschmack - gibt, bei denen es sich um Diagonalisierungen handelt, die sich tatsächlich nachweislich von der Diagonalisierung unterscheiden, die verwendet wird, um beispielsweise die Unentscheidbarkeit des Halteproblems zu beweisen.

Joshua Grochow
quelle
5
Ich weiß nicht viel über dieses Thema, aber ist Lawvere's Fixpunktsatz nicht eine gemeinsame Verallgemeinerung von fast all diesen?
Sasho Nikolov