Trabajo 3 - parte 4 (final)

Ahora vamos a resolver el problema propuesto con una maquina de Turing modificada.
Usamos en este caso la MT multicabezal:

En q0 mientras el 1º cabezal no se mueve el 2º cabezal recorre la cadena de 0's hasta que encuentra un 1 momento que termina de colocarse ambos cabezales en sus respectivos grupos de 0's para ser analizados por parejas y se pasa a q₁. Hay un caso particular en q₀ en el que el 2º cabezal se tropieza con el B antes de leer un 1, significa que en la caden a de entrada sólo nos han dado un grupo de 0's y por lo tanto se sonsidera que está en orden creciente ( :P ) terminando con éxito la MT en el estado final q₃.
En q₁ hacemos todo el rato parejas de 0's hacia la derecha hasta que el 1º cabezal lea un 1, momento en el que se pasa a q₂.
En q₂ sólo movemos el 2º cabezal hacia la derecha para que busque la siguiente cadena de 0's y así repetir el proceso del estado q1 para hacer parejas de 0's.
Si en q2 el segundo cabezal lee un B se considera que no hay más cadenas de 0's que comparar y se envia a q3, estado final.
f(q₀,0,0) = (q₀,{0,Z},{0,R})
f(q₀,0,1) = (q₁,{0,Z},{1,R})
f(q₀,0,B) = (q₃,{0,Z},{B,Z})
f(q₁,0,0) = (q₁,{0,R},{0,R})
f(q₁,1,0) = (q₂,{1,R},{0,R})
f(q₂,0,0) = (q₂,{0,Z},{0,R})
f(q₂,0,1) = (q₁,{0,Z},{1,R})
f(q₂,0,B) = (q₃,{0,Z},{B,Z})
q₃ = ESTADO FINAL