再帰理論

再帰理論（さいきりろん、英：Recursion theory）は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。

発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や エフェクティブ記述集合論(en)とも密接に関係する。

再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。

数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。

計算可能集合と計算不可能集合

再帰理論は、1930年代のクルト・ゲーデル、アロンゾ・チャーチ、アラン・チューリング、スティーヴン・コール・クリーネ、エミール・ポストらの研究に端を発している。

彼らの基本的な成果を通じて、チューリング計算可能性という概念が樹立された。これは計算の実効性という非形式的な概念に正しい形式化を与えるものである。そこからスティーヴン・クリーネ（1952年）は、「チャーチのテーゼ」（Kleene 1952:300）と「チューリングのテーゼ」（p.376）という2つの用語を作った。現在では、これらはしばしばチャーチ＝チューリングのテーゼという一つの仮説と看做されているが、これはアルゴリズムで計算可能な関数は如何なるものであろうと計算可能関数だ、と述べるものである。当初は懐疑的だったゲーデルも、1946年には賛同を示した。

「タルスキは彼の講義において、一般再帰性（またはチューリング計算可能性）が大変重要だと強調したが、これは正しいと思う。これが何故重要かと言えば、この考え方によって人が初めて、ある興味深い認識論的観念について、（特定の形式主義に囚われない様な）絶対的な観念を与えることに成功したから、という理由が大だと私には思える」（Gödel 1946 in Davis 1965: 84）

実効的な計算というものの定義に伴い、数学には実効的に決定できない問題があることを示す最初の一連の証明が得られた。チャーチ（1936a、1936b）とチューリング（1936）はゲーデルの不完全性定理の証明（1931）で用いられた技法に触発され、それぞれ独立に、ダフィット・ヒルベルトが1928年に提示した Entscheidungsproblem（決定問題）(en)が実効的に決定できないことを示した。この結果は、任意の数学的命題が真か偽かを正しく判定するアルゴリズムが存在しないことを明らかにした。

これらの初期の例に続いて、多くの数学問題が決定不能であることが示された。1947年、Markov とポストはそれぞれ独立に半群の word problem が実効的に決定できないことを示す論文を発表した。その結果に基づき、1950年代、Pyotr Sergeyevich Novikov (en)と William Boone はそれぞれ独立に群の word problem (en)が実効的に解けないことを示した。これは有限に表現された群におけるある語（word）が与えられたとき、その語が指す元がその群の単位元かどうかを実効的に決定する手続きが存在しないということである。1970年、ユーリ・マチャセビッチはマチャセビッチの定理(en)を証明し、その系としてヒルベルトの第10問題が実効的な解法を持たないことを示した。この問題は整数上で定義されたディオファントス方程式が整数解を持つかどうかを判定する手続きを求めるものであった。

何らかの数学的行為が実効的に実行できるかを問う研究は、ときに再帰数学と呼ばれることがある。Handbook of Recursive Mathematics (Ershov他、1998)はこの分野の成果を多数紹介している。

チューリング計算可能性

再帰理論における計算可能性の研究はチューリング（1936）に端を発している。自然数の集合と自然数 n を考える。n がその集合の元なら 1 を返して停止し、そうでないなら 0 を返して停止するチューリングマシンが存在するなら、その集合は帰納的集合（または、決定可能集合、計算可能集合、チューリング計算可能集合とも）と呼ばれる。自然数から自然数への関数 f があるとする。任意の自然数 n を入力されたときに f(n) を出力して停止するチューリングマシンが存在するとき、その関数を再帰関数あるいは（チューリング）計算可能関数と呼ぶ。ここでは定義に必ずしもチューリングマシンを持ち出す必要はない。チューリングマシンと同等の能力を持つ計算模型は他にも存在する（例えば、原始再帰関数とμ作用素からなるμ再帰関数）。

再帰関数と集合に関する用語は完全に一定しているわけではない。μ再帰関数による定義や、ゲーデルによる rekursiv（再帰）関数の定義から、伝統的に「再帰的; recursive」という言葉でチューリングマシンで計算可能な集合や関数を意味するようになった。「決定可能; decidable」という用語はチューリングらが論文で使っていたドイツ語 Entscheidungsproblem に由来する。現在では「計算可能関数; computable function」という用語には様々な定義がある。Cutland（1980）によればそれは部分再帰関数（入力値によっては動作が未定義となる関数）を意味し、Soare（1987）によれば、それは全域再帰関数（一般再帰関数）を意味する。この記事では後者の意味で用いる。Soare（1996）には、他にも用語についてのコメントがある。

自然数の集合は常に計算可能という訳ではない。チューリングマシンの停止問題は、0を入力したとき停止するチューリングマシン（についての記述）の集合だが、計算不可能な集合のよく知られた例である。計算不可能な集合が多数存在することは、次の事実から明らかである。つまり、チューリングマシンは枚挙可能（可算）な個数しか存在しないから、計算可能集合も枚挙可能な個数しか存在しないが、自然数から作る集合は枚挙不可能（非可算）な数だけ存在する。

停止問題は計算可能ではないが、プログラムの実行をシミュレートし、実際に停止するプログラムの無限のリストを作成することは可能である。すなわち、停止問題は帰納的可算集合（計算枚挙可能、半決定可能などとも）の例であり、チューリングマシンによって枚挙可能な集合である。同様に、ある集合が帰納的可算であることの必要十分条件は、それが空であるか、または何らかの計算可能関数の値域に等しいことである。帰納的可算集合は一般には決定不能だが、再帰理論が最も詳しく研究してきた領域である。

再帰理論の研究領域

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

相対計算可能性とチューリング次数

詳細は「チューリング還元」および「チューリング次数」を参照

数理論理学における再帰理論は、伝統的に相対計算可能性（relative computability）に注目してきた。これは、チューリングが1939年に神託機械を使って定義したチューリング計算可能性を一般化したものである。神託機械は、普通のチューリングマシンにオラクルへの質問機能を加えた仮説的な機械である。オラクルは自然数の特別な集合であり、「n はオラクル集合の中にあるか?」という形式の問いにだけ答えることができる。その回答は、たとえそのオラクル集合が計算不可能であっても即座に行われる。従って、計算不可能なオラクルを持った神託機械は、オラクルなしでは計算不可能な集合を計算することができる。

非形式的に言えば、自然数の集合 A が集合 B にチューリング還元可能であるとは、B をオラクル集合として持つ神託機械を用いれば、ある数が A に属するかどうかを正しく示せることを意味する（この例では、集合 A は B から（相対的に）計算可能、 B について再帰的とも称する）。集合 A が集合 B にチューリング還元可能であり、かつ、B が A にチューリング還元可能であるとき、これらの集合は同じチューリング次数（「決定不能性の次数」とも）を持つと言う。ある集合のチューリング次数は、その集合の計算不能な度合いの正確な尺度となる。

計算不能な集合の自然な例として、さまざまな形の停止問題を符号化して得られる互いに異なる集合たちがあるが、それらには次のような共通点がある。

1. それらは帰納的可算集合である。
2. 多対一還元によって互いに変換可能である。すなわち、集合 A と B について、A = {x : f(x) ∈ B} となる計算可能関数 f が存在する。これらの集合を多対一同値（またはm-同値）であるという。

多対一還元はチューリング還元より強い。計算不能集合の自然な例は全て多対一同値だが、A を B にチューリング還元可能だが多対一還元不可能な帰納的可算集合 A と B を構築することもできる。すべての帰納的可算集合は停止問題に多対一還元可能であることが判っているので、多対一還元とチューリング還元の観点で、停止問題は最も複雑な帰納的可算集合である。1944年、ポストは、すべての帰納的可算集合は計算可能かあるいは停止問題にチューリング同値かのいずれかだろうか、という疑問を投げかけた。つまり、チューリング次数がこの2つの間になるような帰納的可算集合は存在するか、という問いである。

その問題を考える過程で、ポストは帰納的可算集合の分類として単純集合/超単純集合/超々単純集合といった自然な型を定義した。ポストはこれらの集合が、多対一還元の観点から見たとき、計算可能集合と停止問題の厳密に中間に位置することを示した。ポストはまた、チューリング還元よりも強い意味の還元（真理値表還元）を用いた場合においても、それらの一部が厳密に中間に位置することを示した。しかし、結局ポストは中間のチューリング次数を持つ帰納的可算集合が存在するかという主問題は未解決のまま残し、これはポストの問題(en)と呼ばれるようになった。10年後の1954年、クリーネとポストは計算可能集合と停止問題の間のチューリング次数が存在することは示せたが、そのチューリング次数に属する帰納的可算集合が存在するかは示せなかった。その直後、Friedberg と Muchnik がそれぞれ独立に中間次数の帰納的可算集合が存在することを示し、ポストの問題を解決した。この画期的な成果により、帰納的可算集合のチューリング次数に関する広範な研究が始まり、非常に複雑かつ自明でない構造の存在が明らかになった。

帰納的可算でない集合は非可算個存在しており、一般の集合のチューリング次数に関する研究も、帰納的可算なチューリング次数に関する研究と同様に、再帰理論における主要な研究対象である。様々な特定の次数が構成されている。

