再帰理論

再帰理論（さいきりろん、英: Recursion theory）は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や effective 記述集合論(en)とも密接に関係する。
再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。
数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。

チューリング計算可能性

再帰理論における計算可能性の研究はチューリング（1936）に端を発している。自然数の集合と自然数 n を考える。n がその集合の元なら 1 を返して停止し、そうでないなら 0 を返して停止するチューリングマシンが存在するなら、その集合は帰納的集合（または、決定可能集合、計算可能集合、チューリング計算可能集合とも）と呼ばれる。自然数から自然数への関数 f があるとする。任意の自然数 n を入力されたときに f(n) を出力して停止するチューリングマシンが存在するとき、その関数を再帰関数あるいは（チューリング）計算可能関数と呼ぶ。ここでは定義に必ずしもチューリングマシンを持ち出す必要はない。チューリングマシンと同等の能力を持つ計算模型は他にも存在する（例えば、原始再帰関数とμ作用素からなるμ再帰関数）。
再帰関数と集合に関する用語は完全に一定しているわけではない。μ再帰関数による定義や、ゲーデルによる rekursiv（再帰）関数の定義から、伝統的に「再帰的; recursive」という言葉でチューリングマシンで計算可能な集合や関数を意味するようになった。「決定可能; decidable」という用語はチューリングらが論文で使っていたドイツ語 Entscheidungsproblem に由来する。現在では「計算可能関数; computable function」という用語には様々な定義がある。Cutland（1980）によればそれは部分再帰関数（入力値によっては動作が未定義となる関数）を意味し、Soare（1987）によれば、それは全域再帰関数（一般再帰関数）を意味する。この記事では後者の意味で用いる。Soare（1996）には、他にも用語についてのコメントがある。
自然数の集合は常に計算可能という訳ではない。チューリングマシンの停止問題は、0を入力したとき停止するチューリングマシン（についての記述）の集合だが、計算不可能な集合のよく知られた例である。計算不可能な集合が多数存在することは、次の事実から明らかである。つまり、チューリングマシンは枚挙可能（可算）な個数しか存在しないから、計算可能集合も枚挙可能な個数しか存在しないが、自然数から作る集合は枚挙不可能（非可算）な数だけ存在する。
停止問題は計算可能ではないが、プログラムの実行をシミュレートし、実際に停止するプログラムの無限のリストを作成することは可能である。すなわち、停止問題は帰納的可算集合（計算枚挙可能、半決定可能などとも）の例であり、チューリングマシンによって枚挙可能な集合である。同様に、ある集合が帰納的可算であることの必要十分条件は、それが空であるか、または何らかの計算可能関数の値域に等しいことである。帰納的可算集合は一般には決定不能だが、再帰理論が最も詳しく研究してきた領域である。

再帰理論の研究領域

上述のような再帰的な集合や関数の理論を出発点として、再帰理論は関連する主題を巻き込んで成長してきた。以下に挙げるのはそれぞれ独立した研究分野というわけではない。各分野は結果や考え方を相互に応用しており、再帰理論の研究者であればこれらの大半に親しんでいる。

ライスの定理と算術的階層

ライスの定理は、すべての自明でないクラス C（帰納的可算集合からなるクラスであって空でも全体でもないもの）において、インデックス集合 E = {e: e番目の帰納的可算集合 Wₑ が C に含まれる} を考えると、停止問題かその補問題が E に多対一還元可能という属性を持つことを示す。しかし、このようなインデックス集合の多くは停止問題以上に複雑である。このような集合は算術的階層によって分類される。例えば、すべての有限集合のクラスのインデックス集合 FIN の階層レベルは Σ₂、すべての帰納的集合のクラスのインデックス集合 REC の階層レベルは Σ₃、すべての補有限集合のクラスのインデックス集合 COFIN の階層レベルは Σ₃、すべてのチューリング完全な集合のクラスのインデックス集合 COMP の階層レベルは Σ₄ である。

逆数学

逆数学のプログラムは、二階算術の中の部分体系において、ある定理を証明するのにどの程度の集合存在公理が必要かを問うものである。この研究は Harvey Friedman が創始し、Stephen Simpson らが進めた。Simpson（1999）で、これに関する詳細が議論されている。対象となる集合存在公理は、自然数のべき集合が様々な還元可能性の概念の下で閉じていることを言う公理群とほぼ対応している。逆数学で研究されているそのような公理の中で最も弱いものは「再帰的内包公理; Recursive Comprehension Axiom」であり、これは自然数のべき集合はチューリング還元可能性の下で閉じているとするものである。

