Máquina de Turing en TOC

La máquina de Turing fue inventada por Alan Turing en 1936 y se utiliza para aceptar lenguajes enumerables recursivos (generados por gramática de tipo 0). 

Una máquina de turing consta de una cinta de longitud infinita en la que se pueden realizar operaciones de lectura y escritura. La cinta consta de celdas infinitas en las que cada celda contiene un símbolo de entrada o un símbolo especial llamado espacio en blanco. También consta de un puntero de cabeza que apunta a la celda que se está leyendo actualmente y puede moverse en ambas direcciones.

Una TM se expresa como una tupla de 7 (Q, T, B, ∑, δ, q0, F) donde: 
 

• Q  es un conjunto finito de estados
• T  es el alfabeto de la cinta (símbolos que se pueden escribir en la cinta)
• B  es un símbolo en blanco (todas las celdas se llenan con B excepto el alfabeto de entrada inicialmente)
• ∑  es el alfabeto de entrada (símbolos que forman parte del alfabeto de entrada)
• δ es una función de transición que mapea Q × T → Q × T × {L,R}. Dependiendo de su estado actual y del alfabeto de la cinta actual (señalado por el puntero de la cabeza), se moverá al nuevo estado, cambiará el símbolo de la cinta (puede o no) y moverá el puntero de la cabeza hacia la izquierda o hacia la derecha.
• q0  es el estado inicial
• F  es el conjunto de estados finales. Si se alcanza cualquier estado de F, se acepta la string de entrada.

Construyamos una máquina de turing para L={0^n1^n|n>=1} 
 

• Q = {q0,q1,q2,q3} donde q0 es el estado inicial.
• T = {0,1,X,Y,B} donde B representa un espacio en blanco.
• ∑ = {0,1}
• F = {q3}

La función de transición δ se da en la Tabla 1 como: 

Ilustración

Veamos cómo funciona esta máquina de Turing para 0011. Inicialmente, la cabeza apunta a 0, que está subrayado y el estado es q0 como: 

El movimiento será δ(q0, 0) = (q1, X, R). Significa que irá al estado q1, reemplazará 0 por X y la cabeza se moverá a la derecha como: 

El movimiento será δ(q1, 0) = (q1, 0, R) lo que significa que permanecerá en el mismo estado y sin cambiar ningún símbolo, se moverá a la derecha como: 

El movimiento será δ(q1, 1) = (q2, Y, L) lo que significa que se moverá al estado q2 y cambiando 1 a Y, se moverá a la izquierda como: 

Trabajando en él de la misma manera, la máquina llegará al estado q3 y el cabezal apuntará a B como se muestra: 

Usando move δ(q3, B) = detener, se detendrá y aceptará. 

Nota: 
 

• En la máquina de turing no determinista, puede haber más de un movimiento posible para un estado y símbolo de cinta dados, pero la TM no determinista no agrega ninguna potencia.
• Cada TM no determinista se puede convertir en TM determinista.
• En la máquina de turing de múltiples cintas, puede haber más de una cinta y los punteros de cabeza correspondientes, pero no agrega energía a la máquina de turing.
• Cada TM multicinta se puede convertir en una TM de una sola cinta.

Pregunta: Una máquina de Turing M de una sola cinta tiene dos estados q0 y q1, de los cuales q0 es el estado inicial. El alfabeto de cinta de M es {0, 1, B} y su alfabeto de entrada es {0, 1}. El símbolo B es el símbolo en blanco que se usa para indicar el final de una string de entrada. La función de transición de M se describe en la siguiente tabla. 

La tabla se interpreta como se ilustra a continuación. La entrada (q1, 1, R) en la fila q0 y la columna 1 significa que si M está en el estado q0 y lee 1 en el cuadro de cinta actual, entonces escribe 1 en el mismo cuadro de cinta, mueve su cabezal de cinta una posición hacia el derecha y transiciones al estado q1. ¿Cuál de las siguientes afirmaciones es verdadera acerca de M? 
 

1. M no se detiene en ninguna string en (0 + 1)+
2. M no se detiene en ninguna string en (00 + 1)*
3. M se detiene en todas las strings que terminan en 0
4. M se detiene en todas las strings que terminan en 1

Solución: Veamos si la máquina se detiene en la string ‘1’. Inicialmente, el estado será q0, la cabeza apuntará a 1 como: 

Usando δ(q0, 1) = (q1, 1, R), se moverá al estado q1 y la cabeza se moverá a la derecha como: 

Usando δ(q1, B) = (q0, B, L), se moverá al estado q0 y la cabeza se moverá a la izquierda como: 

Se ejecutará de la misma manera una y otra vez y no se detendrá. 

La opción D dice que M se detiene en todas las strings que terminan en 1, pero no se detiene en 1. Por lo tanto, la opción D es incorrecta. 

Veamos si la máquina se detiene en la string ‘0’. Inicialmente, el estado será q0, la cabeza apuntará a 1 como: 

Usando δ(q0, 0) = (q1, 1, R), se moverá al estado q1 y la cabeza se moverá a la derecha como: 

Usando δ(q1,B)=(q0,B,L), se moverá al estado q0 y la cabeza se moverá a la izquierda como: 

Se ejecutará de la misma manera una y otra vez y no se detendrá. 

La opción C dice que M se detiene en todas las strings que terminan en 0, pero no se detiene en 0. Por lo tanto, la opción C es incorrecta. 

La opción B dice que TM no se detiene para ninguna string (00 + 1)*. Pero la string NULL es parte de (00 + 1)* y TM se detendrá para la string NULL. Para la string NULL, la cinta será, 

Usando δ(q0, B) = alto, TM se detendrá. Como TM se detiene por NULL, esta opción también es incorrecta. 
Entonces, la opción (A) es correcta. 

Este artículo es una contribución de Sonal Tuteja . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.