¿máquina de turing infinita de dos vías?

Question

Una máquina de turing de una sola cinta generalmente no está limitada a la derecha y comienza desde la izquierda. La cabeza de lectura/escritura se mueve a la derecha desde la izquierda después de consumir un símbolo. Pero, ¿qué pasa si hacemos que el lado izquierdo sea también ilimitado y hacemos que el cabezal de lectura/escritura se mueva en ambas direcciones? ¿Aumentará su potencia?

edit : En realidad se ha respondido en cs.stackexchange.com La respuesta es Sí, son iguales en potencia, pueden ser simluados uno por el otro. El enlace es https://cs.stackexchange.com/questions/22863/turing-machine-infinite-tape-in-one-or-two-directions

Answer 1

Para responder a su pregunta:

Esto ya ha sido contestado

"A pesar de la apariencia de ser una herramienta computacional más poderosa las MT multi-cinta son computacionalmente equivalentes a las MT estándar con una cinta".

Enlace a la fuente si quiere comprobar la autenticidad