Máquina de Turing, dispositivo informático hipotético introducido en 1936 por el matemático y lógico inglés Alan M. Turing. Turing concibió originalmente la máquina como una herramienta matemática que podía reconocer infaliblemente proposiciones indecidibles, es decir, aquellos enunciados matemáticos que, dentro de un sistema formal de axiomas dado, no pueden demostrarse como verdaderos o falsos. (El matemático Kurt Gödel había demostrado que tales proposiciones indecidibles existen en cualquier sistema lo suficientemente potente como para contener la aritmética). Turing, en cambio, demostró que nunca puede existir ningún método algorítmico universal para determinar si una proposición es indecidible.
La máquina de Turing no es una máquina en el sentido ordinario, sino más bien un modelo matemático idealizado que reduce la estructura lógica de cualquier dispositivo de computación a lo esencial. Tal como la concibió Turing, la máquina realiza sus funciones en una secuencia de pasos discretos y asume sólo uno de una lista finita de estados internos en cualquier momento. La máquina en sí consta de una cinta infinitamente extensible, un cabezal de cinta que es capaz de realizar diversas operaciones en la cinta, y un mecanismo de control modificable en el cabezal que puede almacenar direcciones de un conjunto finito de instrucciones. La cinta está dividida en cuadrados, cada uno de los cuales está en blanco o tiene impreso uno de un número finito de símbolos. El cabezal de la cinta tiene la capacidad de moverse, leer, escribir y borrar cualquier cuadrado individual y también puede cambiar a otro estado interno en cualquier momento. Cualquier acto de este tipo viene determinado por el estado interno de la máquina y el estado de la casilla escaneada en un momento dado. La salida de la máquina -es decir, la solución a una consulta matemática- puede leerse del sistema una vez que la máquina se ha detenido. (Sin embargo, en el caso de las proposiciones indecidibles de Gödel, la máquina nunca se detendría, lo que se conoció como el «problema de detención»)
Al incorporar todas las características esenciales del procesamiento de la información, la máquina de Turing se convirtió en la base de todos los ordenadores digitales posteriores, que comparten el esquema básico de la máquina de un dispositivo de entrada/salida (cinta y lector), memoria (almacenamiento del mecanismo de control) y unidad central de procesamiento (mecanismo de control).