Trabajo 3 - Parte 2

Ahora vamos a resolver el problema propuesto con una maquina de Turing modificada. Inicialmente se nos habia ocurrido de 2 maneras:

- Utilizar una máquina multicabezal con 2 cabezales, uno para recorrer la cadena y otro para guardar el resustado.
- En caso de la multicinta, usariamos 2 cintas. Hemos observado que con la primera cinta recorremos la cadena de entrada y con la otra cinta se escribe el resultado.

Finalmente hemos escogido la multicabezal porque es ligeramente más eficiente (para nosotros :P ) a la hora de escribir las transiciones.

Poscionamiento inicial de los cabezales

...B00001001001000100BB...
Rojo= Posicion inical del cabezal 1
Azul= Posición inicial del cabezal 2

Procedimiento: Utilizaremos el estado q₀ para desplazar el cabezal 2 a la derecha hasta que encuentre un blanco, momento que mueve a la derecha el cabezal 2 situandose en el segundo blanco de la derecha y cambia al estado q₁. En estado q₁, cada vez que leamos en los cabezales (0,B) marcamos en el primer cabezal un blanco y los desplazamos a la derecha y no modificamos el cabezal 2 ni lo desplazamos. En el estado q₁, cuando encontramos (1,B) marcamos con el cabezal 1 un blanco y desplazamos a la derecha y con el cabezal 2 escribimos un 0 y lo desplazamos a la derecha. Seguiremos en el estado q₁ hasta que encontremos (B,B) no haremos nada con el cabezal 1 y en cabezal marcamos un 0 y terminamos en el estado final q₂.

ENTRADA: ...B0001001001000100B...
SALIDA: ...B00000B...

Las transiciones del MT multicabezal son:

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,R})
f(q₁,0,B) = (q₁,{B,R},{B,Z})
f(q₁,1,B) = (q₁,{B,R},{0,R})
f(q₁,B,B) = (q₂,{B,Z},{0,R})
f(q₂,B,B) = ESTADO FINAL