Puntos Extras...Respuestas Modelo-3

<<Puntos Extras>>

Maquina Turing(Examen de Medio Curso)

Principalmente tendremos que convertir el 37 en número binario.

37 / 2 = 18 ----1

18/ 2= 9---------0

9/ 2= 4-----------1

4/ 2= 2-----------0

2/2= 1------------0

1/2=0-------------1

Obtenemos el número binario siguiente: 1OO1O1

Después lo situamos en la cinta de la maquina turing:

Se queda en estado “s” coloca un 0 y mueve a la derecha

Se queda en estado “s” valor 1 y avanza hacia la derecha

Se queda en estado “s” valor 0 y avanza hacia la derecha, hasta que encuentra una posición vacía en la cinta.

Se convierte en estado “t” se coloca un 0 y avanza hacia la izquierda

Se queda en estado “t” se valor 1 y avanza hacia la izquierda

Se cambia a “si” se convierte a 1 y ahí se detiene.

¿Qué es la salida de la maquina turing (decimal)?

-Al último tenemos como resultado en la cinta el siguiente número binario: 01001110

-Después la conversión de 01001110 es: 2⁶+2³+2²+2¹=78

¿Qué hace la maquina turing?

-Lo que hace la maquina turing es que, multiplica el numero por 2 (porque agrega un 0 en la ultima posición) y le suma, en este caso 4 ya que depende de la posición en el que se encuentra el primer 0 de izquierda a derecha.

¿Qué complejidad tiene?

-Su complejidad es de 0(n), ya que depende de la cantidad de pasos a realizar(n num).