A máquina de Turing — Fundamentos teóricos da computação
Em 1936, Alan Turing publica “On Computable Numbers” e define uma máquina abstrata capaz de executar tudo o que é efetivamente computável. Ele estabelece os fundamentos teóricos da computação e demonstra a existência de problemas indecidíveis.
Source: cs.virginia.edu
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.