Puntos Extra

Para el trabajo de puntos extras yo y mi compañero alexandro carrizales elegimos hacer el problema de la maquina turing. El problema era el siguiente:

Maquina Turing (20 Puntos)

Ejecuta paso a paso la Maquina Turing para la siguiente función de transición, con la entrada siendo la representación binaria del número decimal 37 ¿Cuál es la salida de la máquina en decimal? ¿Qué hace la máquina? ¿Qué complejidad asintótica tiene en términos de computación y memoria?


El primer paso es convertir el numero decimal 37 a binario. Una forma muy sencilla es dividiendo el numero 37 entre 2 y quedaria el cociente 18 y residuo 1; y ahora dividir el 18 entre 2 y te da cociente 9 y residuo 0; ahora dividimos el 9 entre 2 y queda cociente 4 y residuo 1; ahora dividimos el 4 entre 2 y queda cociente 2 y residuo 0; ahora dividimos el 2 entre 2 y queda cociente 1 y residuo 0 y por ultimo dividimos el 1 entre 0 y queda cociente 0 y residuo 1. Ahora sigue juntar todos los residuos para formar el numero binario (recuerden que es primero el ultimo residuo y al final el primero).

El numero binario queda asi:

100101

Ahora sigue la ejecucion de la Maquina Turing. Esta era la tabla que venia en el examen:




Y asi seria la ejecucuion de la Maquina:

0 1 0 0 1 0 1 F
1 S
2 S
3 S
4 S
5 S
6 S
7 S
8 S
9 t
10 T
11 ALTO



El resultado que arroja la Maquina Turing es:

01001110


Ahora tenemos que convertirlo a decimal:


0(27) +1( 26)+0(25)+0(24)+1(23)+1(22)+1(21)+0(20)=

0 + 64 + 0 + 0 + 8 + 4 + 2 + 0= 78


La salida de la Maquina Turing es 78.


¿Que hace la Maquina Turing?

La maquina turing lo que hace es mutiplicar el numero inicial por 2 y despues sumarle 4.


¿Cual es la complejidad en terminos de computacion y memoria?

Este problema tiene complejidad polinomial. El peor caso en este ejemplo hubiera sido que el numero inicial hubieran sido puros 1 y un o al principio, ya que en este caso tendria que recorrer toda la cinta

Cualquier sugerencia o aclaraciones solo pongan los comentarios.

Gracias