10. Funcionamiento de la MT Multicinta

Tal como se describió en la sección anterior sobre la clasificación de las MT, una máquina multicintas posee n cintas diferentes, y n cabezas de L/E. La función de transición para máquinas de Turing con n cintas es:


δ:QxΓ^n→QxΓ^n x〖{D,I,N}〗^n

Para entender su funcionamiento, se presentan dos ejemplos a continuación:




Ejemplo 1

Reconocimiento del lenguaje {anbn
n³ 1}. Éste es bastante laborioso en una máquina de Turing con una única cinta. Es mucho más fácil realizarlo con una máquina de Turing de dos cintas. Suponiendo que, inicialmente, coloca la cadena a analizar en la cinta 1 y que q1 es el estado inicial. Si la cabeza de lectura/escritura de la cinta 1 está situada inicialmente sobre el carácter del extremo izquierdo de la cadena, las cuatro posiciones siguientes son fundamentales para el reconocimiento (cualquier otra transición sería para cadenas mal formadas y se puede suponer que llega a un estado que no es de aceptación):

d (q1, (a, B)) =(q1, (a, a), (R, R))

d (q1, (b, B)) =( q2, (b, B), (S, L))

d ( q2, (b, a)) =( q2, (b, a), (R, L))

d ( q2, (B, B)) =( q3, (B, B), (R, L))

Aunque esta máquina de Turing multicinta parece bastante distinta y posiblemente más potente que la máquina de Turing definida originalmente, las dos son equivalentes en el sentido de que cada una de ellas puede ser simulada por la otra.



Ejemplo 2

Sea una MT de dos cintas, que reconoce el lenguaje L={a^i b^i c^i:i≥0}

Se coloca la cadena de entrada en la primera cinta, la idea es copiar en la segunda cinta una X por cada “a” y cuando encuentre la primera “b”, se detiene en la primera cinta, luego se avanza a la derecha en la primera cinta y se avanza a la izquierda en la segunda cinta, cuando encuentra la primera “c” las dos cintas avanzan hacia la derecha.

La función de transición es la siguiente, sea T = {q3}.

δ(q0, (a,B)) = (q0, (a,X), (D,D))

δ(q0, (b,B)) = (q1, (b,B), (N,D))

δ(q1, (b,B)) = (q1, (b,X), (D, I))

δ(q1, (c,B)) = (q2, (c,B), (N,D))

δ(q2, (c,X)) = (q2, (c,X), (D,D))

δ(q2, (B,B)) = (q3, (B,B), (D,D))

Se muestra el funcionamiento de la MT multicinta, con la cadena de entrada w = abc.

Se finaliza en el estado q3, definido como estado de aceptación.