A tese de Church–Turing

Resumo

De acordo com a tese de Church–Turing, se um cálculo puder ser
feito de forma automatizada — por um dado método, num número finito de
passos — então também pode ser feito por uma máquina de Turing. Neste
artigo faz-se uma breve introdução à tese de Church–Turing e ao contexto
histórico da sua formulação. Inclui-se uma tradução comentada de parte
do artigo de Alan Turing de 1936–37, “On computable numbers, with an
application to the Entscheidungsproblem” [24], onde é possível entender a
origem da máquina de Turing.