計算可能関数

計算可能関数（けいさんかのうかんすう、）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。
計算可能関数の正確な定義が与えられる以前から、数学者は "effectively computable"（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。
チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。
ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。
定義.
計算可能関数は、自然数についての部分関数である。計算可能関数 formula_1 は引数として固定個の自然数をとり、個々の計算可能関数によって引数の個数は異なる。部分関数なので、あらゆる入力の組合せについて定義されているとは限らない。計算可能関数は出力として1つの自然数を返す（この出力を対関数を使って自然数のリストに変換することもできる）。formula_2 と記した場合、引数 formula_3 についての部分関数formula_4を表し、formula_5 と記した場合、formula_1 が引数 formula_3 について定義されていて返す値が formula_8 であることを示している。これらの関数を部分再帰関数（Partial recursive function）と呼ぶ。再帰理論では、関数の定義域はその関数が定義されているあらゆる入力の集合とされる。
全ての引数について定義されている関数を全域関数と呼ぶ。計算可能関数のうち全域関数であるものを全域計算可能関数（Total computable function）または全域再帰関数（Total recursive function）と呼ぶ。
計算可能関数のクラスを定義する等価な方法がいくつも存在する。以下では、チューリングマシンで計算される部分関数として定義された計算可能関数を扱うものとする。同等の計算可能関数のクラスを定義する等価な計算模型はいくつもある。以下に一部を列挙する。
計算可能関数の特性.
計算可能関数の基本特性は、その関数の計算方法を示す有限の手続き（アルゴリズム）が必ず存在するということである。上記の計算模型は、そのような手続きの表現手法であるが、それらの間で多くの特性が共有されている。これらの計算模型が計算可能関数の等価なクラスを与えるということは、ある計算模型を使って別の計算模型の手続きを擬似できることを意味し、これはちょうどコンパイラがある言語から別の言語に変換するのと同じことである。
Enderton [1997] では計算可能関数の計算手続きの特性を次のように表している。同様の考え方は、Turing [1936]、Rogers [1967]、などでも示されている。
従って、全ての計算可能関数には必ず有限長の完全なプログラムがあり、その関数をどう計算すべきかが示される。その関数を計算するには、単にその命令列を実行すればよく、何かを推測したり、前提となる知識に頼ったりすることはない。
直観的に、手続きは逐次的に進行し、各ステップで何をすべきかは命令（規則）で示される。有限個のステップの実行によって関数の値が返される。
従って、"f(x)" の値が見つかった場合、その値は正しい。手続きが値を返すとき、その値は常に正しいので、受け取った側がそれが正しいか間違っているかを判断する必要はない。
Enderton はさらに計算可能関数の手続きの満たすべき条件を以下のように挙げている。
計算複雑性理論では、計算に必要な時間や空間に何らかの前提を設けて関数を研究する。
計算可能集合と計算可能関係.
自然数の集合 "A" が計算可能（帰納的、決定可能）であるとは、数 "n" に関する計算可能関数 "f" があり、"n" が "A" に属する場合は formula_9、そうでない場合は formula_10 となることをいう。
自然数の集合が計算可枚挙（Computably enumerable、帰納可枚挙、準決定可能）であるとは、数 "n" に関する計算可能関数 "f" があり、"f(n)" が "n" がその集合に属する場合だけ定義されていることをいう。従って、ある計算可能関数の定義域だけが計算可枚挙な集合である。"enumerable"（可枚挙、枚挙可能）という用語が使われるのは、自然数の空でない部分集合 "B" について以下が等価であるためである。
集合 "B" が関数 "f" の値域である場合、その関数は "B" の列挙と見ることができる。というのも、"f(0)", "f(1)", ... というリストが "B" の全ての元を含むからである。
自然数における有限関係には自然数の有限な数列の集合が対応するので、計算可能関係（computable relation）や計算可枚挙関係（computably enumerable relation）は、集合からのアナロジーで定義できる。
形式言語.
計算可能性理論は主に形式言語を扱う。アルファベットは任意の集合である。単語はアルファベットに含まれる文字（記号=集合の元）を有限個並べたものである。同じ文字が複数回使われてもよい。例えば、2進数の文字列はアルファベット formula_11 における単語である。言語は、あるアルファベットにおける全単語の集合の部分集合である。例えば、2進数表記のうち 1 を必ず3個含むものの集合はバイナリのアルファベットにおける言語である。
形式言語の重要な特性として、ある単語がある言語に属するかどうかの判定の難しさのレベルがある。ある言語に属する単語を入力として受け付ける計算可能関数を定義するには何らかの符号体系を構築しなければならない。ある言語が計算可能であるとは、あるアルファベットにおける単語 "w" についての計算可能関数 formula_1 があり、その単語がその言語に属する場合は formula_13、その単語がその言語に属さない場合は formula_14 となることをいう。つまり、ある言語が計算可能であるとは、任意の単語がその言語に属するかどうかを正しく判定できる手続きがある場合をいう。
ある言語が計算可枚挙であるとは、計算可能関数 "f" があり、単語 "w" がその言語に属するときだけ formula_15 が定義されていることをいう。"enumerable" という用語の語源は自然数の計算可枚挙な集合の場合と同じである。
例.
以下の関数は計算可能関数である。
"f" と "g" が計算可能ならば、"f + g"、"f * g"、formula_16（"f"が単項の場合）、max("f","g")、min("f","g")などといった様々な組合せも計算可能関数となる。
以下の例では、関数を計算するのがどのアルゴリズムなのかが不明でも、関数が計算可能とされる場合があることを示す。
チャーチ＝チューリングのテーゼ.
チャーチ＝チューリングのテーゼは、上述の3つの特性を持つ手続きで計算可能な関数を計算可能関数であると主張したものである。それら3つの特性は形式的に表現できないため、チャーチ＝チューリングのテーゼは証明できない。以下の事実がしばしばこのテーゼの証拠とされる。
チャーチ＝チューリングのテーゼは、ある関数が計算可能であることを証明するときに特定の具体的な計算模型で手続きを記述することを正当化するのに使われる。これが許されているのは、（少なくとも既知の）どの計算模型であっても記述能力に差がないことが分かっていて、単に様々な記述を省略するためにテーゼを利用していると見なせるからである。
計算不能関数と判定不能問題.
あらゆる計算可能関数にはその計算方法を示す有限な手続きが存在するので、計算可能関数は数え上げられるだけの個数しかない。自然数についての有限関数は数え上げられないほど無数にあり、その多くは計算可能ではない。ビジービーバー関数はそのような計算不能な関数の具体例である。
同様に自然数の部分集合の多くは計算可能ではない。チューリングマシンの停止問題はそのような計算不能な集合の例である。ダフィット・ヒルベルトの提唱した Entscheidungsproblem（決定問題）は（自然数で符号化された）数学的な文が真であるかどうかを決定する実効的な手続きがあるかどうかを問うものであった。これについて1930年代にチューリングとチャーチは個別に決定不能であることを示した。チャーチ＝チューリングのテーゼによれば、そのような計算を行える実効的な手続き（アルゴリズム）は存在しない。
計算可能性の拡張.
関数の計算可能性は、自然数の任意の集合 "A" または等価な任意の（自然数から自然数への）関数 "f" についての神託機械で拡張されたチューリングマシン（あるいは何らかの同等なモデル）を使って、任意の "A" や "f" に相対化できる。このような関数をそれぞれ、A-計算可能あるいはf-計算可能と呼ぶ。
チャーチ＝チューリングのテーゼは計算可能関数に全てのアルゴリズムのある関数が含まれるとしているが、アルゴリズムが持つべき特性をゆるめた、より広い関数のクラスも定義可能である。Hypercomputation という研究分野では、答を得るまでに無限のステップを実行できる計算可能性記法を研究している。さらに一般化した再帰理論としてE-再帰理論があり、任意の集合をE-再帰関数の引数として使うことができる。