このような関数は全て計算可能である。それが計算可能であることに変わりは無い訳である)自然数の計算「不能」な数列(例えばビジービーバー関数)の有限な各部分は計算可能である。計算するアルゴリズムは存在する。Σ(n))を計算するアルゴリズムが存在しないことと対照的である。計算する問題への自明な答になっている。計算するような自明なアルゴリズムが「存在」する(尤も、それが実際に「発見」されたり書かれたりすることは無いかも知れないが)。チャーチ=チューリングのテーゼ[編集]詳細は「チャーチ=チューリングのテーゼ」を参照チャーチ=チューリングのテーゼは、上述の3つの特性を持つ手続きで計算可能な関数を計算可能関数であると主張したものである。それら3つの特性は形式的に表現できないため、チャーチ=チューリングのテーゼは証明できない。以下の事実がしばしばこのテーゼの証拠とされる。様々な等価な計算模型が知られていて、いずれも計算可能関数の同じ定義を与える(それらより弱いモデルも存在する)。それらの計算模型より強力なモデルは、これまで提唱(発見)されていない。チャーチ=チューリングのテーゼは、ある関数が計算可能であることを証明するときに特定の具体的な計算模型で手続きを記述することを正当化するのに使われる。これが許されているのは、(少なくとも既知の)どの計算模型であっても記述能力に差がないことが分かっていて、単に様々な記述を省略するためにテーゼを利用していると見なせるからである。計算不能関数と判定不能問題[編集]あらゆる計算可能関数にはその計算方法を示す有限な手続きが存在するので、計算可能関数は数え上げられるだけの個数しかない。自然数についての有限関数は数え上げられないほど無数にあり、その多くは計算可能ではない。ビジービーバー関数はそのような計算不能な関数の具体例である。同様に自然数の部分集合の多くは計算可能ではない。チューリングマシンの停止問題はそのような計算不能な集合の例である。Entscheidungsproblem(決定問題)は(自然数で符号化された)数学的な文が真であるかどうかを決定する実効的な手続きがあるかどうかを問うものであった。これについて1930年代にチューリングとチャーチは個別に決定不能であることを示した。チャーチ=チューリングのテーゼによれば、そのような計算を行える実効的な手続き(アルゴリズム)は存在しない。このような関数をそれぞれ、A-計算可能あるいはf-計算可能と呼ぶ。チャーチ=チューリングのテーゼは計算可能関数に全てのアルゴリズムのある関数が含まれるとしているが、アルゴリズムが持つべき特性をゆるめた、より広い関数のクラスも定義可能である。いう研究分野では、答を得るまでに無限のステップを実行できる計算可能性記法を研究している。一般化した再帰理論としてE-再帰理論があり、任意の集合をE-再帰関数の引数として使うことができる。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。開発者Cookieに関する声明モバイルビュ。