関数が計算可能であるとはどういうことか？
非公式には、関数はその値が計算可能であれば計算可能であるが、アラン・チューリング、アロンゾ・チャーチ、クルト・ゲーデルはそれぞれ、チューリング・マシン、ラムダ計算、一般再帰関数という計算可能性の正式な定義を持っていた。  チャーチ・チューリング論文でこれら3つの定式化が等価であることが示されると、計算可能性の正式な定義として使用できることがより明確になった。