TRES EJEMPLOS DE MAQUINAS DE TURING

EJEMPLO 1: DISEÑAR UNA MAQUINA DE TURING QUE ACEPTE EL LENGUAJE

L={0n1n :n>0}

Lo primero que haremos es limitar el alfabeto a

$$\Sigma =\{0,1\}$$

así nos aseguramos de que sólo puede aceptar palabras con de entrada con símbolos 1 y 0.
Los símbolos de cinta serán

$$T=\{0,1,B,X,Y\}$$

siendo B el símbolo en blanco.
La MT consta de cinco estados:

$$q_0,q_1,q_2,q_3,q_4$$

Los estados q₀ y q₄ son el inicial y el final, respectivamente.
Inicialmente, la cabeza señala el primer 0. Lo cambia por X y se desplaza a la derecha en busca del primer 1 para cambiarlo por Y:

$$\delta (q_0,0)=(q_1,X,R)$$

$$\delta (q_1,0)=(q_1,0,R)$$

Es decir, mientras haya 0's, se mantiene en el estado q₁ .

$$\delta (q_1,1)=(q_2,Y,L)$$

Ha encontrado el primer 1. Lo cambia por Y y pasa al estado q₂ moviéndose a la izquierda. En este estado, la MT se mueve hacia la izquierda en busca de X saltando las casillas con 0's:

$$\delta (q_2,0)=(q_2,0,L)$$

Cuando encuentra la X, se mueve hacia la derecha esperando encontrar un 0 para cambiarlo por X, por lo que pasa al estado q₀ :

$$\delta (q_2,X)=(q_0,X,R)$$

Una vez cambiado dicho 0 por X, está en el estado q₁ . Ahora tiene que buscar el siguiente 1 y cambiarlo por Y, pero se encuentra con Y antes de llegar, por lo que tiene que saltar esta casilla:

$$\delta (q_1,Y)=(q_3,Y,R)$$

En el estado q₃ sigue saltando las casillas con Y hasta llegar al 1:

$$\delta (q_3,Y)=(q_3,Y,R)$$

$$\delta (q_3,1)=(q_2,Y,L)$$

Pasa al estado q₂ una vez ha cambiado el 1 por la Y. En este estado, la MT se mueve a la izquierda hasta encontrar una X. Una vez la encuentra, se mueve una casilla a la derecha. Si hay un 0, tendrá que empezar el proceso anterior (buscar 1, cambiarlo por Y y volver a buscar la X, con lo que estaremos de nuevo en este punto). Si ya no quedan 0's, habrá una Y y, por tanto, se han cambiado n 0's por n X 's y n 1's por n Y 's. Entonces se mueve a la izquierda:

$$\delta (q_2,Y)=(q_2,Y,L)$$

Se encuentra con una X y pasa al estado q₀. En este estado se busca un 0 para cambiarlo por X, pero suponemos que ya no quedan. Entonces la cabeza debe moverse a la derecha para comprobar que tampoco quedan más 1's:

$$\delta (q_0,Y)=(q_0,Y,R)$$

Cuando encuentra el primer símbolo en blanco, la MT finaliza:

$$\delta (q_0,B)=(q_4,B,R)$$

En el caso de que haya más 0's que 1's, llegará un momento en el que ya no queden 1's (los habrá cambiado por Y ). La MT se quedará permanentemente en el estado q₁ .
El diagrama de la MT es

Vamos a simular la MT para una sola entrada que todas tienen la misma forma. Mostraremos el estado final de la cinta y la posición de la cabeza (sombreado en color rosa).
Entrada: 000111; Resultado esperado: XXXYYY.

• EJEMPLO 2: DISEÑAR UNA MAQUINA DE TURING QUE CALCULA EL NUMERO CONSECUTIVO DE UN NUMERO DADO EN BINARIO

Si el número es par, su último bit es 0. La máquina sólo tiene que cambiar este 0 por un 1.
Si el número es impar, su último bit es 1. En este caso, se tiene que cambiar por 0’s todos los 1’s seguidos que haya escritos de derecha a izquierda hasta llegar al primer 0, que se cambia por un 1. Si no hay ningún 0, entonces se tiene que añadir un 1 delante del número (añadir un bit). Es decir, escribir un 1 en la casilla en blanco (B) a la izquierda del número.
Vamos a considerar tres estados:

$$q_0,q_1,q_2$$

• Inicialmente, la MT está en el estado q₀ con la cabeza señalando la primera cifra del número.
  La MT recorre todo el número para ver si es par o impar sin modificar su cinta.
  
  $$\delta (q_0,0)=(q_0,0,R)$$
  $$\delta (q_0,1)=(q_0,1,R)$$
• Notemos que, por ahora, la MT se detiene al llegar al primer símbolo en blanco a la derecha del número.
  La MT vuelve a la anterior casilla (último número). Si es un 0, lo cambia por un 1 y pasa al estado final que es q₂ . Para hacer esto usaremos el estado q₁ :
  
  $$\delta (q_0,B)=(q_1,B,L)$$
  $$\delta (q_1,0)=(q_2,1,R)$$