ナンバリング

ナンバリングとは関数や集合に対する番号付けである。より一般には自然数の集合から集合  への全射を  のナンバリングという。
 が関数や集合からなる集合である場合には、 のナンバリングの計算可能性・実効性を考えることができる。例えば  が帰納的可算集合からなる集合のとき、 のナンバリング  が計算可能であるとは、述語  が帰納的可算であることをいう。また  が計算可能（部分）関数からなる集合のとき、 のナンバリング  が計算可能であるとは、部分関数  が計算可能であることをいう。
ナンバリングの間には「計算可能関数によって変換できるか」によって擬順序を定めることができる。正確には、ナンバリング  が  に還元可能であるということを、計算可能関数  が存在して  が成り立つことと定める。この還元可能性に関してナンバリングの全体は擬順序集合を成す。とくに計算可能ナンバリングの全体について半順序反映を取ったものをRogers半束という。名前の通りRogers半束は（空でなければ）上半束の構造を成す。
ある計算可能なナンバリングが存在し、そのナンバリングを他のあらゆる計算可能なナンバリングへ変換できる（計算可能ナンバリングの中で還元可能性の意味で最大元となっている）とき、これを acceptable ナンバリングまたはゲーデル数化と言う。Friedberg ナンバリング（発見者の名に因む）は計算可能な一対一ナンバリングである。Friedberg ナンバリングは極小元である（Pour-El: 1964）。したがって、ロジャース半束が自明な場合を除けば、Friedberg ナンバリングは acceptable ナンバリングではない。
Goncharov はある帰納的可算集合のクラスを発見し、そのナンバリングの全体が再帰同型の観点から見て正確に二つのクラスに分類されることを示した。すなわち、そのクラスのRogers半束の濃度が2であることを証明した。

優先度法

ポストの問題は優先度法という技法を用いて解決された。この技法を用いる証明は優先度論法と呼ばれる。これは第一義的には特別な性質を備えた帰納的可算集合を構成することを目的とする。やり方としては、まずその帰納的可算集合が備えるべき性質を無限個の「要件」に分解し、全ての要件を満足すれば目的の集合は自ずと所期の性質を獲得する、という形を作る。個々の要件には優先度を表す自然数を付与しておく。0 を付与された要件が最優先で、以下 1、2 …という具合である。以後、目的の集合を「段階」を踏んで構築して行く。個々の段階は、一つ以上の要件を満たすように、目的の集合に対して数を追加または削除することから成る。一つの要件を満たすと他の要件に反してしまう場合が有り得るが、その際は優先度を参照して処理方法を決定する。
これまで優先度論法を用いて再帰理論の様々な問題が解決されてきており、それらは複雑さの観点から階層状に分類されている(Soare 1987)。複雑な優先度論法はテクニカルかつ難解になりがちなので、伝統的に出来れば優先度論法は使わずに証明することが望ましいとされ、また優先度論法を用いた証明があればそれ抜きの別証明が模索されてきた。例えば Kummer は Friedberg ナンバリングの存在証明について優先度法を用いない証明を発表した（Kummer 1989, 1990）。

帰納的可算集合の束(lattice)

ポストは単純集合（「無限帰納的可算集合を一つも含まないような無限補集合」を持つ帰納的可算集合）を定義し、そこから帰納的可算集合同士の包含関係を研究し始めた。この束 (lattice) は今日では詳細に研究された構造となっている。ある集合が帰納的である必要十分条件は、集合とその補集合が共に帰納的可算であることである。この基本的な結果を用いて、この構造内に帰納的集合を定義できる。無限帰納的可算集合は常に無限帰納的集合を部分集合として持つのに対し、単純集合は余無限 (coinfinite) な帰納的集合を上位集合として持たない。ポスト(1944)は既に超単純集合と超々単純集合を導入していた。後に極大集合 (maximal set) が構成されたが、これは帰納的可算である全ての上位集合が所与の極大集合の有限な変種かまたは余有限 (co-finite) であるような帰納的可算集合である。ポストがこの束を研究した元々の動機は、この性質を満たす全ての集合のチューリング次数が、帰納的集合と停止問題の何れのチューリング次数とも異なるということを構造的に示せないかという点にあった。ポストはそのような性質を見出すことはできず、彼の問題は代わりに優先度法を用いて解決されたが、Harrington と Soare (1991) はそのような性質をついに発見した。

保型性問題

