Modelo computacional creado por Alan Turing con el cual él afirmaba que se podía realizar cualquier computación.
La máquina de Turing, como modelo matemático, consta de un cabezal lector/escritor y una cinta infinita en lo que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a avanzar el cabezal por la izquierda o la derecha despues de haber leído o escrito algo en la casilla de la cinta.
La computación es determinada a partir de una tabla de estados de la forma:
(estado,valor) → (nuevo estado, nuevo valor, dirección)
Esta tabla toma como parametros el estado actual de la maquina y el caracter leido de la cinta, y da como resultado la dirección de movimiento del cabezal, el nuevo estado de la maquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquier computación que un computador digital pueda.
Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinomial son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.
De hecho, de puede demostrar que para cualquier programa informático es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente en mediados del siglo XX.
