基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。その定義には特定の計算モデルを参照する必要がある。computable(実効的に計算可能)という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。計算複雑性理論は、そのような関数の計算効率を研究している。チャーチ=チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い(いくら長くても良いが)有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。定義[編集]計算可能関数は、自然数についての部分関数である。f}は引数として固定個の自然数をとり、個々の計算可能関数によって引数の個数は異なる。部分関数なので、あらゆる入力の組合せについて定義されているとは限らない。計算可能関数は出力として1つの自然数を返す(この出力を対関数を使って自然数のリストに変換することもできる)。y}であることを示している。function)と呼ぶ。再帰理論では、関数の定義域はその関数が定義されているあらゆる入力の集合とされる。全ての引数について定義されている関数を全域関数と呼ぶ。function)と呼ぶ。計算可能関数のクラスを定義する等価な方法がいくつも存在する。以下では、チューリングマシンで計算される部分関数として定義された計算可能関数を扱うものとする。同等の計算可能関数のクラスを定義する等価な計算模型はいくつもある。以下に一部を列挙する。計算可能関数の基本特性は、その関数の計算方法を示す有限の手続き(アルゴリズム)が必ず存在するということである。上記の計算模型は、そのような手続きの表現手法であるが、それらの間で多くの特性が共有されている。これらの計算模型が計算可能関数の等価なクラスを与えるということは、ある計算模型を使って別の計算模型の手続きを擬似できることを意味し、これはちょうどコンパイラがある言語から別の言語に変換するのと同じことである。計算可能関数の計算手続きの特性を次のように表している。[1967]、などでも示されている。従って、全ての計算可能関数には必ず有限長の完全なプログラムがあり、その関数をどう計算すべきかが示される。その関数を計算するには、単にその命令列を実行すればよく、何かを推測したり、前提となる知識に頼ったりすることはない。直観的に、手続きは逐次的に進行し、各ステップで何をすべきかは命令(規則)で示される。有限個のステップの実行によって関数の値が返される。与えられるとき、手続きは永久に続き、停止しない可能性がある。値が見つかった場合、その値は正しい。手続きが値を返すとき、その値は常に正しいので、受け取った側がそれが正しいか間違っているかを判断する必要はない。計算可能関数の手続きの満たすべき条件を以下のように挙げている。手続きは任意の大きさの引数を扱えなければならない。引数が地球上にある原子数より小さいというような前提はない。手続きは出力を生成するまでに有限個のステップを実施して停止する必要があるが、そのステップ数は非常に大きくなる可能性がある。手続きは値を返す場合には有限の空間(領域)を使って計算するが、使用する空間の量に制限はない。手続きが必要とするだけの空間(記憶領域)が与えられるものとされる。計算複雑性理論では、計算に必要な時間や空間に何らかの前提を設けて関数を研究する。=0}となることをいう。その集合に属する場合だけ定義されていることをいう。従って、ある計算可能関数の定義域だけが計算可枚挙な集合である。ついて以下が等価であるためである。計算可能関数の定義域である。全域計算可能関数の値域である。無限である場合、その関数は単射と見なされる。列挙と見ることができる。全ての元を含むからである。relation)は、集合からのアナロジーで定義できる。アルファベットは任意の集合である。単語はアルファベットに含まれる文字(記号=集合の元)を有限個並べたものである。同じ文字が複数回使われてもよい。\{0,1\}}における単語である。言語は、あるアルファベットにおける全単語の集合の部分集合である。3個含むものの集合はバイナリのアルファベットにおける言語である。形式言語の重要な特性として、ある単語がある言語に属するかどうかの判定の難しさのレベルがある。ある言語に属する単語を入力として受け付ける計算可能関数を定義するには何らかの符号体系を構築しなければならない。=0}となることをいう。ある言語が計算可能であるとは、任意の単語がその言語に属するかどうかを正しく判定できる手続きがある場合をいう。f(w)}が定義されていることをいう。いう用語の語源は自然数の計算可枚挙な集合の場合と同じである。例[編集]以下の関数は計算可能関数である。n2素因数分解関数2つの数の最大公約数(を求めること)は計算可能関数である。g}(fが単項の場合)、max(f,g)、min(f,g)などといった様々な組合せも計算可能関数となる。以下の例では、関数を計算するのがどのアルゴリズムなのかが不明でも、関数が計算可能とされる場合があることを示す。