計算可能関数
直観的に、手続きは逐次的に進行し、各ステップで何をすべきかは命令(規則)で示される。有限個のステップの実行によって関数の値が返される。
「その手続きに f の定義域にない k-タプル x が与えられるとき、手続きは永久に続き、停止しない可能性がある。あるいはある時点で停止したとしても、x についての f の値を返さない」
従って、f(x) の値が見つかった場合、その値は正しい。手続きが値を返すとき、その値は常に正しいので、受け取った側がそれが正しいか間違っているかを判断する必要はない。
Enderton はさらに計算可能関数の手続きの満たすべき条件を以下のように挙げている。
手続きは任意の大きさの引数を扱えなければならない。例えば、引数が地球上にある原子数より小さいというような前提はない。
手続きは出力を生成するまでに有限個のステップを実施して停止する必要があるが、そのステップ数は非常に大きくなる可能性がある。時間制限は特にない。
手続きは値を返す場合には有限の空間(領域)を使って計算するが、使用する空間の量に制限はない。手続きが必要とするだけの空間(記憶領域)が与えられるものとされる。
計算複雑性理論では、計算に必要な時間や空間に何らかの前提を設けて関数を研究する。
計算可能関数(けいさんかのうかんすう、英: Computable function)は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。
計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable(実効的に計算可能)という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective(実効的)であってもefficient(効率的)に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。
チャーチ=チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い(いくら長くても良いが)有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。
ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。