10

Maquina de Turing:

Abstraccion matematica diseñada por Turing para explicar de manera teorica el funcionamiento de una computadora. Esta formada por:

  • Cinta dividida en casilla (memoria)
  • Cabeza movil que lee y escribe simbolos en ella (microprocesador)
  • Programa que le diga a la cabeza que hacer

Abstraccion Matematica:
MT = (Q,q0,T,∑,δ)
Donde:
Q = Conjunto de estados posibles
qo = Estado inicia
T = Conjunto de simbolos posibles
∑ = Input inicial(simbolos de inicio)
δ = Funcion de Transicion

Sintaxis de δ:
δ(qo,σo)=(σf,M,qf)
qo=estado incial
σo=simbolo inicial (si encuentra este simbolo ejecuta la expresion)
σf=simbolo final (cambia el simbolo actual por σf)
M=movimiento de la cabeza (R(derecha) L(izquierda) *(no se mueve))
qf=estado final (cambia el estado a qf)

Ejemplo:
δ(q1,1)=(0,L,q2)
Significa si estas en el estado q1 y leer un 1, cambia el valor a 0, muevete a la izquierda y pasa al estado q2

Ejemplo de un programa de Turing: Sumar 1 a un binario
Q = {q0,q1,q2,q3}
T = {_,0,1}

∑ : numero binario de tres digitos

Programa:
#El programa inicia en el simbolo no vacio de la izquierda
#Nos vamos a la derecha hasta el ultimo digito no vacio
#Una vez ahi cambiamos al estado q1
δ(q0,)=(,L,q1)
δ(q0,0)=(0,R,q0)
δ(q0,1)=(1,R,q0)

#Si encotramos un 0 lo convertimos en 1 y termina el programa (q2)
#Si encontramos un 1 lo convertimos en cero y llevamos 1 al numero de la derecha seguimos en el estado q1
#Si encotramos un vacio () escribimos 1 en el (el uno que llevamos anteriormente) y termina el programa (q2)
δ(q1,0)=(1,*,q2)
δ(q1,1)=(0,L,q1)
δ(q1,
)=(1,*,q2)

#Fin del programa
δ(q3,1)=(1,*,q3)!

Primitivos de Turing:
Son los requerimientos minimos de una maquina para ejecutar cualquier programa son:

  • RIGTH: Moverse a la derecha
  • LEFT: Moverse a la izquierda
  • PRINT: Escribir
  • SCAN: Leer
  • ERASE: Borrar
  • NOTHING/HALT: No hacer nada

Con ellos podemos:

  • Tomar/cambiar/borrar datos (scan/print/erase)
  • Tomar decisiones: (moverse a la derecha/izquierda, cambiar de estado)
  • Instrucciones repetitivas: (seguir en la misma instruccion mientras se cumpla una condicion)
  • Terminar el programa (NOTHING/HALT)

En conclusion la maquina de Turing es una abstraccion de una maquina capaz de hacer cualquier computo que fundo las bases matematicas para luego construir las computadoras que tenemos hoy en dia

Escribe tu comentario
+ 2