Abstraccion matematica diseñada por Turing para explicar de manera teorica el funcionamiento de una computadora. Esta formada por:
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:
Con ellos podemos:
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
Hola, muy buen aporte. Podrías por favor compartir las referencias?
Hola, claro aquí te dejo algunos links que me sirvieron para crear este aporte: