Alan Mathison Turing tomando los teoremas de Incompletitud de Gödel y con la misma idea de “effective calculability” de Alonzo Church, más el problema que plantearon David Hilbert y Wilhelm Ackermann en 1.928 como problema “Entscheidungs – Problema de Decisión”, publica en 1.936 “On computable numbers, with an application to the Entscheidungsproblem”, a la postre la Máquina de Turing.
La Máquina de Turing es una máquina abstracta, o modelo matemático, consistente en un autómata que es capaz de recrear cualquier problema matemático expresado a través de un algoritmo, simulando su lógica en un computador. Con esta “máquina” pudo demostrar que hay problemas irresolubles y por tanto ningún computador sería capaz de obtener la solución.
El modelo presentado por Turing es similar a los propuestos por Alonzo Church (Cálculo Lambda), Kurt Gödel y Stephen Kleene (Funciones Recursivas Parciales) y Kurt Gödel, Stephen Kleene y Jacques Herbrand (Funciones Recursivas Generales).
La “máquina” de Turing tiene una cinta infinita dividida en cuadrados (Celdas), cada uno de los cuales puede estar en blanco o puede llevar un símbolo, 0 o 1, o algún otro símbolo tomado de un alfabeto finito. Sobre la cinta actúa un dispositivo que puede adoptar diversos estados y que, en cada instante, lee un símbolo de la casilla sobre la que esta situado. En función del símbolo leído y del estado en el cual se encuentra, realiza tres acciones:
- Pasa a un nuevo estado
- Imprime un símbolo en lugar del que acaba de leer,
- Se desplaza una posición hacia la izquierda, o derecha, o se para.
Existen distintos tipos de máquinas de Turing:
- Con cinta infinita a ambos lados.
- Con cinta multipista y/o multicinta.
- Determinista y no determinista.
- Cuántica.
La Máquina Universal de Turing, es universal en el sentido de que puede programarse para realizar cualquier cálculo que pueda ser realizado por un humano, un trabajador que actúe de acuerdo con un procedimiento. La máquina universal tiene una única tabla fija de instrucciones, operando de acuerdo con esta tabla fija, puede leer y ejecutar instrucciones codificadas inscritas en su cinta que es el concepto de “programa almacenado”.
Ver la Máquina Neuronal de Turing (MNT).