Una máquina de Turing multicinta, también denominada 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 lectura y escritura. Inicialmente, la entrada aparece en la cinta 1, y las demás comienzan en blanco.

Este modelo parece intuitivamente mucho más potente que el modelo de una sola cinta, pero cualquier máquina de cintas múltiples (sin importar cuántas cintas tenga) puede ser simulada por una máquina de una sola cinta utilizando solo más tiempo de cálculo, que se incrementa cuadráticamente. Es decir, cualquier lenguaje que pueda ser decidido en tiempo por una máquina de Turing de cintas múltiples puede ser decidido en por una máquina 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 una sola cinta, y ninguna de las clases robustas de complejidad (como la de tiempo polinómico) se ve afectada por un cambio entre máquinas de una sola cinta y de cintas múltiples.

Definición formal Una máquina de Turing de cintas se puede definir formalmente como una 7-tupla , siguiendo la notación de una máquina de Turing:

es un conjunto finito y no vacío de símbolos del alfabeto de la cinta; 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); es el conjunto de símbolos de entrada, es decir, el conjunto de símbolos que pueden aparecer en el contenido inicial de la cinta; es un conjunto finito y no vacío de estados; es el estado inicial; es el conjunto de estados finales o estados de aceptación. Se dice que el contenido inicial de la cinta es aceptado por si finalmente se detiene en un estado de . es una función parcial llamada función de transición, donde L representa el desplazamiento a la izquierda y R el desplazamiento a la derecha.

Una máquina de Turing de cintas, , donde es el número de cintas asignadas, realiza los cálculos de la siguiente manera: comienza en su estado inicial . Este estado se define por el hecho de que todas las cintas tienen un cabezal que comienza en la posición más a la izquierda, junto con una entrada en las posiciones más a la izquierda de de la primera cinta. Todos los demás símbolos de cada cinta son el símbolo en blanco definido por . Un paso de la máquina se realiza evaluando la función de transición. Esto se logra tomando el estado actual y el conjunto de símbolos alfabéticos sobre los que se encuentran los cabezales, denotado como . La función de transición toma ambos parámetros y genera los tres elementos necesarios para una transición: el nuevo estado al que transita , un nuevo conjunto de símbolos alfabéticos que cada uno de los cabezales escribirá en sus respectivas celdas, y un conjunto de instrucciones de desplazamiento que indicarán a cada cabezal en qué dirección moverse (una celda a la izquierda o a la derecha) después de escribir los nuevos símbolos. La función de transición itera hasta que alcanza un estado final perteneciente al conjunto , momento en el que se detiene.

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

Véase también Máquina de Turing Máquina de Turing universal Máquina de Turing alternante Máquina de Turing probabilística Equivalentes de la máquina de Turing

Referencias

Categoría:Máquinas de Turing