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.
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.
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:
Se otorgan dos puntos extra por esta entrada.
Publicar un comentario