Unentscheidbarkeit, ob ein Programm wahr oder falsch zurückgibt

7

Betrachten Sie das Problem, eine Eingabe-Turing-Maschine zu nehmen und festzustellen, ob die endgültige Zelle a ist 0 oder 1nach der Berechnung wird angehalten. In Fällen, in denen etwas anderes geschrieben wird oder nicht angehalten wird, dürfen Sie eine Antwort geben (aber Sie müssen anhalten und auf alle Eingaben eine Antwort geben).

Ist dieses Problem unentscheidbar? Mein Bauch sagt, dass es sein sollte, aber ich kann keine Reduzierung des Halteproblems finden. Bei einer Turing-Maschine, die möglicherweise anhält oder nicht, können wir die Maschine so einrichten, dass sie mit a endet0 für den Fall, dass es anhält, aber im ununterbrochenen Fall mit nichts fertig werden kann, könnte das Orakel einfach sagen 0 in diesem Fall, ohne herausfinden zu müssen, ob die Maschine tatsächlich anhält.

Beachten Sie, dass eine Reduzierung in die andere Richtung einfach ist. Wenn Sie das Problem des Anhaltens lösen können, geben Sie ein TM ein, das entweder mit endet0 oder 1ersetzen wir die 1-Schreibschritt mit einer Endlosschleife zum Erstellen eines neuen TM. Wenn das neue TM anhält, sagen wir "es schreibt a0"und wenn es nicht aufhört, sagen wir", schreibt es a 1". Diese Antwort ist garantiert richtig, solange das TM tatsächlich mit a anhält 0 oder 1, damit wir das ursprüngliche Problem lösen können.

Mario Carneiro
quelle

Antworten:

8

Angenommen, Sie haben eine Funktion wie die von Ihnen beschriebene:

def haltify(f):
    # Never fails to halt.
    # If 'f' halts, returns f().
    # If 'f' doesn't halt, anything could be returned.
    ... magic ...

Aber dann kommt jemand und macht das:

def evil():
    return not haltify(evil)

Sehen Sie das Problem?

  1. Wenn haltify(f)garantiert für alle angehalten wird f, evilwird auch angehalten, weil es nur haltifyeine bestimmte aufruft fund die Ausgabe invertiert.
  2. Da evilhält an, haltify(evil)muss gleich bewertet werden wie evil().
  3. Also not haltify(evil)vereinfacht sich not evil()und das evil()kehrt zurück.
  4. Das ist ein Problem, denn es gibt keine xBefriedigung x == not x. Das Ergebnis des Bösen ist widersprüchlich.
  5. Daher ist eine der von uns verwendeten Annahmen falsch: Entweder haltifywird nicht garantiert, dass sie anhält, oder es wird nicht garantiert, dass sie zurückkehrt, f()wenn ein Anhalten bestanden wird f.

def good(): return haltify(good)Bonusübung : Warum verursacht die Funktion keine Probleme beim Anhalten, obwohl sie anscheinend auf die Endlosschleife vereinfacht wird def good(): return good()?

