Decidabilità delle macchine di tentazione che non muovono mai le loro teste oltre nessuna stringa di input

Question

.

$ l_1={\ Langle m, w \ rangle: m \ text {è un tm che non sposta mai la testa oltre la stringa di ingresso} w \} $
. $ l_2={\ Langle m \ Rangle: m \ text {è un TM che non sposta mai la sua testa oltre la stringa di ingresso} \} $

Considera le due lingue sopra.Voglio sapere quali sono decidabili.

So che $ l_1 $ è decidabile, perché $ m $ ha solo una quantità finita diPossibili configurazioni con la stringa di ingresso $ W $ , quindi possiamo creare una macchina di tentazione (TM) per controllare 1 passo oltre il numero di combinazioni e decidere.

Tuttavia, per $ l_2 $ , possiamo farlo?Mi sento come $ l_2 $ è indecidibile, perché possiamo esserci alcun limite alle possibili configurazioni.

Answer 1

Il problema di interruzione, $ \ mathsf {halt} $ riduce a $ \ overline {l_2} $ .

Dato un TM $ T $ e ingresso $ W $ , creare una nuova classe TM $ N $ su qualsiasi ingresso di lunghezza $ n $ , simula $ T $ su input $ W $ per $ n $ passaggi e quindi si ferma se non $ T $ mai fermi prima $ n $ passaggi, $ N $ sposterà la testa a destra per sempre.

C'è un gap nella riduzione di cui sopra. Quando $ N $ simula $ t $ su $ w $ per $ N $ passaggi, può spostarsi dall'input quando si sposta a sinistra (assumiamo che l'input sia messo a destra dell'origine, il Posizione iniziale di $ N $ head, inclusivamente). Questo gap può essere risolto dal classico trucco di "tradurre il nastro". Quando la simulazione riguarda la mossa a sinistra dell'origine, lasciare $ N $ Traduci la corrente del nastro una cella a destra. Quindi $ N $ va all'origine, come se fosse la cella a sinistra dell'origine. In questo modo, ci assicureremo $ N $ non sposterà mai dalla stringa di ingresso fintanto che la simulata $ t $ on $ W $ non si ferma. (Per abilitare $ N $ Per riconoscere l'origine, dovrebbe sempre contrassegnare l'origine con un simbolo "composto" che racconta anche il suo simbolo originale. Ad esempio, se l'originale simbolo all'origine è $ a $ , $ N $ dovrebbe cambiarlo in $ A_O $ , un simbolo che non è $ a $ ma punti a $ a $ . I simboli "Compound" vengono anche utilizzati quando $ N $ Traduce il contenuto del nastro.)

Dal momento che $ \ mathsf {halt} $ non è decidabile, $ \ overline {l_2} $ non è decidabile. Quindi, $ l_2 $ non è decidabile.