Costruire una macchina di Turing che decide se un TM fisso si fermerà su un ingresso fisso o no

Question

noto che il problema di fermezza è decidabile per ogni fisso $ M_0 $ macchina di tentazione e ogni file fisso $ w_0 $ Input.

La mia domanda correlata sarebbe la seguente: è vero che per ogni strumento fisso $ m_0 $ macchina di tentazione e ogni file fisso $ w_0 $ ingresso, una classe $ M_ {m_0, w_0} $ Macchina per la macchina può essere costruita per la quale i possibili ingressi sono $ (m, w) $ coppie di ingresso macchina e per la $ (m_0, w_0) $ paia, l'uscita è" 1 "Se $ M_0 $ si fermerà su $ w_0 $ e" 0 "se $ M_0 $ non si fermerà su $ w_0 $ ? ( $ M_ {M_0, W_0} $ può dare risposte false per altre coppie, non è richiesto che debba funzionare correttamente per ogni $ (m, w) $ paia.)

Answer 1

poiché $ M_0 $ e $ w_0 $ sono parametri fissi del problema, la risposta è sì : per ogni file fisso $ M_0 $ e $ w_0 $ esiste una macchina di tinger $ M_ {M_0, w_0} $ (a seconda della classe $ M_0 $ e $ w_0 $ ) tale che, per l'ingresso $ (m_0, w_0) $ , $ m_ {m_0, w_0 } $ restituisce $ 1 $ se $ m_0 (w_0) $ silenzia e 0 altrimenti. < / P >.

In particolare una macchina di questo tipo di Turing $ m_ {m_0, w_0} $ deve essere una delle seguenti due macchine:

.
• $ m'_1 $ : scrivere $ 1 $ . Fermare.
• $ m'_0 $ : scrivi $ 0 $ . Fermare.

Se, invece, sei alla ricerca di un algoritmo che richiede $ M_0 $ e $ w_0 $ come input e uscite una macchina $ M_ {m_0, w_0} $ Con la proprietà sopra la proprietà, quindi sei sfortunato: non c'è un tale algoritmo in generale (potrebbe Esistono se limita il set di macchine di input $ M_0 $ ). Supponiamo che un tale algoritmo (I.e., Turing Machine) $ A $ esistesse, quindi consentirebbe di risolvere il problema di fermezza:

.
• Dato $ M_0 $ e $ w_0 $ , calcola $ M_ {m_0, w_0} $ simulando $ a $ su ingresso $ (m_0, w_0) $ .
• Simula $ m_ {m_0, w_0} $ in ingresso $ (m_0, w_0) $ . Per definizione di $ m_ {m_0, w_0} $ Questo passaggio richiede tempo finito.
• Ritorna "Sì" se l'output di $ M_ {M_0, W_0} ((M_0, w_0)) $ era $ 1 $ , altrimenti restituire "no".