計算可能性の拡張
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/02/29 16:21 UTC 版)
関数の計算可能性は、自然数の任意の集合 A または等価な任意の（自然数から自然数への）関数 f についての神託機械で拡張されたチューリングマシン（あるいは何らかの同等なモデル）を使って、任意の A や f に相対化できる。このような関数をそれぞれ、A-計算可能あるいはf-計算可能と呼ぶ。 チャーチ＝チューリングのテーゼは計算可能関数に全てのアルゴリズムのある関数が含まれるとしているが、アルゴリズムが持つべき特性をゆるめた、より広い関数のクラスも定義可能である。Hypercomputation という研究分野では、答を得るまでに無限のステップを実行できる計算可能性記法を研究している。さらに一般化した再帰理論としてE-再帰理論があり、任意の集合をE-再帰関数の引数として使うことができる。
※この「計算可能性の拡張」の解説は、「計算可能関数」の解説の一部です。
「計算可能性の拡張」を含む「計算可能関数」の記事については、「計算可能関数」の概要を参照ください。
ウィキペディア小見出し辞書の「計算可能性の拡張」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算可能性の拡張のページへのリンク
