Máquina de Turing multipista

Una máquina de Turing multipista es un tipo específico de máquina de Turing multicinta .

En una máquina de Turing estándar de n cintas, n cabezales se mueven independientemente a lo largo de n pistas. En una máquina de Turing de n pistas, un cabezal lee y escribe en todas las pistas simultáneamente. Una posición de cinta en una máquina de Turing de n pistas contiene n símbolos del alfabeto de la cinta. Es equivalente a la máquina de Turing estándar y, por lo tanto, acepta precisamente los lenguajes recursivamente enumerables .

Una máquina de Turing multipista con${\displaystyle n}$-las cintas se pueden definir formalmente como una 6-tupla${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$, dónde

• ${\displaystyle Q}$es un conjunto finito de estados;
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$es un conjunto finito de símbolos de entrada , es decir, el conjunto de símbolos que pueden aparecer en el contenido inicial de la cinta;
• ${\displaystyle \Gamma }$es un conjunto finito de símbolos del alfabeto de cinta ;
• ${\displaystyle q_{0}\in Q}$es el estado inicial ;
• ${\displaystyle F\subseteq Q}$es el conjunto de estados finales o de aceptación ;
• ${\displaystyle \delta$ :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)} es una función parcial llamada función de transición .

A veces también se denota como${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}$, dónde${\displaystyle d\in \{L,R\}}$.

Se puede definir una variante no determinista reemplazando la función de transición.${\displaystyle \delta }$mediante una relación de transición${\displaystyle \delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}$.

Esto demostrará que una máquina de Turing de dos pistas es equivalente a una máquina de Turing estándar. Esto se puede generalizar a una máquina de Turing de n pistas. Sea L un lenguaje recursivamente enumerable. Sea${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$Sea M una máquina de Turing estándar que acepta L. Sea M' una máquina de Turing de dos pistas. Para demostrar que${\displaystyle M=M'}$Debe demostrarse que${\displaystyle M\subseteq M'}$y${\displaystyle M'\subseteq M}$.

• ${\displaystyle M\subseteq M'}$

Si se ignora la segunda pista, entonces M y M' son claramente equivalentes.

• ${\displaystyle M'\subseteq M}$

El alfabeto de cinta de una máquina de Turing de una pista equivalente a una máquina de Turing de dos pistas consta de un par ordenado . El símbolo de entrada a de una máquina de Turing M' puede identificarse como un par ordenado .${\displaystyle [x,y]}$de la máquina de Turing M. La máquina de Turing de una sola pista es:

${\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$con la función de transición${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}$

Esta máquina también acepta L.

• Thomas A. Sudkamp (2006). Lenguajes y máquinas, tercera edición. Addison-Wesley. ISBN 0-321-32221-5Capítulo 8.6: Máquinas de cintas múltiples: págs. 269–271