計算可能関数

計算可能関数︵けいさんかのうかんすう、英: Computable function︶は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。

計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable︵実効的に計算可能︶という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective︵実効的︶であってもefficient︵効率的︶に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。

チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い︵いくら長くても良いが︶有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。

ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。

定義

計算可能関数は、自然数についての部分関数である。計算可能関数 $f$$f$は引数として固定個の自然数をとり、個々の計算可能関数によって引数の個数は異なる。部分関数なので、あらゆる入力の組合せについて定義されているとは限らない。計算可能関数は出力として1つの自然数を返す︵この出力を対関数を使って自然数のリストに変換することもできる︶。$f(x_{1},\ldots ,x_{k})\downarrow$$f(x_{1},\ldots ,x_{k})\downarrow$ と記した場合、引数 $x_{1},\ldots ,x_{k}$$x_{1},\ldots ,x_{k}$についての部分関数$f$$f$を表し、$f(x_{1},\ldots ,x_{k})\downarrow =y$$f(x_{1},\ldots ,x_{k})\downarrow =y$ と記した場合、$f$$f$ が引数 $x_{1},\ldots ,x_{k}$$x_{1},\ldots ,x_{k}$について定義されていて返す値が $y$$y$であることを示している。これらの関数を部分再帰関数︵Partial recursive function︶と呼ぶ。再帰理論では、関数の定義域はその関数が定義されているあらゆる入力の集合とされる。

全ての引数について定義されている関数を全域関数と呼ぶ。計算可能関数のうち全域関数であるものを全域計算可能関数︵Total computable function︶または全域再帰関数︵Total recursive function︶と呼ぶ。

計算可能関数のクラスを定義する等価な方法がいくつも存在する。以下では、チューリングマシンで計算される部分関数として定義された計算可能関数を扱うものとする。同等の計算可能関数のクラスを定義する等価な計算模型はいくつもある。以下に一部を列挙する。

• チューリングマシン
• μ再帰関数
• ラムダ計算
• コンビネータ論理
• タグシステム - ポストマシンとも
• レジスタマシン

計算可能関数の特性

詳細は「アルゴリズム」を参照

計算可能関数の基本特性は、その関数の計算方法を示す有限の手続き︵アルゴリズム︶が必ず存在するということである。上記の計算模型は、そのような手続きの表現手法であるが、それらの間で多くの特性が共有されている。これらの計算模型が計算可能関数の等価なクラスを与えるということは、ある計算模型を使って別の計算模型の手続きを擬似できることを意味し、これはちょうどコンパイラがある言語から別の言語に変換するのと同じことである。

Enderton [1997] では計算可能関数の計算手続きの特性を次のように表している。同様の考え方は、Turing [1936]、Rogers [1967]、などでも示されている。

●﹁その手続きには、有限長の明確な命令列︵すなわちプログラム︶がなければならない﹂

従って、全ての計算可能関数には必ず有限長の完全なプログラムがあり、その関数をどう計算すべきかが示される。その関数を計算するには、単にその命令列を実行すればよく、何かを推測したり、前提となる知識に頼ったりすることはない。

●﹁その手続きに fの定義域にある k-タプル xが与えられるとき、有限個の離散ステップを実行後にその手続きは完了し、f(x) を生成する﹂

直観的に、手続きは逐次的に進行し、各ステップで何をすべきかは命令︵規則︶で示される。有限個のステップの実行によって関数の値が返される。

●﹁その手続きに fの定義域にない k-タプル xが与えられるとき、手続きは永久に続き、停止しない可能性がある。あるいはある時点で停止したとしても、x についての fの値を返さない﹂

従って、f(x) の値が見つかった場合、その値は正しい。手続きが値を返すとき、その値は常に正しいので、受け取った側がそれが正しいか間違っているかを判断する必要はない。

Enderton はさらに計算可能関数の手続きの満たすべき条件を以下のように挙げている。

●手続きは任意の大きさの引数を扱えなければならない。例えば、引数が地球上にある原子数より小さいというような前提はない。

●手続きは出力を生成するまでに有限個のステップを実施して停止する必要があるが、そのステップ数は非常に大きくなる可能性がある。時間制限は特にない。

