sábado, 8 de mayo de 2010

Problema -Puntos Extra-

Máquina de Turing

Siendo la representación binaria del número 37; ejecutaremos la Máquina de Turing, siguiendo la función de transición dada.

37: 100101





Bien, iniciemos nuestra máquina...

Vemos que la máquina empieza en un estado S.


Enseguida asigna un 0 al inicio, y avanza un espacio a la derecha.



Al pasar a la siguiente posición, se encuentra un 1, y escribe un 1, y avanza un espacio a la derecha.

Al estar un 0 en las siguientes dos posiciones, en cada una de ellas escribe un cero y avanza un espacio a la derecha.


En la siguiente posición hay un 1, escribe un 1 y avanza un espacio a la derecha.


Ahora vemos un 0, escribe 0, y avanza un espacio a la derecha.


Le sigue un 1, y al igual que las demás posiciones escribe un 1, y avanza un lugar a la derecha.


En este momento se encuentra con un espacio vacío.


Entonces la máquina escribe un cero.

Y avanza un espacio, ahora hacia la izquierda, volviendose en un estado T, y al estar en un 1, escribe 1, y avanza un espacio a la izquierda.


Al encontrar el primer cero escribe un 1, imprime SI, y termina.



Entonces nos queda el siguiente número binario: 01001110

que es el número 78.

1 comentario:

Elisa dijo...

Se otorgan dos puntos extra por esta entrada.