• hyperimmune-free degrees：この次数から相対的に計算可能な関数は（非相対化された）計算可能関数によって majorize される
• high degrees：この次数からは（全ての計算可能関数 g を支配するような）関数 f が相対的に計算可能。ここでいう支配とは、g に依存する定数 c が存在し、全ての x > c についてg(x) < f(x)が成り立つことを指す
• random degrees：アルゴリズム的ランダムな無限列が該当
• 1-generic degrees：1-generic集合の次数
• 極限再帰集合の停止問題より下の次数

任意のチューリング次数（帰納的可算とは限らない）の研究では、チューリングジャンプの研究が関係してくる。ある集合 A のチューリングジャンプとは、オラクル集合 A を持つ神託機械の停止問題を符号化した自然数の集合である。任意の集合のチューリングジャンプは、元の集合よりチューリング次数が常に高く、Friedberg の定理によって、停止問題を計算する任意の集合は別の集合のチューリングジャンプとなることが示されている。ポストの定理は、チューリングジャンプと算術的階層（算術における定義可能性に基づいて自然数の部分集合を分類したもの）との密接な関係を示している。

チューリング次数に関する近年の研究は、チューリング次数の集合の全体構造と、帰納的可算集合のチューリング次数の集合に注目してきた。Shore と Slaman (1999)の深い定理によれば、次数 x をそのチューリングジャンプの次数に変換するような関数は、チューリング次数のなす半順序の中で定義できる。Ambos-Spies and Fejer (2006) にそのような研究の歴史が概観されている。

還元可能性

詳細は「還元 (計算複雑性理論)」を参照

チューリング還元可能性以外の還元可能性（reducibility）の研究も盛んである。ポスト（1944）は、真理値表還元可能性を含む強い還元可能性をいくつか提唱した。強い還元可能性を定義する神託付きチューリング機械は、付加されたオラクルがどういうものであろうと全域関数を計算する。弱い還元可能性とは、還元過程が必ずしも全てのオラクルで停止しない（つまり全域関数を計算しない）可能性があるものである。チューリング還元可能性は弱い還元可能性の一種である。

強い還元可能性には、次のものが含まれる。

一対一還元可能性

A が B に一対一還元可能であるとは、全域計算可能な単射 f があり、n が A に属すことと f(n) が B に属すこととが同値になることをいう。

多対一還元可能性

一対一還元可能性とほぼ同じだが、f の単射性を仮定しない。

真理値表還元可能性

A が B に真理値表還元可能であるとは、どんなオラクルに対しても全域関数を計算するような神託機械によってA が B にチューリング還元可能である場合を指す。神託の使用回数を制限したり、神託機械に条件を課すことで、様々な変種が得られる。それらも研究されている。

強い還元可能性に関する主要な研究においては、帰納的可算集合のクラスに対する理論と自然数からなる集合のクラスに対する理論との比較が行われてきた。さらに、各種還元可能性間の関係も研究されている。例えば、チューリング次数は真理値表次数であるか、または無限個の真理値表次数の和集合のどちらかであることが知られている。

チューリング還元可能性よりも弱い還元可能性（つまり、チューリング還元可能性を内包する還元可能性）も研究されている。よく知られている例として、算術的還元可能性と超算術的還元可能性がある。これらの還元可能性は、算術の標準モデルにおける定義可能性と密接に関連している。

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

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

逆数学

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

ナンバリング

ナンバリングとは関数や集合に対する番号付けである。より一般には自然数の集合から集合 $A$ への全射を $A$ のナンバリングという。

$A$ が関数や集合からなる集合である場合には、$A$ のナンバリングの計算可能性・実効性を考えることができる。例えば $A$ が帰納的可算集合からなる集合のとき、$A$ のナンバリング $\nu$ が計算可能であるとは、述語 $x\in \nu (i)$ が帰納的可算であることをいう。また $A$ が計算可能（部分）関数からなる集合のとき、$A$ のナンバリング $\nu$ が計算可能であるとは、部分関数 $(i,x)\mapsto \nu (i)(x)$ が計算可能であることをいう。