●手続きは値を返す場合には有限の空間︵領域︶を使って計算するが、使用する空間の量に制限はない。手続きが必要とするだけの空間︵記憶領域︶が与えられるものとされる。

計算複雑性理論では、計算に必要な時間や空間に何らかの前提を設けて関数を研究する。

計算可能集合と計算可能関係

自然数の集合 Aが計算可能︵帰納的、決定可能︶であるとは、数 nに関する計算可能関数 fがあり、n が Aに属する場合は ${\displaystyle f($n)\downarrow =1} $f(n)\downarrow =1$、そうでない場合は ${\displaystyle f($n)\downarrow =0} $f(n)\downarrow =0$となることをいう。

自然数の集合が計算可枚挙︵Computably enumerable、帰納可枚挙、準決定可能︶であるとは、数 nに関する計算可能関数 fがあり、f(n) が nがその集合に属する場合だけ定義されていることをいう。従って、ある計算可能関数の定義域だけが計算可枚挙な集合である。enumerable︵可枚挙、枚挙可能︶という用語が使われるのは、自然数の空でない部分集合 Bについて以下が等価であるためである。

●B が計算可能関数の定義域である。

●B が全域計算可能関数の値域である。B が無限である場合、その関数は単射と見なされる。

集合 Bが関数 fの値域である場合、その関数は Bの列挙と見ることができる。というのも、f(0), f(1), ... というリストが Bの全ての元を含むからである。

自然数における有限関係には自然数の有限な数列の集合が対応するので、計算可能関係︵computable relation︶や計算可枚挙関係︵computably enumerable relation︶は、集合からのアナロジーで定義できる。

形式言語

詳細は「形式言語」を参照

計算可能性理論は主に形式言語を扱う。アルファベットは任意の集合である。単語はアルファベットに含まれる文字︵記号=集合の元︶を有限個並べたものである。同じ文字が複数回使われてもよい。例えば、2進数の文字列はアルファベット $\{0,1\}$$\{0,1\}$における単語である。言語は、あるアルファベットにおける全単語の集合の部分集合である。例えば、2進数表記のうち1を必ず3個含むものの集合はバイナリのアルファベットにおける言語である。

形式言語の重要な特性として、ある単語がある言語に属するかどうかの判定の難しさのレベルがある。ある言語に属する単語を入力として受け付ける計算可能関数を定義するには何らかの符号体系を構築しなければならない。ある言語が計算可能であるとは、あるアルファベットにおける単語 wについての計算可能関数 $f$$f$があり、その単語がその言語に属する場合は ${\displaystyle f($w)\downarrow =1} $f(w)\downarrow =1$、その単語がその言語に属さない場合は ${\displaystyle f($w)\downarrow =0} $f(w)\downarrow =0$となることをいう。つまり、ある言語が計算可能であるとは、任意の単語がその言語に属するかどうかを正しく判定できる手続きがある場合をいう。

ある言語が計算可枚挙であるとは、計算可能関数 fがあり、単語 wがその言語に属するときだけ ${\displaystyle f($w)} $f(w)$が定義されていることをいう。enumerable という用語の語源は自然数の計算可枚挙な集合の場合と同じである。

例

以下の関数は計算可能関数である。

●定数関数 f : N^k→ N, f(n₁,...n_k) := n

●加法 f : N²→ N, f(n₁,n₂) := n₁+ n₂

●素因数分解関数

●2つの数の最大公約数︵を求めること︶は計算可能関数である。

●ベズーの等式 - 線形ディオファントス方程式

f と gが計算可能ならば、f + g、f * g、$f\circ g$$f\circ g$︵fが単項の場合︶、max(f,g)、min(f,g)などといった様々な組合せも計算可能関数となる。

以下の例では、関数を計算するのがどのアルゴリズムなのかが不明でも、関数が計算可能とされる場合があることを示す。