もう一つの重要な問題は再帰理論の構造物における保型性の存在である。このような構造の一つとして、有限な差を除いて包含関係が成り立つような帰納的可算集合同士の関係がある。この構造においては、A が B に含まれる必要十分条件は差集合 B - A が有限であることである。（前節で定義したような）極大集合は、非極大集合に対して保型的にはなれないという性質がある。つまり、今しがた述べたような構造の下で帰納的可算集合に保型性が存在するのなら、如何なる極大集合も他の極大集合に写像できる。Soare (1974) はこの逆も成り立つこと、即ち任意の二つの極大集合は保型的であることを示した。従って極大集合は軌道を成す。つまり全ての保型性は自ずと極大性を保ち、如何なる二つの極大集合も何らかの保型性によって互いに変換し合うことができる。その他の例として、Harrington が得た停止問題に多対一同値な creative 集合(en)も、保型的な性質を有する。
帰納的可算集合の束論の傍らで、全ての集合のチューリング次数の構造や或いは帰納的可算集合のチューリング次数の構造についても、保型性は研究されている。何れについても、Cooper は幾つかの次数を他の次数に写像するような自明でない保型性を構成したと主張している。しかしながらこの構成法は確かめられておらず、一部の研究者によると誤りがあり、従ってチューリング次数に自明でない保型性が存在するか否かは依然としてこの分野の主たる未解決問題の一つだという (Slaman and Woodin 1986, Ambos-Spies and Fejer 2006)。

コルモゴロフ複雑性

コルモゴロフ複雑性とアルゴリズム的無作為性の分野は、1960年代から1970年代にかけてチャイティン、コルモゴロフ、Levin、Martin-Löf、Solomonof らが開拓した。中心となる考え方は、万能チューリング機械 U があるとき、数（あるいは文字列）x の複雑性を x が出力となるような U(p) の最短の入力 p の長さで表すというものである。これにより、無限の数列（自然数の部分集合を与える特性関数と等価）が無作為か否かの判定を、有限のオブジェクト群の無作為性から導くことができるようになった。コルモゴロフ複雑性は独立した研究分野というだけでなく、他の分野での証明に応用されるようになっている。未解決の問題も多く残されている。最近でも、2007年1月にこの分野に関する国際会議が開催され、未解決の問題の一覧が Joseph Miller と Andre Nies によって示された。

頻度計算

再帰理論のこの分野が扱ったのは、次の問題である。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 であるような集合の例である。このような集合は非可算個存在し、また帰納的可算だが計算不可能な集合でこの性質を持つものも存在する。後に Degtev は (1,n+1)-再帰的だが (1,n)-再帰的ではないような帰納的可算集合を階層状に分類した。ロシア人の科学者達による研究が長年続いた後、この話題は Beigel の限定付きクエリ (bounded queries) に関する命題によって再び注目を集めた。Beigel の命題は頻度計算と上に述べた限定付き還元可能性や他の関連概念を結び付けた。主な結果の一つとして Kummer の濃度理論がある。それによれば集合 A が計算可能となる必要十分条件は次の性質を満たす n が存在することである。即ち何らかのアルゴリズムを用いて、n 個の異なる数字から成る組について、この n 個の数字の集合と A との積集合が取り得る濃度の候補を n 種類まで数え上げることができる（これらの候補は正しい濃度を必ず含むが、少なくとも一つは間違った濃度が混ざる）。

帰納的推論

ここでは学習理論の再帰理論版について触れる。これは Gold が1967年に提出した極限学習モデルを基礎としており(訳注：アルゴリズム的学習理論(en)参照)、以来様々な学習モデルを開発してきた。一般的なシナリオは次の通り。計算可能関数のクラス S があるとする。学習者（と呼ばれる再帰関数）が存在し、(f(0),f(1),...,f(n)) という形をした如何なる入力に対しても結果（仮説と呼ぶ）を一つ出力する。（全ての計算可能関数についての予め取り決めた acceptable ナンバリングに照らして）殆ど全ての仮説が f を指す同じインデクス e であるならば、学習者 M は関数 f を学習したと言い、また M が S 中の全ての f を学習したなら、M は S を学習したと言う。基本的な結果として、全ての帰納的可算な関数のクラスは学習可能だが、全ての計算可能関数のクラス REC は学習不可能である。これまで関連するモデルが数多く考察されてきており、また帰納的可算集合の様々なクラスにおける正例からの学習については Gold の1967年の論文以来研究が続いている。

チューリング計算可能性の一般化

