Puntos Extras

Problema # 3 Máquina Turing

Instrucciones

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?

Conversión a número binario

Existen muchos métodos para convertir un número decimal a un número binario uno de ellos es el siguiente:

Primero se observa si el numero decimal es impar o es par si es impar se le resta 1 y se escribe un 1 y se divide entre 2; si es par solamente dividimos entre 2 y escribimos un 0 (el resultado de las divisiones se escriben de arriba hacia abajo).

37 = 1 (como es un número impar se escribe un 1 y después le restamos 1 y lo

dividimos entre 2)

18 = 0 (18 es un numero par así que escribimos un cero y dividimos entre dos)

9 = 1

4 = 0

2 = 0

1 = 1

El número en binario es (al escribir el número se debe de empezar desde el último número obtenido): 100101b

Ejecución de la Maquina Turing

Utilizando la siguiente tabla y el número en binario realizar las transiciones de la Maquina Turing:

En decimal el número 01001110b es:

2⁷(0) + 2⁶(1) + 2⁵(0)+ 2⁴ (0)+ 2³ (1)+ 2² (1)+ 2¹ (1)+ 2⁰(0) = 64+8+4+2 = 78

¿Qué es lo que hace esta máquina? Y ¿Qué complejidad asintótica tiene en términos de computación y memoria?

Lo que hace la maquina es multiplicar el número por 2 y sumarle 4, y suma 4 porque al momento de cambiar el cero por el uno, el cambio se hace en la posición del número 4.

En este problema no hubo mucha complejidad porque se encontró un cero muy rápido así que no tuvo que volver hasta el inicio siendo este el peor caso porque tendría que recorrer toda la cinta de regreso, uno de los peores casos también seria que el numero binario fueran puros 1 y que solo hubiera un solo cero al principio de la cinta.

Este problema tiene complejidad asintótica de tiempo polinomial.