Problema di arresto per la macchina di tentazione fissa e input fisso

Question

È noto che il problema di fermezza è indecidabile anche quando risolviamo la macchina di turing $ m $ o L'ingresso $ W $ .

Cosa succede se ha risolto sia la macchina che l'ingresso?Cioè, è decidabile per ogni macchina fissa di Turing $ M_0 $ e ogni ingresso fisso $ w_0 $ $ M_0 $ si fermerà su $ w_0 $ come input?

Answer 1

.

È noto che il problema di fermezza è indecidabile anche quando risolviamo la macchina di turing $ m $ o L'ingresso $ W $ .

Devi essere più attento a questa affermazione. Non è vero per qualsiasi macchina di tentazione fissa $ m $ che il problema di blocco $ \ testo {halt} _m $ (decidere su input $ w $ se $ m $ halts on $ W $ ) è indecidabile. Ad esempio, se $ m $ è una macchina che si ferma sempre, possiamo facilmente decidere $ \ testo {halt} _m $ Solo spostando "sì".

Quello che probabilmente volevi dire è i seguenti fatti, che sono vere:

.

1. esiste una macchina di turing $ m $ in modo tale che il problema $ \ testo {halt} _m $ (decidere su ingresso $ W $ se $ m $ interruzioni su $ W $ ) è indecidabile.

2. per tutti parole $ w $ , il problema $ \ text { Halt} _w $ (decidere su ingresso $ m $ se $ m $ si ferma su < Span Class="Math-Container"> $ W $ ) è indecidabile.

In particolare per il fatto 1, possiamo prendere $ m $ per essere la macchina di turing universale.

.

Cosa succede se ha risolto sia la macchina che l'ingresso? Cioè, è decidabile per ogni macchina fissa di Turing $ M_0 $ e ogni ingresso fisso $ w_0 $ < Span Class="Math-contenitore"> $ M_0 $ si fermerà su $ w_0 $ come input?

Sì, il problema diventa banale decidabile. Definire la lingua $ \ Text {HALT} _ {M_0, W_0} $ Per essere il problema di decidere se $ M_0 $ interruzioni su $ w_0 $ . Ma notare che questo problema non ha più alcun input che dipende dalla risposta, poiché entrambe le cose che la risposta potrebbe dipendere da ( $ m_0 $ e $ W_0 $ ) Ora è fisso, vale a dire parte della definizione della lingua, non parte dell'ingresso. Ciò significa che la risposta è solo "sì" o "no". Quindi possiamo istalmente decidere questo problema o utilizzando un programma che dice sempre "sì" o un programma che dice sempre "no".

Questa è una trabosizione comune sulla decidabilità: è utile solo chiedere se un problema è decidabile o meno quando il numero di possibili ingressi è infinito. Se ci sono solo molti input possibili, quindi Tutti i problemi diventano decidabili. Hai chiesto se un problema con solo 1 possibile ingresso (l'ingresso vuoto) è decidabile e la risposta a questo è sempre sì.