●πを計算した十進数列に n個の連続した '5' が出現するなら f(n) = 1 を返し、そうでなければ f(n) = 0 を返すような関数 fは、計算可能である。︵この関数は単に定数1を返すか、または、何らかの定数 kについて、n <k なら f(n) = 1 を返し、k ≤ n なら f(n) = 0 を返す。このような関数は全て計算可能である。πの十進表現に '5' が任意の桁数連続して出現する場所があるかは不明なので、﹁どの﹂関数が fなのかを知ることは出来ない。けれども、どれが関数 fだろうとも、それが計算可能であることに変わりは無い訳である︶

●自然数の計算﹁不能﹂な数列︵例えばビジービーバー関数︶の有限な各部分は計算可能である。例えば、有限な数列 Σ(0), Σ(1), Σ(2), …, Σ(n) — を計算するアルゴリズムは存在する。これはΣの数列﹁全体﹂︵つまり全ての nについての Σ(n)︶を計算するアルゴリズムが存在しないことと対照的である。かくして、﹁0, 1, 4, 6, 13 を印字せよ﹂というアルゴリズムは、Σ(0), Σ(1), Σ(2), Σ(3), Σ(4) を計算する問題への自明な答になっている。同様に、全ての nについて、Σ(0), Σ(1), Σ(2), ..., Σ(n) を計算するような自明なアルゴリズムが﹁存在﹂する︵尤も、それが実際に﹁発見﹂されたり書かれたりすることは無いかも知れないが︶。

チャーチ＝チューリングのテーゼ

詳細は「チャーチ＝チューリングのテーゼ」を参照

チャーチ＝チューリングのテーゼは、上述の3つの特性を持つ手続きで計算可能な関数を計算可能関数であると主張したものである。それら3つの特性は形式的に表現できないため、チャーチ＝チューリングのテーゼは証明できない。以下の事実がしばしばこのテーゼの証拠とされる。

●様々な等価な計算模型が知られていて、いずれも計算可能関数の同じ定義を与える︵それらより弱いモデルも存在する︶。

●それらの計算模型より強力なモデルは、これまで提唱︵発見︶されていない。

チャーチ＝チューリングのテーゼは、ある関数が計算可能であることを証明するときに特定の具体的な計算模型で手続きを記述することを正当化するのに使われる。これが許されているのは、︵少なくとも既知の︶どの計算模型であっても記述能力に差がないことが分かっていて、単に様々な記述を省略するためにテーゼを利用していると見なせるからである。

計算不能関数と判定不能問題

あらゆる計算可能関数にはその計算方法を示す有限な手続きが存在するので、計算可能関数は数え上げられるだけの個数しかない。自然数についての有限関数は数え上げられないほど無数にあり、その多くは計算可能ではない。ビジービーバー関数はそのような計算不能な関数の具体例である。

同様に自然数の部分集合の多くは計算可能ではない。チューリングマシンの停止問題はそのような計算不能な集合の例である。ダフィット・ヒルベルトの提唱した Entscheidungsproblem︵決定問題︶は︵自然数で符号化された︶数学的な文が真であるかどうかを決定する実効的な手続きがあるかどうかを問うものであった。これについて1930年代にチューリングとチャーチは個別に決定不能であることを示した。チャーチ＝チューリングのテーゼによれば、そのような計算を行える実効的な手続き︵アルゴリズム︶は存在しない。

計算可能性の拡張

関数の計算可能性は、自然数の任意の集合 Aまたは等価な任意の︵自然数から自然数への︶関数 fについての神託機械で拡張されたチューリングマシン︵あるいは何らかの同等なモデル︶を使って、任意の Aや fに相対化できる。このような関数をそれぞれ、A-計算可能あるいはf-計算可能と呼ぶ。

チャーチ＝チューリングのテーゼは計算可能関数に全てのアルゴリズムのある関数が含まれるとしているが、アルゴリズムが持つべき特性をゆるめた、より広い関数のクラスも定義可能である。Hypercomputation という研究分野では、答を得るまでに無限のステップを実行できる計算可能性記法を研究している。さらに一般化した再帰理論としてE-再帰理論があり、任意の集合をE-再帰関数の引数として使うことができる。

関連項目

• 計算可能数
• 計算理論
• 再帰理論
• チューリング次数
• 算術的階層

参考文献

• Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.
• Rogers, H. Theory of recursive functions and effective computation (McGraw-Hill 1967).
• Turing, A. (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.