Sacks (1990) が述べたように、再帰理論ではこの分野の一般化である算術的還元可能性、超算術的還元可能性、α-再帰理論なども研究されている。これらの一般化された概念の中には、チューリングマシンでは実行不能にも関わらず、それでもなおチューリング還元可能性の自然な一般化と看做せるような還元可能性が存在する。これらの研究には解析的階層を調べるためのアプローチが各種含まれる。解析的階層と算術的階層の違いは、個々の数の量化に加えて自然数の集合の量化を認める点にある。これらの領域は整列順序や木の理論と関係している。例えば再帰的な（二分木でない）木が無限の分岐を持たない場合、その全てのインデクスの集合は解析的階層のレベル  について完全である。effective 記述集合論の分野ではチューリング還元可能性と超算術的還元可能性は共に重要である。集合論では構成可能性の次数という更に強力な概念についても研究されている。

定義可能性、証明、計算可能性の相互関係

自然数の集合のチューリング次数と、一階述語論理を用いてその集合を定義する（算術的階層から見た）困難さの間には、密接な関係がある。そのような関係性を正確に示す一例がポストの定理である。より弱い関係性として、例えばクルト・ゲーデルが不完全性定理の証明の中で示した例がある。ゲーデルの証明は、実効的な一階理論の論理的結果の集合は帰納的可算集合を成すこと、そしてもしその理論が十分強いならこの集合は計算不可能になることを示している。同様に、タルスキの定義不可能性定理(en)は定義可能性と計算可能性の両方の言葉で解釈することができる。
再帰理論は二階算術（自然数と自然数の集合に関する形式的理論）とも関係している。特定の集合が計算可能だったり相対的に計算可能だったりする場合、それらの集合は二階算術の中の弱い体系内で定義できることがよくある。逆数学の研究プログラムは、よく知られた数学的定理に内在する計算不可能性を測る尺度としてこれらの体系を用いる。Simpson (1999) は二階算術と逆数学に関する様々な話題を取り上げている。
証明論の分野の研究対象には、二階算術とペアノ算術の他にも、ペアノ算術よりも弱い自然数に関する形式的体系などがある。これらの弱い体系の強さを分類する一つの方法として、それらの体系の中で「どの計算可能関数が全域関数であると証明できるか」による特徴付けがある (Fairtlough and Wainer (1998)を参照されたい)。例えば、原始帰納的算術において全域関数であることが証明可能な計算可能関数は原始帰納的なものに限られるが、ペアノ算術ではアッカーマン関数のような原始帰納的でない関数が全域関数であることを証明できる。とはいえペアノ算術でも全ての計算可能関数が全域関数と証明できる訳ではない。そのような関数としてはグッドスタインの定理から得られる例がある。

名称問題

数理論理学において、計算可能性とその一般化を研究する分野は、「再帰理論」と呼ばれてきた。Robert I. Soare は1996年、これを「計算可能性理論; computability theory」と呼ぶことを提案した。彼は、クリーネの「再帰; recursive」という用語よりもチューリングの「計算可能; computable」という用語の方が自然で判り易いと主張している。そのため、近年では計算可能性理論と呼ぶ研究者が増えている。同時に「部分計算可能関数」や「計算可枚挙」といった用語が、「部分再帰関数」や「帰納的可算」といった用語の代わりとして使われるようになっている。しかし、Fortnow や Simpson のようにまだ納得していない研究者もいる。また、「再帰理論」にしても「計算可能性理論」にしても、研究対象のほとんどが計算可能でないことを表せていない点を指摘する人もいる。さらに、Osherson は帰納的推論における「学習者; learner」という用語を「科学者; scientist」に代えることを提案し、著書 Systems that learn を改版するときに、そのように用語を変更した。
Rogers (1967) は、再帰理論の鍵となる特性は、その結果や構造が自然数への計算可能な全単射において不変である点だとした。すなわち、計算可能な全単射では集合の各要素を単に改名するだけで、その構造は変化させない。ユークリッド平面での回転が幾何学的形状を変化させないのと同じである。2つの無限の計算可能集合は計算可能な全単射でリンクされるので、これは全ての無限な計算可能集合に当てはまる（有限の計算可能集合については自明である）。Rogers によれば、再帰理論が対象とする集合は、計算可能な全単射で自然数と対応できるような計算不可能集合である。

学術団体

再帰理論を扱う国際的学術団体として記号論理学会（Association for Symbolic Logic）がある。同学会は毎年、学術会議をいくつか開催している。