En 1936, Alan Turing publicó “On Computable Numbers”, introduciendo lo que hoy llamamos máquina de Turing: un modelo mínimo capaz de simular cualquier procedimiento algorítmico efectivo.
Con ese modelo demostró que el problema de la parada es indecidible: no existe un algoritmo general que diga si un programa arbitrario termina. Church llegó a conclusiones equivalentes con el cálculo lambda.
La tesis Church–Turing unificó la noción de computabilidad. Sin ese lenguaje común, no habría teoría de la complejidad ni una base clara para preguntar qué puede “aprender” o “razonar” una máquina.
