La máquina de Turing (1936)
Alan Turing, matemático británico de 24 años, publica un artículo fundacional en el que define un modelo abstracto de cálculo: una cinta infinita, un cabezal de lectura/escritura y un conjunto finito de estados. Esta máquina puede simular cualquier algoritmo.
El problema de la decisión
Turing responde negativamente al Entscheidungsproblem de David Hilbert: existen funciones matemáticas que ningún procedimiento mecánico puede calcular (problema de la parada). Este resultado, obtenido independientemente por Alonzo Church, traza los límites fundamentales del cálculo.
Impacto
La tesis de Church-Turing afirma que todo cálculo efectivo puede ser realizado por una máquina de Turing. Este modelo teórico es la base de toda la informática: compiladores, complejidad algorítmica, inteligencia artificial.