計算可能関数の特性

ウィキペディア小見出し辞書

計算可能関数の特性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/02/29 16:21 UTC 版)

「計算可能関数」の記事における「計算可能関数の特性」の解説

詳細は「アルゴリズム」を参照 計算可能関数の基本特性は、その関数の計算方法を示す有限の手続き（アルゴリズム）が必ず存在するということである。上記の計算模型は、そのような手続きの表現手法であるが、それらの間で多くの特性が共有されている。これらの計算模型が計算可能関数の等価なクラスを与えるということは、ある計算模型を使って別の計算模型の手続きを擬似できることを意味し、これはちょうどコンパイラがある言語から別の言語に変換するのと同じことである。 Enderton [1997] では計算可能関数の計算手続きの特性を次のように表している。同様の考え方は、Turing [1936]、Rogers [1967]、などでも示されている。 「その手続きには、有限長の明確な命令列（すなわちプログラム）がなければならない」 従って、全ての計算可能関数には必ず有限長の完全なプログラムがあり、その関数をどう計算すべきかが示される。その関数を計算するには、単にその命令列を実行すればよく、何かを推測したり、前提となる知識に頼ったりすることはない。 「その手続きに f の定義域にある k-タプル x が与えられるとき、有限個の離散ステップを実行後にその手続きは完了し、f(x) を生成する」 直観的に、手続きは逐次的に進行し、各ステップで何をすべきかは命令（規則）で示される。有限個のステップの実行によって関数の値が返される。 「その手続きに f の定義域にない k-タプル x が与えられるとき、手続きは永久に続き、停止しない可能性がある。あるいはある時点で停止したとしても、x についての f の値を返さない」 従って、f(x) の値が見つかった場合、その値は正しい。手続きが値を返すとき、その値は常に正しいので、受け取った側がそれが正しいか間違っているかを判断する必要はない。 Enderton はさらに計算可能関数の手続きの満たすべき条件を以下のように挙げている。 手続きは任意の大きさの引数を扱えなければならない。例えば、引数が地球上にある原子数より小さいというような前提はない。 手続きは出力を生成するまでに有限個のステップを実施して停止する必要があるが、そのステップ数は非常に大きくなる可能性がある。時間制限は特にない。 手続きは値を返す場合には有限の空間（領域）を使って計算するが、使用する空間の量に制限はない。手続きが必要とするだけの空間（記憶領域）が与えられるものとされる。 計算複雑性理論では、計算に必要な時間や空間に何らかの前提を設けて関数を研究する。