Craig Gidney
quelle
Sehr schön. Dies ist isomorph zu Yuvals Antwort, aber etwas weniger umwerfend prägnant. Re: Bonus, haltifykann das Ergebnis von auswählen good()und ist in beiden Fällen selbstkonsistent, kehrt aber trotzdem zurück, weil (durch Voodoo-Magie) haltify(good)angehalten wird, so dass es sich nicht um eine Endlosschleife handelt, sondern vielmehr um eine Einschränkung des Antworten. (In Wirklichkeit besteht der Weg zur Implementierung haltifynur darin, das Argument auszuführen. In diesem Fall werden beide goodund evildurch Divergenz vor Widersprüchen bewahrt, aber dann müssen wir natürlich zulassen haltify, dass wir auseinander gehen, was den Punkt
zunichte macht
Eine weitere interessante Frage ist, ob es möglich ist, einen "optimierenden Compiler" zu schreiben, der eine Eingabe TM verwendet T und gibt einige aus Tdas berechnet das gleiche Ergebnis, aber schneller. Die Antwort hängt stark von den Details der Maschinen ab und ist ein aktives Forschungsgebiet. Dieses Ergebnis zeigt, dass für einen solchen Compiler zumindest einige unendliche Berechnungen nicht "beschleunigt" werden können, um in endlicher Zeit ausgeführt zu werden (was eine Art unendliche Version des Inkompressibilitätssatzes für Codierungsschemata ist).
Mario Carneiro
@MarioCarneiro Die endliche Version gilt auch hier: Es gibt zumindest einige Turing-Maschinen, die immer in endlicher Zeit ausgeführt werden, aber nicht beschleunigt werden können.
John Dvorak
Ist IEEE 754 nicht NaNzufriedenstellend x == !x?
Katze
@tac Wird in Python not float('nan')als falsch ausgewertet. notist auch einer der Operatoren, die Sie nicht überladen können. es gibt immer einen Bool zurück. (Sie können eine benutzerdefinierte Konvertierung in Bool definieren, der Interpreter überprüft jedoch, ob Sie tatsächlich einen Bool zurückgegeben haben.) Selbst wenn es einen hackigen Weg gibt, eine xPython- Version zu erstellen, die zufriedenstellend ist x == not x, sollte das Beispiel nur pädagogisch korrekt und nicht pedantisch korrekt sein.
Craig Gidney
6

Nehme an, dass Mist eine Maschine, die dieses Problem löst; Ich nehme das anMakzeptiert eine Turing-Maschine und eine Eingabe, aber Sie können festlegen, dass eine Turing-Maschine nur akzeptiert wird, wenn Sie dies bevorzugen. Wir bauen eine andere MaschineTdas funktioniert wie folgt. Bei Eingabex, es läuft M an der Maschine x und Eingabe x, zeichnet die Ausgabe als auf bund schreibt 1bin der Anfangszelle. Jetzt rennT auf sich selbst einen Widerspruch zu erreichen.

Yuval Filmus
quelle
1
Funktioniert nicht. Ersetzen Sie die folgende Einschränkung im ursprünglichen Problem. Die Eingabe der Turingmaschine bleibt garantiert stehen. Tatsächlich ist diese Reduzierung auch für das Stoppproblem falsch, aber aus ganz offensichtlichen Gründen.
Joshua
Ich sehe das Problem nicht. Vielleicht könntest du es erklären?
Yuval Filmus
1
Wenn die Eingabe garantiert angehalten wird, muss die Maschine sie lediglich ausführen, um die Antwort zu finden, und kann dies daher nicht verfehlen.
Joshua
1
Jedem sein eigenes.
Yuval Filmus
@Joshua: Wollen Sie damit sagen, dass alle Eingabe-Turing-Maschinen garantiert angehalten werden oder dass eine bestimmte Eingabe-Turing-Maschine garantiert angehalten wird? Es gibt keine Garantie dafür, dass alle Eingaben anhalten und fürMUm die Eingabe "nur auszuführen", müsste sie die stoppenden Eingaben identifizieren.
user2357112 unterstützt Monica
-3

Ihre Reduzierung auf das Halteproblem ist logischerweise unkompliziert. Wenn Ihre Maschine anhält, muss sie aufgrund einer primitiven Konstruktion ihrer Eingabe in einiger Zeit T anhalten. Wenn das Halteproblem nicht lösbar ist, muss die Konstruktion verlustbehaftet sein. Daher gibt es eine Maschine, für die sie falsch vermutet und anhält, ohne vollständig bewertet zu werden, und eine lange Kette von XOR erzwingt eine vollständige Bewertung, um die richtige Antwort zu erhalten. Daher gibt es eine Maschine, für die sie die falsche Antwort liefert.

Tatsächlich reduziert sich jedes nicht triviale Problem, das nicht anhaltende Maschinen nicht als Eingabe ausschließt, auf diese Weise auf das Stoppproblem. Ref: https://en.wikipedia.org/wiki/Rice's_theorem

Joshua
quelle
2
Ihre Antwort macht leider nicht viel Sinn.
Yuval Filmus
Ich habe keine Ahnung, was Ihr letzter Absatz bedeuten soll. Die meisten Probleme reduzieren sich nicht auf das Problem des Anhaltens. zB ist der Satz von Turing-Maschinen, die bei jeder Eingabe anhalten, nicht auf das Halteproblem reduzierbar, sondern von streng größerer Komplexität(0>T0).
Noah Schweber
@NoahSchweber: Es ist ein tiefer Satz der Informatik. Sie können keine nicht trivialen Eigenschaften aller untypisierten rekursiven Funktionen nachweisen, da Sie das Stoppproblem nicht lösen können. Sie müssen Ihre Problemdomäne auf rekursive Funktionen beschränken, die anhalten.
Joshua
Der Satz von @Joshua Rice ist kein "tiefer Satz der Informatik", sondern ein sehr grundlegender Satz der Berechenbarkeitstheorie. Und es bedeutet nicht, was Sie zu bedeuten scheinen - das Problem des Anhaltens bedeutet ein sehr schwaches Maß an Unentscheidbarkeit. (Der Satz von Rice besagt das Gegenteil von dem, was Sie geschrieben haben: Er besagt, dass das Stoppproblem auf jede "nichttriviale Eigenschaft partiell berechenbarer Funktionen" reduziert werden kann, dh von gleicher oder geringerer Komplexität ist als es lohnt sich, die Grundlagen noch einmal zu überprüfen; Kennen Sie zum Beispiel die Tatsache, dass ich oben erwähnt habe ( )? 0>T0
Noah Schweber