Ist es möglich, dass das Stoppproblem für alle Eingaben außer dem Code der Maschine lösbar ist?

9

Diese Frage kam mir über das Problem des Anhaltens und ich konnte online keine gute Antwort finden und fragte mich, ob jemand helfen kann.

Ist es möglich, dass das Stoppproblem für jedes TM an einem Eingang entscheidbar ist, solange der Eingang nicht das TM selbst ist? Grundsätzlich:

Halts(TM, I)
    IF TM == I:
        Undecidable, return a random result/throw an exception, whatever
    ELSE:
        Solve the problem

Halts'(X)
    IF Halts(X, X):
        Loop infinitely
    ELSE:
        Print 'done'

Dies löst scheinbar den Widerspruch. Wenn wir die paradoxen Halts (Halts) nennen, können wir kein konsistentes Verhalten erwarten, aber alle anderen Aufrufe von Halts (und Halts) sind legitim und lösbar.

Ich verstehe, dass dies sehr unintuitiv ist. Wenn ein Muster in den Bits das Verhalten aller möglichen Programme aufzeigen könnte, warum würde es dann plötzlich auseinanderfallen, wenn TM und Eingang übereinstimmen? Aber können wir dies mathematisch als eine Möglichkeit eliminieren?

Und dieses reduzierte Halteproblem wäre überhaupt nicht uninteressant. Selbst wenn es ein aussagekräftiges Programm gäbe, das seinen eigenen Code als Eingabe verwendet, könnte es trivial umgeschrieben werden, um mit etwas anderen Eingaben zu arbeiten. Natürlich macht dieser Vorschlag es noch weniger verständlich, warum mit dieser einen Einschränkung eine Lösung zum Stoppen existieren könnte, aber können wir diese Möglichkeit wirklich mathematisch ausschließen?

Vielen Dank für jede Hilfe.

CS101
quelle
7
Die Entscheidbarkeit wird durch endliche Änderungen nicht beeinflusst.
Es gibt unendlich viele äquivalente TMs, und es gibt keine (entscheidbare) Möglichkeit, äquivalente TMs zu erkennen (dh es ist im Wesentlichen dasselbe wie das Stoppproblem selbst). es gibt jedoch einige komplexe "Lücken"; Versuchen Sie Computer Science Chat für eine weitere Analyse des Halteproblems im Zusammenhang mit automatisierten
Thm-Tests
Ich habe meine Frage etwas klarer formuliert. Tut mir leid, wenn ich jemanden irreführe.
CS101
Die Antwort ist nein, wie in dieser Antwort cstheory.stackexchange.com/questions/2853/…
Mohammad Alaggan

Antworten:

4

Aber wir können Ihre Einschränkung leicht umgehen. Angenommen, ein Programm kehrt die Bits der Eingabe um und ruft Ihr für das Ergebnis auf. Definieren dann mit allen umgekehrten Bits (dh 0 für 1s, 1s für 0s). Dann können wir Ihr mit aufrufen und kehren zum ursprünglichen Problem zurück.GH!HHG(!H)

Jack Aidley
quelle
Danke. Nachdem ich die Antwort von @David Richerby gelesen hatte, begann ich zu denken, dass dies die Antwort ist. Wenn wir für alle Programme Q ein funktional äquivalentes Q ' konstruieren können , können wir erneut die Haltbarkeit für alle Probleme entscheiden, nicht nur für diejenigen außerhalb der Diagonale. Ich sehe, das sagst du.
CS101
12

Erinnern Sie sich an den Standardbeweis für die Unentscheidbarkeit des Halteproblems. Nehmen wir an, dass einige Maschinen-  das Halteproblem entscheidet und lassen die Maschine, die am Eingang  verwendet  zu bestimmen , ob stoppt , und wenn ja, -  Schleifen; Andernfalls wird  angehalten. Jetzt wird genau dann angehalten, wenn es nicht anhält.Q M H M ( M ) Q Q Q ( Q )HQMHM(M)QQQ(Q)

Ist es möglich, dass das Stoppproblem für jedes TM an einem Eingang entscheidbar ist, solange der Eingang nicht das TM selbst ist?

Nein. Wenn Sie die Definition des Stoppproblems auf diese Weise ändern, funktioniert der Beweis weiterhin. Wir interessieren uns nicht , was passiert , wenn  empfängt  als Eingang , da der Widerspruch kommt , nachdem wir Eingang geben zu  .H Q , Q HHHQ,QH

Zweitens, wenn Sie modifiziert  zu erkennen , dass die Eingabe, könnten wir den gleichen Widerspruch unter Verwendung eines beliebige andere Maschine bekommen ‚die äquivalent ist  in dem Sinne , dass für jede Eingabe  ,  stoppt , wenn und nur dann , wenn ,  angehalten wird . Es gibt unendlich viele davon und  kann nicht alle erkennen, da nicht entschieden werden kann, ob zwei Turing-Maschinen gleichwertig sind.Q ' Q w Q ' ( w ) Q ( w ) H.HQQwQ(w)Q(w)H

David Richerby
quelle
3
Der letzte Absatz allein kann ausreichen, um die Frage zu beantworten: Sie können nicht alle Codierungen gleichwertiger Maschinen fest codieren, unabhängig davon, welche endliche Anpassung (basierend auf der Semantik) Sie durchführen möchten. (Das heißt nicht, dass der Rest Ihres Beitrags nicht lesenswert ist!)
Raphael
Danke für die Antwort. Ist die Unentscheidbarkeit, ob Programme funktional gleichwertig sind oder nicht, nicht selbst auf die Unentscheidbarkeit des Stoppproblems zurückzuführen? Warum sollte dies kein Zirkelschluss sein?
CS101
1
@ CS101: Die Unentscheidbarkeit von ist ein für alle Mal ein Theorem. Wir "betrügen" nicht, wenn wir damit zeigen, dass es unmöglich ist, ein anderes Problem zu lösen das versucht zu bekommen um die Einschränkung. Nebenbei bemerkt, wir wissen pragmatisch, wie man die Beendigung oder Nichtbeendigung vieler praktischer Programme (nur nicht aller Programme) nachweist. Der Nachweis der Gleichwertigkeit von Programmen erweist sich jedoch in der Praxis als erheblich schwieriger (obwohl beide unentscheidbar sind). H A L T 'HALTHALT
Cody
Ich bin verwirrt und habe vergessen, dass das Problem des vollständigen Anhaltens meiner Vermutung nach immer noch dasselbe ist. Vielen Dank.
CS101