He visto máquinas turing representadas con cintas infinitas en una y en dos direcciones. ¿Hay alguna diferencia en el poder de tales máquinas de turing, o son básicamente equivalentes? En mi cabeza, creo que son equivalentes, ya que supongo que debe haber alguna forma de representar la cinta infinita bidireccional como una cinta infinita unidireccional, pero parece que no puedo encontrar una prueba o ejemplo.
turing-machines
usuario2795095
fuente
fuente
Respuestas:
Son equivalentes en potencia computacional. Cualquier cosa computable por uno de estos dos tipos de máquinas de Turing, es computable por el otro tipo. Veamos cómo simular una máquina Turing con una cinta doblemente infinita, en una máquina Turing con una cinta individualmente infinita.
La idea es cortar tu cinta doblemente infinita en dos, para que tengas dos cintas infinitas, una a la izquierda y otra a la derecha, que finalmente combinarás. Puede marcar los extremos con una ubicación de cinta que contenga un símbolo EOF especial. También duplica su control finito, de modo que tiene dos controles de estado finito idénticos. Asume que tiene un dispositivo de control de paso (ver abajo), de modo que, cuando la máquina izquierda intenta ir más allá del extremo derecho de su cinta, pasa el control a la máquina derecha, en su posición de cinta más a la izquierda (justo antes de extremo izquierdo de la cinta derecha). Y a la inversa, al intentar pasar el extremo izquierdo de la cinta derecha.
Ahora estamos listos para fusionar las dos medias cintas, por ejemplo doblando la derecha sobre la izquierda. Para eso, voltea la media cinta derecha y tiene cuidado de modificar en consecuencia las transiciones, intercambiando derecha por izquierda e izquierda por derecha. Luego fusiona las dos medias cintas en una sola cinta que contiene pares de símbolos, uno izquierdo y uno derecho, cada componente posiblemente en blanco.
Modifica nuevamente las transiciones de ambas máquinas, de modo que las transiciones a la izquierda (respectivamente a la derecha) usan y modifican solo las partes a la izquierda (respectivamente a la derecha) de los pares en la cinta. Luego, combina el control de las dos máquinas mediante una simple unión de conjuntos respectivamente para los estados y las transiciones.
Agregue un conjunto de transiciones para cada estado existente, de modo que cuando el símbolo de la cinta sea EOF, regrese a la ubicación de la cinta anterior (la primera ubicación no EOF) y el estado cambie a su contraparte quiral: si es un izquierdo (resp. derecha), cambia a su contraparte derecha (resp. izquierda). Ese es el dispositivo de control de paso.
Puede que haya olvidado un detalle, pero esta es la idea general de la construcción. La prueba se deja como un ejercicio.
Por supuesto, la cinta inicial (entrada) debe modificarse en consecuencia. Pero eso puede simplificarse colocando la entrada (si es finita) completamente en el lado izquierdo (el que no se voltea) del corte de cinta.
Luego guardas el destornillador, ya que puede ser peligroso para los niños.
PD: Solo mostré que la cinta doblemente infinita se puede simular con una cinta individualmente infinita. Lo contrario parece demasiado obvio.
fuente