再帰理論
再帰理論のこの分野が扱ったのは、次の問題である。0 < m < n であるような定数 m,n があるとする。関数の集合 A があるとして、n 個の任意の異なる入力 x1,x2,...,xn について、少なくとも m 個の等式 A(xk) = yk が真となるように、n 組の数字 y1,y2,...,yn を計算できるだろうか? そのような集合は (m,n)-再帰集合と呼ばれる。再帰理論のこの方面における最初の主要な成果は Trakhtenbrot が得た結果で、それによればある集合が 2m > n であるような m,n について (m,n)-再帰的であるとき、その集合は計算可能である。その一方で、Jockusch の semirecursive 集合(Jockusch が1968年に導入する以前から非形式的には知られていた)は、(m,n)-再帰的である必要十分条件が 2m < n+1 であるような集合の例である。
ここでは学習理論の再帰理論版について触れる。これは Gold が1967年に提出した極限学習モデルを基礎としており(訳注:アルゴリズム的学習理論(en)参照)、以来様々な学習モデルを開発してきた。一般的なシナリオは次の通り。計算可能関数のクラス S があるとする。学習者(と呼ばれる再帰関数)が存在し、(f(0),f(1),...,f(n)) という形をした如何なる入力に対しても結果(仮説と呼ぶ)を一つ出力する。(全ての計算可能関数についての予め取り決めた acceptable ナンバリングに照らして)殆ど全ての仮説が f を指す同じインデクス e であるならば、学習者 M は関数 f を学習したと言い、また M が S 中の全ての f を学習したなら、M は S を学習したと言う。基本的な結果として、全ての帰納的可算な関数のクラスは学習可能だが、全ての計算可能関数のクラス REC は学習不可能である。これまで関連するモデルが数多く考察されてきており、また帰納的可算集合の様々なクラスにおける正例からの学習については Gold の1967年の論文以来研究が続いている。
計算不能な集合の自然な例として、さまざまな形の停止問題を符号化して得られる互いに異なる集合たちがあるが、それらには次のような共通点がある。
それらは帰納的可算集合である。
多対一還元によって互いに変換可能である。すなわち、集合 A と B について、A = {x : f(x) ∈ B} となる計算可能関数 f が存在する。これらの集合を多対一同値(またはm-同値)であるという。
多対一還元はチューリング還元より強い。計算不能集合の自然な例は全て多対一同値だが、A を B にチューリング還元可能だが多対一還元不可能な帰納的可算集合 A と B を構築することもできる。すべての帰納的可算集合は停止問題に多対一還元可能であることが判っているので、多対一還元とチューリング還元の観点で、停止問題は最も複雑な帰納的可算集合である。1944年、ポストは、すべての帰納的可算集合は計算可能かあるいは停止問題にチューリング同値かのいずれかだろうか、という疑問を投げかけた。つまり、チューリング次数がこの2つの間になるような帰納的可算集合は存在するか、という問いである。
その問題を考える過程で、ポストは帰納的可算集合の分類として単純集合/超単純集合/超々単純集合といった自然な型を定義した。ポストはこれらの集合が、多対一還元の観点から見たとき、計算可能集合と停止問題の厳密に中間に位置することを示した。ポストはまた、チューリング還元よりも強い意味の還元(真理値表還元)を用いた場合においても、それらの一部が厳密に中間に位置することを示した。