Ejemplo Maquinas de Turing en 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.