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 poderoso que el modelo de cinta única, pero cualquier máquina de cintas múltiples, sin importar cuántas cintas, puede ser simulada por una máquina de cinta única utilizando sólo cuadráticamente más tiempo de cálculo. [2] Por lo tanto, las máquinas de cintas múltiples no pueden calcular más funciones que las máquinas de cinta única, [3] y ninguna de las clases de complejidad robusta (como el tiempo polinomial ) se ve afectada por un cambio entre máquinas de cinta única y de cinta múltiple. .
Definicion formal
Una máquina de Turing de cinta k puede describirse como una tupla de 6 dónde:
- es un conjunto finito de estados
- es un conjunto finito del alfabeto de cintas
- es el estado inicial
- es el símbolo en blanco
- es el conjunto de estados finales o de aceptación
- es una función parcial llamada función de transición, donde k es el número de cintas, L es desplazamiento a la izquierda, R es desplazamiento a la derecha y S es sin desplazamiento.
Máquina de Turing de dos pilas
Las máquinas Turing de dos pilas tienen una entrada de solo lectura y dos cintas de almacenamiento. Si una cabeza 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".
Ver también
Referencias
- ^ Sipser, Michael (2005). Introducción a la Teoría de la Computación . Tecnología del curso Thomson. pag. 148. ISBN 0-534-95097-3.
- ^ Papadimitriou, Christos (1994). Complejidad computacional . Addison-Wesley. pag. 53 . ISBN 0-201-53082-1.
- ^ Martín, John (2010). Introducción a los lenguajes y la teoría de la computación . McGraw Hill. págs. 243–246. ISBN 978-0071289429.