チャーチ＝チューリングのテーゼ
1932年にエルブラン、および1934年にゲーデルが、原始帰納的関数と呼ばれる自然数上の関数の明示的構成法を拡張して帰納的関数(もしくは一般帰納的関数)と呼ばれる関数の構成法を作り上げた。1933年から1935年ごろには、チャーチやクリーネがやはり関数の構成的な定義法であるラムダ記法を用いて定義可能な関数のクラスを定めた。さらに、1935年から1936年にかけてポストとチューリングは、チューリングマシンの概念を用いてこの理念的計算機械で実行可能なプログラムのクラスを定めた。
こうしてほぼ同時期に出現したさまざまな計算できる数論的関数のクラスは、実は互いに同じものであることが証明された。これにより、それまで非形式的に「実質的に計算できる関数」(effectively computable function) と呼び慣わされていたこのクラスをもってして「計算できる関数」とみなそうという主張がなされることになった。