Problem ohne Selbstreferenz stoppen

10

In dem Halteproblem sind wir interessiert, ob es eine Turingmaschine , die erkennen kann, ob eine gegebene Turingmaschine M an einem gegebenen Eingang i anhält oder nicht . Normalerweise beginnt der Beweis mit der Annahme, dass ein solches T existiert. Dann betrachten wir einen Fall, in dem wir i auf M selbst beschränken und dann einen Widerspruch ableiten, indem wir eine Instanz eines diagonalen Arguments verwenden. Ich bin interessiert, wie der Beweis verlaufen würde, wenn wir das Versprechen erhalten, dass ich M bin . Was ist mit dem Versprechen i M ' , wobei M ' funktional äquivalent zu M ist ?TMiTiMiMiMMM

bellpeace
quelle
2
Hinweis: Auch wenn nicht verpflichtet ist, Fragen über sich selbst oder sogar über das Äquivalent von M ' richtig zu beantworten , können wir ihm dennoch ein Äquivalent M ' geben und sehen, was es tut. Denn es ist nicht berechenbar ist , ob M ' entspricht M , M nicht in der Lage sein , es hat sich gleichwertig etwas zu erzählen. MMMMMM
Andrej Bauer
@AndrejBauer War das nur ein Hinweis, den du mir gegeben hast und ich sollte mein eigentliches Problem mit diesem Hinweis lösen? Ich bin etwas verwirrt, da Sie das Problem lockern, indem Sie "nicht erforderlich" sagen, wobei ich in meiner Einstellung verspreche, dass nicht mit einem äquivalenten M ' gefüttert wird . Grundsätzlich würde ich gerne sehen, dass jede Art von "Selbstreferenz" das ist, was Probleme unentscheidbar macht. Ich dachte, dass dies der Fall ist, wenn ich über Logik und Unvollständigkeit spreche. MM
Bellpeace
Sie können das Versprechen brechen und füttern, was Sie wollen. Es kann dir sowieso nicht sagen, dass du das Versprechen gebrochen hast. Wenn du denkst, dass das Betrug ist, dann füttere ich M Dinge, die nicht M entsprechen, weil sie wie M sind, aber alle Eingaben um 1 verschoben sind , oder so. MMMM1
Andrej Bauer
Eigentlich sind Ihre Fragen nicht gut formuliert. Sie sollten den tatsächlichen Beweis skizzieren, den Sie im Sinn haben, und dann genau angeben, was Sie vermeiden möchten. Ich glaube Sie nicht , dass , sondern etwas anderes. iM
Andrej Bauer

Antworten:

7

Angenommen, HALTS ist ein TM, das seine Eingabe als Paar und x liest , wobei M eine TM-Codierung ist und x eine beliebige Eingabe für dieses TM ist.MxMx

Ihre Frage ist ob das, was passieren würde , wenn wir davon ausgegangen , hält das Halteproblem für alle Eingänge gelöst , so dass x nicht eine Codierung eines TM ist , die funktional äquivalent zu ist M .M,xxM

Ich behaupte, dies impliziert einen Widerspruch. Ich habe mir das sofort ausgedacht, daher begrüße ich jede Kritik an meinem Beweis. Die Idee des Beweises ist, dass wir, anstatt etwas an sich zu diagonalisieren, zwei sich gegenseitig rekursive TMs erstellen, die sich bei einigen Eingaben unterschiedlich verhalten (daher nicht funktional äquivalent sind), aber ansonsten Widersprüche verursachen.

Sei und D 2 zwei gegenseitig rekursive TMs (dh wir können die Beschreibung von D 2 innerhalb des Programms von D 1 simulieren, drucken usw. und umgekehrt). Beachten Sie, dass wir aus dem Rekursionssatz gegenseitig rekursive TMs erstellen können.D1D2D2D1

Definieren Sie und D 2 wie folgt: am Eingang x , wenn | x | < 10 (10 willkürlich gewählt), dann akzeptiert D 1 und D 2 Schleifen. (Somit sind sie funktional nicht äquivalent).D1D2x|x|<10D1D2

Gegebene Eingabe mit | x | 10 definieren D 1 HALT auf simulieren D 2 , x und halt , wenn D 2 stoppt oder Schleife , wenn D 2 Schleife.x|x|10D1D2,xD2D2

Gegebene Eingabe mit | x | 10 definieren D 2 HALT auf simulieren D 1 , x und Schleife , wenn D 1 stoppt oder halt , wenn D 1 - Schleifen.x|x|10D2D1,xD1D1

Beachten Sie dann, dass für jedes mit | x | 10 , D 1 (x) hält entweder an oder schleift. Wenn D 1 am Eingang x anhält, wissen wir, dass HALTS ( D 2 , x) bestimmt hat, dass D 2 am Eingang x anhält. Das Anhalten von D 2 am Eingang x impliziert jedoch, dass HALTS ( D 1 , x) Schleifen sind.x|x|10D1D1D2D2D2D1

Wenn am Eingang x Schleifen hat, folgt der Widerspruch ähnlich.D1x

Dies ist ein Widerspruch, es sei denn, ist eine Codierung für eine Turingmaschine, die funktionell D 1 oder D 2 entspricht . In diesem Fall weist HALTS ein undefiniertes Verhalten auf. Allerdings x wurde willkürlich aus allen Saiten einer Größe von mehr als gewählt 10 . Es bleibt also zu zeigen, dass es eine Turingmaschine mit einer Codierung von mehr als 10 gibt, die sich anders verhält als D 1 und D 2 . Wir können eine solche Maschine trivial konstruieren. QED.xD1D2x10D1D2

Gedanken?

Kurt Müller
quelle
Warum müssen Sie sicherstellen, dass und D 2 nicht funktional äquivalent sind? D1D2
Bellpeace
Ich denke, Sie haben Recht, dass dies nicht notwendig ist. Meine ursprüngliche Absicht war , auf Halt (diagonalisieren )D1,D2
Kurt Mueller
Ohne das ist der Beweis eleganter, aber er sieht für mich trotzdem gut aus und ist genau das, was ich brauchte.
Bellpeace
2

Du bist immer noch nicht aus dem Wald. Sie führen in das gleiche Problem, nur jetzt Sie geben einen anderen TM, als Eingabe, in dem Sie sich entschieden haben M ' funktional äquivalent zu sein , M (sagen Sie eine neue Regel hinzuzufügen , M , so dass M ' s Öffnung bewegt sind einen Schritt nach rechts, einen Schritt nach links und ansonsten nehmen Sie keine Änderungen vor). Sie werden immer noch auf einen Widerspruch stoßen. Sie könnten versuchen, alle TMs zu entfernen, die M entsprechen , aber das ist eine unentscheidbare Menge.MMMMMM


Update . Korrigieren Sie ein Codierungsschema, bei dem Bezeichnet die Beschreibung unter diesem Schema eines TM M und nimmt an, Sie hatten ein TM, H woMMH

  • H(M,x)xHxH
  • H(M,x)M(x)

Q

Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

QHx=QQ(Q)H

Rick Decker
quelle
iM
1
Angenommen, Sie erhalten ein solches Versprechen. Ich weiß, dass es nicht berechenbar ist. Ich habe das OP aktualisiert.
Bellpeace
@bellpeace: Wie definieren Sie das überhaupt?
(M,i)iM1Mi0
1
MM