ナンバリングの間には「計算可能関数によって変換できるか」によって擬順序を定めることができる。正確には、ナンバリング $\nu$ が $\mu$ に還元可能であるということを、計算可能関数 $f$ が存在して $\nu =\mu \circ f$ が成り立つことと定める。この還元可能性に関してナンバリングの全体は擬順序集合を成す。とくに計算可能ナンバリングの全体について半順序反映を取ったものを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) が述べたように、再帰理論ではこの分野の一般化である算術的還元可能性、超算術的還元可能性、α-再帰理論なども研究されている。これらの一般化された概念の中には、チューリングマシンでは実行不能にもかかわらず、それでもなおチューリング還元可能性の自然な一般化と看做せるような還元可能性が存在する。これらの研究には解析的階層を調べるためのアプローチが各種含まれる。解析的階層と算術的階層の違いは、個々の数の量化に加えて自然数の集合の量化を認める点にある。これらの領域は整列順序や木の理論と関係している。例えば再帰的な（二分木でない）木が無限の分岐を持たない場合、その全てのインデクスの集合は解析的階層のレベル $\Pi _{1}^{1}$ について完全である。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）がある。同学会は毎年、学術会議をいくつか開催している。

参考文献

入門的教科書

• S. B. Cooper, 2004. Computability Theory, Chapman & Hall/CRC. ISBN 1-58-488237-9
• N. Cutland, 1980. Computability, An introduction to recursive function theory, Cambridge University Press. ISBN 0-521-29465-7
• Y. Matiyasevich, 1993. Hilbert's Tenth Problem, MIT Press. ISBN 0-262-13295-8

専門的教科書

• S. Jain, D. Osherson, J. Royer and A. Sharma, 1999. Systems that learn, an introduction to learning theory, second edition, Bradford Book. ISBN 0-262-10077-0
• S. Kleene, 1952. Introduction to Metamathematics, North-Holland (11th printing; 6th printing added comments). ISBN 0-7204-2103-9
• M. Lerman, 1983. Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag. ISBN 3-540-12155-2.
• P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN 0-444-87295-7
• P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN 0-444-50205-X
• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
• S. G. Simpson, 1999. Subsystems of Second Order Arithmetic, Springer-Verlag. ISBN 3-540-64882-8
• R. I. Soare, 1987. Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag. ISBN 0-387-15299-7.

概要的な論文

• K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.
• H. Enderton, 1977. "Elements of Recursion Theory." Handbook of Mathematical Logic, edited by J. Barwise, North-Holland (1977), pp. 527–566. ISBN 0-7204-2285-X
• Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, 1998. Handbook of Recursive Mathematics, North-Holland (1998). ISBN 0-7204-2285-X
• M. Fairtlough and S. Wainer, 1998. "Hierarchies of Provably Recursive Functions". In Handbook of Proof Theory, edited by S. Buss, Elsevier (1998).
• R. I. Soare, 1996. Computability and recursion, Bulletin of Symbolic Logic v. 2 pp. 284–321.

研究論文

• A. Church, 1936a. "An unsolvable problem of elementary number theory." American Journal of Mathematics v. 58, pp. 345–363. Reprinted in "The Undecidable", M. Davis ed., 1965.
• A. Church, 1936b. "A note on the Entscheindungsproblem." Journal of Symbolic Logic v. 1, n. 1, and v. 3, n. 3. Reprinted in "The Undecidable", M. Davis ed., 1965.
• M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9
• R. M. Friedberg, 1958. "Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition." The Journal of Symbolic Logic, v. 23, pp. 309-316.
• E. M. Gold, 1967. "Language identification in the limit". Information and Control, volume 10, pages 447–474.
• L. Harrington and R. I. Soare, 1991. "Post's Program and incomplete recursively enumerable sets", Proceedings of the National Academy of Sciences of the USA, volume 88, pages 10242--10246.
• S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability." Annals of Mathematics v. 2 n. 59, 379–407.
• J. Myhill, 1956. "The lattice of recursively enumerable sets." The Journal of Symbolic Logic, v. 21, pp. 215-220.
• E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
• E. Post, 1947. "Recursive unsolvability of a problem of Thue." Journal of Symbolic Logic v. 12, pp. 1–11. Reprinted in "The Undecidable", M. Davis ed., 1965.
• T. Slaman and W. H. Woodin, 1986. "Definability in the Turing degrees." Illinois J. Math. v. 30 n. 2, pp. 320–334.
• R. I. Soare, 1974. "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets." Annals of Mathematics, v. 100, pp. 80-120.
• A. Turing, 1937. "On computable numbers, with an application to the Entscheindungsproblem." Proceedings of the London Mathematics Society, ser. 2 v. 42, pp. 230–265. Corrections ibid. v. 43 (1937) pp. 544–546. Reprinted in "The Undecidable", M. Davis ed., 1965.
• A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.

外部リンク

• Association for Symbolic Logic 公式サイト
• Computability in Europe 公式サイト
• Webpage on Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes