Desde el cinta de trabajo es finito que sólo tendrá un número finito de configuraciones posibles, por lo que podemos desechar la cinta de trabajo y considerar su configuración como parte del estado.
Lo que tenemos entonces es una máquina de Turing completamente de sólo lectura, pero aún bidireccional, y se nos pide que demostremos que tales máquinas tienen la misma potencia que las máquinas de sólo lectura que sólo pueden moverse hacia la derecha (es decir, DFAs).
Sin embargo, al disponer de un número suficiente de estados, podemos simular la ejecución de la máquina bidireccional en una sola pasada hacia delante. Todo lo que necesitamos recordar en cada casilla a la que lleguemos es:
- ¿Qué estado es el primero estado en que la máquina bidireccional llegará a esta plaza?
- Para cada Estado $s$ si la máquina bidireccional se mueve a la izquierda de esta casilla y entra en el estado $s$ ¿en qué estado siguiente ¿llegar a esta plaza? ¿O tal vez aceptará antes de volver a esta casilla, o divergirá sin volver a esta casilla?
Sólo hay $S(S+2)^S$ muchos conjuntos diferentes de respuestas a estas preguntas, que son finitamente muchos. Y para cada conjunto de respuestas, combinado con un símbolo de entrada, podemos calcular de una vez por todas (es decir, mientras generamos nuestro DFA) cuál será el conjunto de respuestas correspondiente para el siguiente cuadrado.
(La frase final del párrafo anterior exige, por supuesto, una prueba explícita, cuyos detalles dejaré a la OP la tarea de descifrar).
1 votos
Quieres demostrar que para cualquier máquina de Turing de esta forma puedes construir una DFA que haga lo mismo, y de forma similar para cualquier DFA existe una máquina de Turing de esta forma.
0 votos
@TylerChen ¡¡Gracias por la respuesta!! Me las arreglé para demostrar una parte, en la que cada DFA tiene tal máquina, pero se atascó en la segunda parte. ¿Hay alguna posibilidad de una pista?
0 votos
¿Existen restricciones adicionales en la TM, como que la cabeza sólo se mueva hacia la derecha? Si tuvieras una TM que nunca se detuviera, entonces no veo cómo podrías representar esto como un DFA.
1 votos
@TylerChen: La convención habitual es que una máquina que no se detiene en una entrada particular se considera que rechace eso. Una máquina que nunca se detiene por lo tanto reconoce el lenguaje vacío, para el que es fácil escribir un DFA.