Decidibilidade de máquinas de Turing que nunca movem suas cabeças além de qualquer sequência de entrada

Question

$L_1 = \{ \langle M, w angle :M ext{ é uma TM que nunca passa da string de entrada } w \}$
$L_2 = \{ \langle M angle :M ext{ é uma TM que nunca passa de qualquer string de entrada} \}$

Considere as duas linguagens acima.Quero saber quais são decidíveis.

eu sei que $L_1$ é decidível, porque $M$ tem apenas uma quantidade finita de configurações possíveis com a string de entrada $w$, para que possamos criar uma Máquina de Turing (TM) para verificar 1 passo além do número de combinações e decidir.

No entanto, para $L_2$, Podemos fazer isso?Sinto-me como $L_2$ é indecidível, porque podemos, parece não haver limite para as configurações possíveis.

Answer 1

O problema da parada, $\mathsf{HALT}$ reduz para $\overline{L_2}$.

Dado um TM $T$ e entrada $w$, crie uma nova TM $N$ que em qualquer entrada de comprimento $n$, simula $T$ na entrada $w$ para $n$ passos e depois para, exceto que se $T$ já parou antes $n$ passos, $N$ moverá sua cabeça para a direita para sempre.

Há uma lacuna na redução acima.Quando $N$ simula $T$ sobre $w$ para $n$ etapas, ele pode sair da entrada quando se move para a esquerda (assumimos que a entrada é colocada à direita da origem, a posição inicial de $N$cabeça, inclusive).Essa lacuna pode ser resolvida com o clássico truque de “traduzir a fita”.Quando a simulação é sobre o movimento para a esquerda da origem, vamos $N$ transfira a corrente da fita uma célula para a direita.Então $N$ vai para a origem, como se fosse a célula à esquerda da origem.Desta forma, teremos certeza $N$ nunca sairá da string de entrada enquanto o simulado $T$ sobre $w$ não para.(Para ativar $N$ para reconhecer a origem, deve sempre marcá-la com um símbolo “composto” que também indique o seu símbolo original.Por exemplo, se o símbolo original na origem for $A$, $N$ deveria mudar para $A_o$, um símbolo que não é $A$ mas aponta para $A$.Símbolos "Compostos" também são usados ​​quando $N$ traduz o conteúdo da fita.)

Desde $\mathsf{HALT}$ não é decidível, $\overline{L_2}$ não é decidível.Então, $L_2$ não é decidível.