A máquina de Turing (1936)
Alan Turing, matemático britânico de 24 anos, publica um trabalho fundamental no qual define um modelo abstrato de computação: uma fita infinita, uma cabeça de leitura/escrita e um conjunto finito de estados. Essa máquina pode simular qualquer algoritmo.
O problema da decisão
Turing dá uma resposta negativa ao Entscheidungsproblem de David Hilbert: existem funções e problemas matemáticos que nenhum procedimento mecânico pode resolver de forma geral, entre eles o problema da parada. Alonzo Church chega independentemente a um resultado equivalente.
Impacto
A tese de Church-Turing afirma que toda função efetivamente computável pode ser calculada por uma máquina de Turing. Esse modelo teórico fundamenta compiladores, teoria da complexidade e inteligência artificial.