Lo primero que hay que hacer es convertir el 37 en numero binario.
Mi metodo es este:
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
Entonces tomando el divisor de la ultima division y tomando los residuos de abajo hacia arriba queda:
100101
ejecutamos la maquina turing
s
> 1 0 0 1 0 1
1- s > s, 0, -->
s
0 1 0 0 1 0 1
Cambia el inicio por un cero y avanza un espacio hacia la derecha
2- s 1 s, 1, -->
s
0 1 0 0 1 0 1
Estado "s" ,se queda el 1 y avanza a la derecha
3- s 0 s, 0,-->
s
0 1 0 0 1 0 1
Sigue estado "s", se queda el 0 y avanza un espacio a la derecha
4- s 0 s,0,-->
s
0 1 0 0 1 0 1
Sigue estado "s", se queda el cero y avanza un espacio a la derecha
5- s 1 s,1,-->
s
0 1 0 0 1 0 1
Sigue estado "s", se queda el 1 y avanza a la derecha
6- s 0 s,0,-->
s
0 1 0 0 1 0 1
Sigue estado "s", se queda el 0 y avanza hacia la derecha
7- s 1 s,1,-->
s
0 1 0 0 1 0 1
Sigue estado "s", se queda el 1 y avanza hacia la derecha y llega a un espacio vacio
8- s [_] t, 0 <--
t
0 1 0 0 1 0 1 0
Como estaba en estado "s" en una parte vacia, cambia de estado, ahora es "t", se agrega un 0 y se regresa a la izquierda un espacio.
9- t 1 t,1,<--
t
0 1 0 0 1 0 1 0
Cambia el estado "s" a "t", deja el 1 y avanza a la izquierda un espacio
10- t 0 Si, 1,--
Si
0 1 0 0 1 1 1 0
Cambia del estado "t" a "Si", cambia el 0 por el 1 y ahi se detiene
La salida de la maquina en decimal es:
1 0 0 1 1 1 0
2^6 2^5 2^4 2^3 2^2 2^1 2^0
64 0 0 8 4 2 0
64+8+4+2= 78
Que hace la maquina: pues multiplica el numero por 2 y le suma 4.
La complejidad: O(n) porque tardas segun el numero de transiciones que tienes que hacer.
Nombre: Juan Manuel Casanova Villarreal
Matricula: 1453829
1 comentario:
Muy bien explicada la ejecucion de la maquina de turing, una duda no deberia ser 00101 no entendi muy bien lo de tomar el divisor de la ultima division saludos
Publicar un comentario