Decidibilidad de las máquinas de Turing que nunca mueven sus cabezas más allá de ninguna cadena de entrada

Question

$ l_1={\ langose M, w \ rangle: m \ texto {es un TM que nunca mueve su cabeza más allá de la cadena de entrada} W \ \} $
$ l_2={\ langose M \ rangle: M \ Texto {es un TM que nunca mueve su cabeza pasando por cualquier cadena de entrada} \} $

Considerar los dos idiomas anteriores.Quiero saber cuáles son decidibles.

Sé que $ l_1 $ es decidible, porque $ m $ tiene solo una cantidad finita dePosibles configuraciones con la cadena de entrada $ w $ , para que podamos crear una máquina de Turing (TM) para verificar 1 paso más allá del número de combinaciones y decidir.

Sin embargo, para $ l_2 $ , ¿podemos hacer eso?Me siento como $ l_2 $ no es decidible, porque no podemos no haber límite a las posibles configuraciones.

Answer 1

El problema de detención, $ \ mathsf {halt} $ reduce a $ \ overline {l_2} $ .

Dado un TM $ t $ y entrada $ w $ , cree una nueva clase TM $ n $ que en cualquier entrada de longitud $ n $ , simula $ T $ en la entrada $ w $ para $ n $ pasos y luego se detiene, excepto que si $ t $ detestan nunca antes de $ n $ pasos, $ N $ moverá su cabeza a la derecha para siempre.

Hay una brecha en la reducción anterior. Cuando $ n $ simula $ t $ en $ w $ para $ n $ pasos, puede salir de la entrada cuando se mueve a la izquierda (asumimos que la entrada se coloca a la derecha del origen, el Posición inicial de $ n $ 's HEAD, IN inclusivamente). Esta brecha puede ser resuelta por el truco clásico de "traducir la cinta". Cuando la simulación se trata del movimiento a la izquierda de origen, permita que $ n $ traduzca la corriente de la cinta una celda a la derecha. Luego, $ n $ va al origen, como si fuera la celda a la izquierda del origen. De esta manera, nos aseguraremos de que $ n $ nunca se mudará de la cadena de entrada siempre y cuando el contenedor de matemáticas "Span Class=" simulado "> $ t $ en $ w $ no se detiene. (Para habilitar $ n $ para reconocer el origen, siempre debe marcar el origen con un símbolo "compuesto" que también cuenta su símbolo original. Por ejemplo, si el original El símbolo en el origen es $ A $ , $ n $ debe cambiarlo a $ A_O $ , un símbolo que no es $ A $ pero apunta a $ a $ . "Los símbolos" compuestos también se usan cuando $ n $ traduce el contenido de la cinta.)

desde $ \ mathsf {halt} $ no es decidible, $ \ overline {l_2} $ no es decidible Entonces, $ l_2 $ no es decidible.