Puntos extra - Maquina de Turing - Problema 3 del examen de medio curso

En este problema hay que ejecutar paso a paso la máquina Turing definida por la siguiente función de transición:



con la entrada siendo la representación binaria del numero decimal 37

Para resolver este problema primero hay que convertir el numero decimal en bianrio, para convertirlo existen varias maneras, asi que usaré una de las más fáciles:

37/2 = 18, residuo 1
18/2 = 9, residuo 0
9/2 = 4, residuo 1
4/2 = 2, residuo 0
2/2 = 1, residuo 0
1/2 = 0, residuo 1

Nuestro numero binario serían los residuos de todas las divisiones. Nuestro número binario sería: 100101

Empezamos:


por nuestras condiciones se queda el estado s, se pone un 0 y se mueve a la derecha



ahora se queda el estado s, se pone un 1 y se mueve a la derecha



se repite una condición anterior, se queda en s, se pone un 0 y se mueve a la derecha



estado s, se pone un 0, se mueve a la derecha



estado s, se pone un 1, se mueve a la derecha



estado s, se pone un 0, se mueve a la derecha



estado s, se pone un 1, se mueve a la derecha



ahora cambió, ahora es un estado t, se pone un 0 y se mueve a la izquierda



finalmente queda en Si, se pone un 1 y termina.

el numero binario que queda es 01001110
ahora hay que convertir este numero binario en decimal
(0*2^0)+(1*2^1)+(1*2^2)+(1*2^3)+(0*2^4)+(0*2^5)+(1*2^6)+(0*2^7)

= (2^1)+(2^2)+(2^3)+(2^6)

= 2+4+8+64

= 78

Lo que hace esta maquina de turing es multiplicar el numero por 2 y le suma 4.
La complejidad sería O(n).