Alan Turing describe la máquina la
máquina de Turing, la cual formaliza el concepto de algoritmo.
Una máquina de Turing es un
dispositivo que manipula símbolos sobre una tira de cinta de
acuerdo a una tabla de reglas. A pesar de su simplicidad, una
máquina de Turing puede ser adaptada para simular la lógica de
cualquier algoritmo de computador y es particularmente útil en la
explicación de las funciones de un CPU dentro de un computador.
La Máquina de Turing fue descrita por Alan Turing como una <<máquina automática>> en 1936 en la revista Proceedings of the London Mathematical Society, La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.
Un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y
finitas que permite realizar una actividad mediante pasos sucesivos
que generan dudas a quien deba realizar dicha actividad. Los
algoritmos son el objeto de estudio de la algoritmia.
Esta imagen mostrada es una Máquina de Turing hecha realidad. El creador, Mike Davey, pensó que sería divertido construir físicamente la máquina teórica concebida en la mente del pionero de la computación Alan Turing.
La Máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la 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: