Máquina de Turing multicinta

Una máquina de Turing de múltiples cintas 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 intuitivamente parece mucho más poderoso que el modelo de cinta única, pero cualquier máquina de múltiples cintas (sin importar cuántas cintas) puede ser simulada por una máquina de cinta única usando solo cuadráticamente más tiempo de cálculo. ^[2] Por lo tanto, las máquinas de múltiples cintas 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 múltiples cintas.

Definición formal

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

• ${\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 pueden aparecer 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 si finalmente se detiene en un estado de . ${\displaystyle M}$ ${\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, R es desplazamiento a la derecha.

Una máquina de Turing de cintas realiza los cálculos de la siguiente manera: inicialmente, recibe su entrada en las posiciones más a la izquierda de la primera cinta; el resto de la primera cinta, así como las demás cintas, están en blanco (es decir, llenas de símbolos en blanco). Todas las cabezas comienzan en la posición más a la izquierda de las cintas. Una vez que ha comenzado, el cálculo continúa de acuerdo con las reglas descritas por la función de transición. El cálculo continúa hasta que ingresa en los estados de aceptación, momento en el que se detiene. ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}}$ ${\displaystyle n}$ ${\displaystyle M}$

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 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".

Véase también

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

Referencias

1. Sipser, Michael (2005). Introducción a la teoría de la computación . Thomson Course Technology. pág. 148. ISBN 0-534-95097-3.
2. Papadimitriou, Christos (1994). Complejidad computacional . Addison-Wesley. pág. 53. ISBN 0-201-53082-1.
3. Martin, John (2010). Introducción a los lenguajes y la teoría de la computación . McGraw Hill. pp. 243–246. ISBN 978-0071289429.