再帰理論
再帰理論(さいきりろん、英:Recursion theory)は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。
発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や エフェクティブ記述集合論(en)とも密接に関係する。
再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。
数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。
このような集合は非可算個存在し、また帰納的可算だが計算不可能な集合でこの性質を持つものも存在する。後に Degtev は (1,n+1)-再帰的だが (1,n)-再帰的ではないような帰納的可算集合を階層状に分類した。ロシア人の科学者達による研究が長年続いた後、この話題は Beigel の限定付きクエリ (bounded queries) に関する命題によって再び注目を集めた。Beigel の命題は頻度計算と上に述べた限定付き還元可能性や他の関連概念を結び付けた。主な結果の一つとして Kummer の濃度理論がある。それによれば集合 A が計算可能となる必要十分条件は次の性質を満たす n が存在することである。即ち何らかのアルゴリズムを用いて、n 個の異なる数字から成る組について、この n 個の数字の集合と A との積集合が取り得る濃度の候補を n 種類まで数え上げることができる(これらの候補は正しい濃度を必ず含むが、少なくとも一つは間違った濃度が混ざる)。