10. Describa el funcionamiento de la máquina de Turing Multicintas.

Una máquina de Turing multicinta es como una máquina ordinaria con muchas cintas. Cada cinta tiene su propia cabeza de la cinta. Inicialmente la cadena de entrada se encuentra en la cinta 1 y las otras cintas están en blanco. La función de transición se modifica para permitir la lectura, escritura y movimiento de todas las cintas simultáneamente. Formalmente, se define como

δ: Q x Γk → Q x Γk x { L, R }k,

Donde k es el número de cintas. La expresión δ(qi, a1, …, ak) = (qj, b1, …, bk, L, R, …, L) significa que, si la máquina se encuentra en el estado qi y las cabezas 1 a la k están leyendo los símbolos a1 hasta ak, la máquina va al estado qj, escribe los símbolos b1 hasta bk y mueve cada cabeza a la izquierda o derecha según se especifica.

Pareciera que las máquinas de Turing multicinta son más poderosas que las máquinas de Turing ordinarias, pero podemos mostrar que son equivalentes. Recordemos que dos máquinas son equivalentes si reconocen el mismo lenguaje.

Teorema de equivalencia entre máquinas de Turing ordinarias y máquinas de Turing multicinta.

Cada máquina de Turing multicinta tiene una máquina de Turing ordinaria equivalente.

Demostración

Mostramos como convertir una MT multicinta M a una MT S con una sola cinta. La idea principal es mostrar como simular M con S.

Digamos que M tiene k cintas. Entonces S simula el efecto de k cintas almacenando la información de las cintas en su cinta sencilla. S utiliza el símbolo # para delimitar el contenido de las cintas. Además del contenido de cada cinta, S debe almacenar la posición de las cabezas. Esto se hace marcando el símbolo donde está colocada la cabeza en cada cinta. En la figura se ilustra cómo puede usarse una cinta para representar tres cintas.

  S = “Sobre la cadena de entrada w = w1 … wn

1. S coloca su cinta en el formato que representa las k cintas de M. La cinta con el formato contiene

# w1 w2 … wn # Џ # Џ # … #

2. Para simular un movimiento, S barre su cinta desde el primero hasta el último símbolo # para determinar los símbolos bajo las cabezas virtuales. Después S hace un segundo barrido para actualizar las cintas de acuerdo a como dicta la función de transición de M.

3. Si en algún punto S mueve una de las cabezas virtuales a la derecha sobre un símbolo #, esta acción significa que M ha movido la cabeza correspondiente sobre la porción de cinta aún no leída (con símbolos blancos). De tal forma que S escribe un símbolo blanco en su cinta y recorre una posición todos los símbolos desde ahí hasta el símbolo # más a la derecha. Después continua la simulación como antes.”