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.