TURING (MÁQUINAS DE)

En el curso de investigaciones realizadas a partir de 1936, cuando estudiaba en Princeton, el matemático inglés A. M. Turing (1912-1954) presentó un modelo de computabilidad que ha venido sir­viendo de patrón para las operaciones realiza­das por todos los computadores digitales o de estado discreto. Este modelo es conocido con el nombre de «máquina de Turing». No se trata propiamente de una máquina, sino de un modelo para construir máquinas computado­ras. Estas últimas pueden ser consideradas, de un modo o de otro, como «máquinas de Tu­ring». La «máquina de Turing» es una má­quina universal.

La idea de Turing («On Computable Numbers, with an Application to the Entscheidungsproblem», Proceedings of the London Mathematical Society, 42 [1937], 230-265) para el modelo referido consiste sustancial­mente en un número de instrucciones propor­cionadas para dar ciertos pasos en secuencia. Los pasos constituyen, así, una secuencia de