計算可能関数 (Computable function) とは、「(計算機やアルゴリズムによって)計算できる」関数である。チャーチ=チューリングのテーゼの下で、これは帰納的関数に同一視される。
概要
数学やその応用分野の問題を解くにあたり、わたしたちは自然にアルゴリズムやそれに類似の操作を行っている。例えば、与えられた自然数が素数かどうかを調べるには2から順に自然数で割っていけば確認ができるだろう。お金を持っていれば、然るべき手順に沿った後に食べ物や飲み物を買うことができるだろう。アッカーマン関数で\(A(10,10)\)がいくつになるかですら、定義に沿って計算すればいつかは計算できるだろう(先に宇宙が終わるかもしれないが)。
定義を持たない観念としての「計算できる」という語は古くから使われてきており、その内容を吟味すればおおむね以下の内容で語られるだろう。あるメソッド、あるいは手順やアルゴリズムである M が "effective" あるいは "mechanical" であるとは、以下の条件を満たすようなことである[1]：
- Mは有限個の指示(instructions)として提示されており、それぞれの指示は有限個の記号で表現されている(各指示が無限長であったりなどはしない)。
- エラーを起こさない限り、Mは必ず求められた結果を有限個の段階数のうちに出力する。
- Mは原則的に、機械を使うことなく、紙とペンによってわれわれ人間に実行可能である(作業効率とかは無視するものとして)。
- Mは人間の洞察力や発見等を必要としていない。
「計算可能である」ということがどのようなことであるか、数学の言葉でどのように特徴づけられるか、ということを探す試みは20世紀の初頭に行われた。これを「計算可能関数とは帰納的関数のことである」とした主張が'チャーチ=チューリングのテーゼ (Church–Turing thesis) である。
チャーチ=チューリングのテーゼは数学的に示された定理ではない。しかし、多くの現実的な計算モデル、例えば、チューリング機械、レジスター機械、型なしラムダ計算などで計算可能である関数は帰納的関数と一致することが知られている。現在ではこの性質をチューリング完全性 (Turing completeness) といいプログラミング言語などのチューリング完全性が知られている。このような経験則から計算可能関数は帰納的関数であるというチャーチ=チューリングのテーゼに疑いを持つものは少ないと思われる。
以下では計算可能性関数をチューリング計算可能関数（これは先程のべたように帰納的関数と一致する）として、具体的な定義とそのための構成を与える：
チューリングマシンによる説明
2色チューリングマシン \(T\) を仮定する。正の整数 \(n\) が与えられたとき、チューリングマシンのヘッドが位置するテープの左端のマスから \(n\) マスだけ続くマスを除いて、テープを空白に設定する。チューリンブマシンをシミュレーションすると次のようなことが起こる。
- ヘッドが左端にあり、テープ上に \(m \in \mathbb{N}\) マスだけ空白でない色が続いた状態で停止する。この場合、\(T\) が \(n\) を入力されて \(m\) を出力したと言うことができる。
- 停止するが、上のように描写される構成にはならない。
- 停止しない。
\(f\) を \(T\) が \(n\) を入力されたら \(m\) を返すようなすべての順序対 \((m,n)\) からなる集合とする。すると、\(f\) を \(\mathbb{N}\) を定義域と終域にもつ部分関数 (partial function) と見なすことができる。このとき \(T\) が \(f\) を計算する (compute) と言うことができ、そして部分計算可能関数 (partial computable function) (または 部分再帰関数 (partial recursive function) ) とはそれを計算するチューリングマシンが存在する部分関数である。
計算可能関数 (computable function) (または再帰関数，再帰的関数 (recursive function)) とは完全な部分計算可能関数である。つまり、計算可能関数とはチューリングマシンで計算できる関数であり、計算できない関数 \(f: \mathbb{N} \rightarrow \mathbb{N}\) は計算不可能と呼ばれる。
計算不可能関数は (遠まわしに) 計算不可能なほどに急増加する関数、すなわち、すべての計算可能な関数を支配する関数を意味している場合がある。そのような関数のもっとも有名な例としてビジービーバー関数がある。そのような関数は計算不可能で、並はずれて速く成長し、 FGH に関して \(\omega_1^\text{CK}\) (チャーチ・クリーネ順序数)未満のいかなる順序数に再帰的基本列系を定めたものより強く、一方で \(\omega_1^\text{CK}\) に適切な基本列系を定めたもので支配される。すべての計算不可能関数がこのような性質をもつわけではないことに注意することは重要である、たとえば、チューリングマシンを並べる方法を定めた上で \(n\) 番目のチューリングマシンが停止するときには \(1\) を返し、そうでなければ \(0\) を返す関数 \(h(n)\) は計算不可能であるが急増加はしない。
ほとんどすべての自然数上の関数は計算不可能関数である。なぜならば、計算可能関数の集合は可算であるが、計算不可能関数の集合は非可算となるためである。
計算可能関数の性質
定理: 計算可能関数の集合は合成に関して閉じている。
証明: 計算可能関数 \(f\) と \(g\) が与えられたときに、 \(g \circ f\) が計算可能であることを示す。\(S\) を \(f\) を計算するチューリングマシン \(T\) を \(g\) を計算するチューリングマシンとし、それぞれの状態は互いに重ならないとする。\(Q_S\) を \(S\) の状態、\(q_{S0}\) を初期状態、 \(q_{SH}\) を停止状態、\(\delta_S\) を遷移関数とし、 \(T\) についても同様のものを用意する。次のようなチューリングマシン \(S \circ T\) を定義する。
- \(Q_{S \circ T} = (Q_S \backslash q_{SH}) \cup Q_T\)
- \(q_{S \circ T,0} = q_{S0}\)
- \(q_{S \circ T,H} = q_{TH}\)
- \(\delta_{S \circ T} = \delta_S' \cup \delta_T\) 、 \(\delta_S'\) は \(\delta_S\) の中にある \(q_{SH}\) の状態を \(q_{T0}\) に置き換えたもの。
- \(Q_{S \circ T} \leadsto Q_{q_{SN} \delta^{\beta}}\) for \(N\) does not \( >^*S\) and \(\beta\) is computable. よって全体のシーケンスは計算可能である。
実際、このチューリングマシンは \(f\) を計算したうえで \(g\) を計算するため、表現される計算可能関数は \(g \circ f\) となる。よって \(g \circ f\) は計算可能である。
計算不可能関数の例
現在、計算不可能なほどに急増加する関数の多くはビジービーバー関数あるいはラヨ関数を元としている。
参考文献
- ↑ Copeland, B.J.; Copeland, Jack; Proudfoot, Diane (June 2000). "The Turing-Church Thesis". AlanTuring.net. Turing Archive for the History of Computing. Retrieved 23 March 2013.