計算可能関数
あらゆる計算可能関数にはその計算方法を示す有限な手続きが存在するので、計算可能関数は数え上げられるだけの個数しかない。自然数についての有限関数は数え上げられないほど無数にあり、その多くは計算可能ではない。ビジービーバー関数はそのような計算不能な関数の具体例である。
同様に自然数の部分集合の多くは計算可能ではない。チューリングマシンの停止問題はそのような計算不能な集合の例である。ダフィット・ヒルベルトの提唱した Entscheidungsproblem(決定問題)は(自然数で符号化された)数学的な文が真であるかどうかを決定する実効的な手続きがあるかどうかを問うものであった。これについて1930年代にチューリングとチャーチは個別に決定不能であることを示した。チャーチ=チューリングのテーゼによれば、そのような計算を行える実効的な手続き(アルゴリズム)は存在しない。
計算可能関数の基本特性は、その関数の計算方法を示す有限の手続き(アルゴリズム)が必ず存在するということである。上記の計算模型は、そのような手続きの表現手法であるが、それらの間で多くの特性が共有されている。これらの計算模型が計算可能関数の等価なクラスを与えるということは、ある計算模型を使って別の計算模型の手続きを擬似できることを意味し、これはちょうどコンパイラがある言語から別の言語に変換するのと同じことである。
Enderton [1997] では計算可能関数の計算手続きの特性を次のように表している。同様の考え方は、Turing [1936]、Rogers [1967]、などでも示されている。
「その手続きには、有限長の明確な命令列(すなわちプログラム)がなければならない」
従って、全ての計算可能関数には必ず有限長の完全なプログラムがあり、その関数をどう計算すべきかが示される。その関数を計算するには、単にその命令列を実行すればよく、何かを推測したり、前提となる知識に頼ったりすることはない。
「その手続きに f の定義域にある k-タプル x が与えられるとき、有限個の離散ステップを実行後にその手続きは完了し、f(x) を生成する」