A teoria da computação teve início nos primeiros anos do século XX, antes da invenção dos modernos computadores eletrônicos. Naquela período, após a famosa palestra do matemático alemão David Hilbert em que ele listou os maiores desafios no campo da matemática para o século vindouro, os matemáticos se debruçavam sobre o décimo problema de Hilbert tentando descobrir quais problemas matemáticos poderiam ser resolvidos por um método efetivo, e quais não poderiam. O primeiro passo estava em definir o significado de um "método efetivo" para resolver o problema. Em outras palavras, eles precisavam de um modelo formal da computação.
Do que os matemáticos precisavam para descobrir quais problemas matemáticos poderiam ser resolvidos por um método efetivo?
modelo formal da computação precisavam de um modelo formal da computação um modelo formal da computação