La máquina de Turing es un entidad abstracta,no debe entenderse como un conjunto de mecanismos sino como un modelo matemático, que Alan Turing introdujo en su artículo "Sobre los Números Calculables" para desarrollar el teorema de Gödel y que posteriormente sentaría las bases de lo que hoy en día se llama algoritmo y por ende de la informática.Consiste básicamente en un autómata capaz de implementar cualquier problema matemático expresado a través de un algoritmo.
En su desarrollo teórico una máquina de Turing se compone de una cinta con cuadrados. En el interior de cada cuadrado se encuentran diferentes símbolos pertenecientes al alfabeto de entrada, ⎾. Además tiene un cabezal que se puede desplazar a lo largo de la cinta a izquierda y derecha leyendo el input ∑ (subconjunto del alfabeto que se da a la máquina como entrada en un instante determinado), o escribiendo los datos de salida correspondientes en la misma cinta.
Además una máquina de Turing cuenta con un registro de estados (q0...qn), que almacena el estado en el que la máquina se encuentra en el desarrollo del algoritmo. Cuando un algoritmo se inicia, este registro esta incializado con el estado q0 y cuando el algoritmo termina de ejecutarse se encontrará en el estado qn. Para entender dichos estados, se debe pensar en las etapas que recorre la mente de un individuo haciendo cálculos.
En la siguiente imagen se puede ver un diagrama de tres estados de un algoritmo muy simple para una máquina de Turing. La explicación es sencilla. Si la máquina se encuentra en el estado 0 y lee de la cinta un 0 entonces deja el 0 y se mueve a la derecha. Por el contrario si encuentra un 1, deja el 1, se mueve a la derecha y pasa al estado q1.
Una máquina de Turing actuará según el programa o algoritmo que tenga almacenado, (por ejemplo si está en estado q0 y lee un 1 escribe un 0 y mueve el cabezal a la izquierda).
De modo formal una máquina de Turing se pude definir del siguiente modo:
La función de transición es aquella que estando en un estado qn, se lee del alfabeto de entrada un símbolo y me permite escribir escribir un símbolo de salida, mover el cabezal a izquierda o derecha y pasar a un nuevo estado.
La máquina de Turing sentó las bases de la informática moderna ya que cualquier algoritmo que se piense, o que corra en una máquina de hoy día puede ser implementado en una máquina de Turing.
EL PROBLEMA DE LA PARADA
Como se ha explicado, la máquina de Turing sigue un programa y acaba al llegar a su final. Sin embargo puede ser que un programa nunca se detenga. Turing investigó este fenómeno, intentando demostrar si había una máquina de Turing a la cual se le diera como input el programa de otra máquina de Turing y sus valores de entrada y tuviera como output la respuesta a si el programa se paraba o no para una entrada determinada.
Turing demostró que este problema es irresoluble (demostración por reducción al absurdo) limitando en este sentido la máquina teórica que acababa de inventar.
SIMULADOR
En el siguiente enlace podemos comprobar el funcionamiento de una máquina de Turing con un sencillo programa escrito en un lenguaje ensamblador bastante sencillo. En el ejemplo el programa se dedica a ver si una cadena binaria es un palíndromo. Para elaborar un programa a nuestra medida en primer lugar deberíamos plantear el problema, crear el diagrama de estados como el mostrado en la figura anterior y posteriormente plasmarlo en el lenguaje ensamblador.
Simulador máquina de Turing
SIMULADOR REAL
En el siguiente enlace se puede observar la implementación real (con elementos móviles electromecánicos) de una máquina de Turing con todos sus elementos. Se puede apreciar la sencillez del sistema y además la polivalencia, pues se podría programar para diferentes fines.
Maquina de Turing Real
No hay comentarios:
Publicar un comentario