Máquina de Turing multitapa

Una máquina de Turing de cintas múltiples es una variante de la máquina de Turing que utiliza varias cintas. Cada cinta tiene su propio cabezal para leer y escribir. Inicialmente, la entrada aparece en la cinta 1, y las demás comienzan en blanco. ^{[ 1 ]}

Este modelo parece intuitivamente mucho más potente que el modelo de cinta única, pero cualquier máquina de múltiples cintas —sin importar cuántas cintas tenga— puede ser simulada por una máquina de una sola cinta usando solo un tiempo de cálculo cuadrático mayor. ^{[ 2 ]} Es decir, cualquier lenguaje que pueda ser decidido en tiempo O( t ( n )) por una TM de múltiples cintas puede ser decidido en O( t ² (n)) por una TM de una sola cinta.

Por lo tanto, las máquinas de cintas múltiples no pueden calcular más funciones que las máquinas de cintas únicas, ^{[ 3 ]} y ninguna de las clases de complejidad robustas (como el tiempo polinomial ) se ve afectada por un cambio entre máquinas de cintas únicas y de cintas múltiples.

A${\displaystyle k}$-La máquina de Turing de cinta se puede definir formalmente como una 7- tupla${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$, siguiendo la notación de una máquina de Turing :

• ${\displaystyle \Gamma }$es un conjunto finito y no vacío de símbolos del alfabeto de cinta ;
• ${\displaystyle b\in \Gamma }$es el símbolo en blanco (el único símbolo que puede aparecer en la cinta infinitamente a menudo en cualquier paso durante el cálculo);
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$es el conjunto de símbolos de entrada , es decir, el conjunto de símbolos que se permite que aparezcan en el contenido inicial de la cinta;
• ${\displaystyle Q}$es un conjunto finito y no vacío de estados ;
• ${\displaystyle q_{0}\in Q}$es el estado inicial ;
• ${\displaystyle F\subseteq Q}$es el conjunto de estados finales o estados de aceptación . Se dice que el contenido inicial de la cinta es aceptado por${\displaystyle M}$si finalmente se detiene en un estado de${\displaystyle F}$.
• ${\displaystyle \delta$ :(Q\setminus F)\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}} es una función parcial llamada función de transición , donde L es desplazamiento a la izquierda y R es desplazamiento a la derecha.

A${\displaystyle k}$-máquina de Turing de cinta${\displaystyle M}$, dónde${\displaystyle k}$es el número de cintas asignadas, se calcula de la siguiente manera.${\displaystyle M}$comienza en su estado inicial${\displaystyle q_{0}}$Esto se define por todas las cintas que tienen un cabezal que comienza en la posición más a la izquierda, junto con una entrada.${\displaystyle w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}}$en el extremo izquierdo${\displaystyle n}$posiciones de la primera cinta, siendo todos los demás símbolos de cada cinta el símbolo en blanco definido por${\displaystyle b}$Un paso para la máquina se realiza evaluando la función de transición. Esto se hace tomando el estado actual.${\displaystyle q_{i}\in Q}$y el conjunto de símbolos alfabéticos sobre los que se encuentran las cabezas, anotado como${\displaystyle \Gamma ^{k}}$La función de transición toma ambos parámetros y produce los tres elementos necesarios para una transición: el nuevo estado${\displaystyle q_{j}\in Q}$eso${\displaystyle M}$Transición a un nuevo conjunto de símbolos del alfabeto${\displaystyle \Gamma ^{k}}$que cada uno de los${\displaystyle k}$Las cabezas escribirán en sus respectivas celdas y un conjunto de instrucciones de turno.${\displaystyle \{L,R\}^{k}}$que indicará a cada una de las cabezas en qué dirección moverse (izquierda o derecha una celda) después de que se escriban los nuevos símbolos. La función de transición itera hasta${\displaystyle M}$entra en un estado final perteneciente al conjunto${\displaystyle F}$, momento en el que se detiene.

Las máquinas de Turing de dos pilas tienen una entrada de solo lectura y dos cintas de almacenamiento. Si un cabezal se mueve hacia la izquierda en cualquiera de las cintas, se imprime un espacio en blanco en esa cinta, pero se puede imprimir un símbolo de una "biblioteca".

• máquina de Turing
• Máquina de Turing universal
• Máquina de Turing alterna
• Máquina de Turing probabilística
• Equivalentes de la máquina de Turing