計算可能関数のクラスを定義する等価な方法がいくつも存在する。以下では、チューリングマシンで計算される部分関数として定義された計算可能関数を扱うものとする。同等の計算可能関数のクラスを定義する等価な計算模型はいくつもある。以下に一部を列挙する。計算可能関数の特性.計算可能関数の基本特性は、その関数の計算方法を示す有限の手続き(アルゴリズム)が必ず存在するということである。上記の計算模型は、そのような手続きの表現手法であるが、それらの間で多くの特性が共有されている。これらの計算模型が計算可能関数の等価なクラスを与えるということは、ある計算模型を使って別の計算模型の手続きを擬似できることを意味し、これはちょうどコンパイラがある言語から別の言語に変換するのと同じことである。従って、全ての計算可能関数には必ず有限長の完全なプログラムがあり、その関数をどう計算すべきかが示される。その関数を計算するには、単にその命令列を実行すればよく、何かを推測したり、前提となる知識に頼ったりすることはない。直観的に、手続きは逐次的に進行し、各ステップで何をすべきかは命令(規則)で示される。有限個のステップの実行によって関数の値が返される。計算複雑性理論では、計算に必要な時間や空間に何らかの前提を設けて関数を研究する。計算可能集合と計算可能関係.形式言語.例.以下の関数は計算可能関数である。以下の例では、関数を計算するのがどのアルゴリズムなのかが不明でも、関数が計算可能とされる場合があることを示す。チャーチ=チューリングのテーゼ.チャーチ=チューリングのテーゼは、ある関数が計算可能であることを証明するときに特定の具体的な計算模型で手続きを記述することを正当化するのに使われる。これが許されているのは、(少なくとも既知の)どの計算模型であっても記述能力に差がないことが分かっていて、単に様々な記述を省略するためにテーゼを利用していると見なせるからである。計算不能関数と判定不能問題.あらゆる計算可能関数にはその計算方法を示す有限な手続きが存在するので、計算可能関数は数え上げられるだけの個数しかない。自然数についての有限関数は数え上げられないほど無数にあり、その多くは計算可能ではない。ビジービーバー関数はそのような計算不能な関数の具体例である。計算可能性の拡張.加地秀綱