• Si el número es impar, la MT no ha cambiado el último número, pero está en el estado q₁ . Tiene que cambiar todos los 1's consecutivos que haya de derecha a izquierda.
  
  $$\delta (q_1,1)=(q_1,0,L)$$
• Por ahora, la MT se para cuando llega al primer 0 (de derecha a izquierda) ó en un símbolo en blanco. Si es un 0, lo cambia por un 1 y el proceso finaliza:
  
  $$\delta (q_1,0)=(q_2,1,L)$$
  (Hemos escrito un desplazamiento a la izquierda, pero esto no tiene importancia ya que la MT ha llegado al estado final).
• Si lo que señala la cabeza es un blanco en vez de un 1, tiene que cambiarlo por un 1 y finalizar el proceso.
  
  $$\delta (q_1,B)=(q_2,1,L)$$

El diagrama de la máquina es

Donde el cuadro representa el símbolo en blanco B.
Vamos a simular la MT para varias entradas. Mostraremos el estado final de la cinta y la posición de la cabeza (sombreado en color rosa).
Entrada: 000; Resultado esperado: 001.

Entrada: 0011; Resultado esperado: 0100.

Entrada: 111; Resultado esperado: 1000.

Entrada: 1; Resultado esperado: 10.

• EJEMPLO 3: DISEÑAR UNA MAQUINA DE TURING QUE, DADA UNA PALABRA W DEL ALFABETO Σ={0, 1}, PROPORCIONA SU REVERSO, w_R .

Lo que tiene que hacer la MT es cambiar el orden de los símbolos que hay en su cinta.

Usaremos los símbolos de cinta adicionales A y Z para indicar el comienzo y el final de la palabra w en la cinta.
En el estado q₀ , la MT busca el comienzo de palabra, es decir, el primer símbolo en blanco a la izquierda. Cuando lo encuentra, lo cambia por A:

$$\delta (q_0,0)=(q_0,0,L)$$

$$\delta (q_0,1)=(q_0,1,L)$$

En el estado q₁ la MT se desplaza hacia la derecha hasta encontrar el primer símbolo en blanco para cambiarlo por Z:

$$\delta (q_1,0)=(q_1,0,R)$$

$$\delta (q_1,1)=(q_1,1,R)$$

$$\delta (q_1,B)=(q_2,Z,L)$$

Luego pasa al estado q₂ . En este estado, cambia el primer elemento de la palabra w (o sea, el último) por B para escribirlo al lado derecho de Z.
Como usaremos este estado posteriormente, puede ocurrir que ya no queden símbolos de wporque ya se ha copiado. En este caso sólo quedarán símbolos en blanco y el símbolo A que marca el comienzo de w:

$$\delta (q_2,B)=(q_2,B,L)$$

$$\delta (q_2,A)=(q_8,B,L)$$

$$\delta (q_2,1)=(q_3,B,R)$$

$$\delta (q_2,0)=(q_6,B,R)$$

En el caso de que ya no haya símbolos de w, la MT borra A y vuelve pasa al estado q₈ en el que buscará la Z para borrarla de la cinta, pasando al estado final q₉ :

$$\delta (q_8,B)=(q_8,B,R)$$

$$\delta (q_8,Z)=(q_9,B,R)$$

Volviendo al punto anterior, si en q₂ se encuentra con el símbolo 1, entonces lo borra y entra en los estados q₃ y q₄ cuya finalidad son escribir el 1 en su sitio correspondiente a la derecha de Z:

$$\delta (q_3,B)=(q_3,B,R)$$

$$\delta (q_3,Z)=(q_4,Z,R)$$

$$\delta (q_4,B)=(q_5,1,R)$$

$$\delta (q_4,0)=(q_4,0,R)$$

$$\delta (q_4,1)=(q_4,1,R)$$

En el estado q₅ la MT busca de nuevo el símbolo Z para pasar de nuevo al estado q₂ :

$$\delta (q_5,0)=(q_5,0,L)$$

$$\delta (q_5,1)=(q_5,1,L)$$

$$\delta (q_5,Z)=(q_2,Z,L)$$

El otro caso es que en q₂ se encuentre con el símbolo 0. La MT procede de forma análoga a los estados q₃ y q₄ pero escribiendo 0 en vez de 1. Para ello usaremos los estados q₆ y q₇:

$$\delta (q_6,B)=(q_6,B,R)$$

$$\delta (q_6,Z)=(q_7,Z,R)$$

$$\delta (q_7,B)=(q_5,0,L)$$

$$\delta (q_7,0)=(q_7,0,R)$$

$$\delta (q_7,1)=(q_7,1,R)$$

Finalmente, en la cinta sólo quedará la palabra w^R, es decir, la palabra w escrita de derecha a izquierda.
El diagrama de la máquina de Turing es