計算可能関数
関数の計算可能性は、自然数の任意の集合 A または等価な任意の(自然数から自然数への)関数 f についての神託機械で拡張されたチューリングマシン(あるいは何らかの同等なモデル)を使って、任意の A や f に相対化できる。このような関数をそれぞれ、A-計算可能あるいはf-計算可能と呼ぶ。
チャーチ=チューリングのテーゼは計算可能関数に全てのアルゴリズムのある関数が含まれるとしているが、アルゴリズムが持つべき特性をゆるめた、より広い関数のクラスも定義可能である。Hypercomputation という研究分野では、答を得るまでに無限のステップを実行できる計算可能性記法を研究している。さらに一般化した再帰理論としてE-再帰理論があり、任意の集合をE-再帰関数の引数として使うことができる。
チャーチ=チューリングのテーゼは、上述の3つの特性を持つ手続きで計算可能な関数を計算可能関数であると主張したものである。それら3つの特性は形式的に表現できないため、チャーチ=チューリングのテーゼは証明できない。以下の事実がしばしばこのテーゼの証拠とされる。
様々な等価な計算模型が知られていて、いずれも計算可能関数の同じ定義を与える(それらより弱いモデルも存在する)。
それらの計算模型より強力なモデルは、これまで提唱(発見)されていない。
チャーチ=チューリングのテーゼは、ある関数が計算可能であることを証明するときに特定の具体的な計算模型で手続きを記述することを正当化するのに使われる。これが許されているのは、(少なくとも既知の)どの計算模型であっても記述能力に差がないことが分かっていて、単に様々な記述を省略するためにテーゼを利用していると見なせるからである。