Ejemplo

 

Diseñar una máquina de Turing que acepta el lenguaje L={0n1n :n>0}

Lo primero que haremos es limitar el alfabeto a

Σ={0,1}Σ={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}T={0,1,B,X,Y}

siendo B el símbolo en blanco.

La MT consta de cinco estados:

q0,q1,q2,q3,q4q0,q1,q2,q3,q4

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:

δ(q0,0)=(q1,X,R)δ(q0,0)=(q1,X,R)

δ(q1,0)=(q1,0,R)δ(q1,0)=(q1,0,R)

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

δ(q1,1)=(q2,Y,L)δ(q1,1)=(q2,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:

δ(q2,0)=(q2,0,L)δ(q2,0)=(q2,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₀ :

δ(q2,X)=(q0,X,R)δ(q2,X)=(q0,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:

δ(q1,Y)=(q3,Y,R)δ(q1,Y)=(q3,Y,R)

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

δ(q3,Y)=(q3,Y,R)δ(q3,Y)=(q3,Y,R)

δ(q3,1)=(q2,Y,L)δ(q3,1)=(q2,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:

δ(q2,Y)=(q2,Y,L)δ(q2,Y)=(q2,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:

δ(q0,Y)=(q0,Y,R)δ(q0,Y)=(q0,Y,R)

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

δ(q0,B)=(q4,B,R)δ(q0,B)=(q4,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.