Erstellen einer Turiermaschine, die entscheidet, ob ein fester TM an einem feststehenden Eingang hält oder nicht

Question

es ist bekannt Dass das Anhalten des Anhaltensproblems für jeden festen $ M_0 $ Turing-Maschine und jeder feste $ w_0 $ Eingang.

Meine bezogene Frage wäre das Folgende: Ist es richtig, dass für jeden festen $ M_0 $ Turing-Maschine und jeden festen $ w_0 $ input, ein $ m_ {m_0, w_0} $ Turing-Maschine kann aufgebaut sein, für die die möglichen Eingänge $ (M, W) $ Maschineneingabepaare, und für den $ (M_0, W_0) $ Paar, ist der Ausgang" 1 "Wenn $ M_0 $ auf $ W_0 $ und" 0 "haltet, wenn $ M_0 $ wird nicht auf $ w_0 $ halt>? ( $ m_ {m_0, w_0} $ kann falsche Antworten für andere Paare geben, es wird nicht verlangt, dass es für jede $ (M, W) $ Paar.)

Answer 1

seit $ m_0 $ und $ w_0 $ sind feste Parameter des Problems, die Antwort ist ja : Für jeden festen $ M_0 $ und $ w_0 $ gibt es eine Turing-Maschine $ M_ {M_0, W_0} $ (je nach $ m_0 $ und $ w_0 $ ) so, dass für den Eingang $ (m_0, w_0) $ , $ m_ {m_0, w_0 } $ Returns $ 1 $ Wenn $ M_0 (W_0) $ haltet> ansonsten und 0 ansonsten. < / p>

Insbesondere eine solche Turing-Maschine $ M_ {M_0, W_0} $ muss einer der folgenden zwei Maschinen sein:

• $ m'_1 $ : schreibe $ 1 $ . Halt.
• $ m'_0 $ : schreibe $ 0 $ . Halt.

Wenn Sie stattdessen einen Algorithmus suchen, der $ M_0 $ und $ w_0 $ an Als Input und Ausgänge ein Maschine $ M_ {M_0, W_0} $ mit der oben genannten Eigenschaft, dann sind Sie nicht Glück: Es gibt keinen solchen Algorithmus im Allgemeinen (es könnte sein) Gibt es, wenn Sie den Satz von Eingabemaschinen einschränken $ M_0 $ ). Angenommen, ein solcher Algorithmus (d. H., Turing-Machine) $ A $ existierte, dann würde es erlauben, das Anhalten des Anhaltens zu lösen:

• gegeben $ M_0 $ und $ w_0 $ , berechnen $ M_ {m_0, w_0} $ Durch Simulieren von $ A $ bei input $ (M_0, W_0) $ .
• Simulieren $ M_ {M_0, W_0} $ bei input $ (M_0, W_0) $ . Definition von $ M_ {M_0, W_0} $ Dieser Schritt erfordert eine endliche Zeit.
• Gibt "Ja" zurück, wenn der Ausgang von $ M_ {M_0, W_0} ((M_0, W_0)) $ $ 1 $ , sonst zurücksenden "Nein".