計算可能性理論
上記の再帰集合と関数の理論から始まり、再帰理論の分野は多くの密接に関連するトピックの研究を含むように成長しました。 これらは独立した研究分野ではありません：これらの各分野は他の分野からアイデアと結果を引き出し、ほとんどの再帰理論家はそれらの大部分に精通しています。
相対計算可能性とチューリング度
数学的論理における再帰理論は伝統的に相対計算可能性に焦点を当ててきたが、これはチューリング(1939)によって導入されたoracleチューリングマシンを使用して定義されたチューリング計算可能性の一般化である。 Oracle Turing machineは、通常のTuring machineのアクションを実行することに加えて、自然数の特定のセットであるoracleの質問をすることができる仮想的なデバイスです。 Oracleマシンは、「oracleセットにnはありますか？”. Oracleセットが計算できない場合でも、各質問はすぐに正しく回答されます。 したがって、非計算可能なoracleを持つoracleマシンは、oracleを持たないTuringマシンができないセットを計算できます。
非公式には、自然数の集合Aは、bをoracle集合として実行したときに数値がaにあるかどうかを正しく伝えるoracleマシンがある場合、集合Bにチューリング還元可能である（この場合、集合AはBから（相対的に）計算可能であり、bで再帰的であるとも言われる）。 集合Aが集合Bにチューリング還元可能であり、BがAにチューリング還元可能であるならば、集合は同じチューリング度（解かない度とも呼ばれる）を持つと言われる。 セットのチューリング度は、セットがどのように計算不可能であるかの正確な尺度を与えます。
計算できない集合の自然な例は、停止問題の変種を符号化する多くの異なる集合を含み、共通する二つの性質を有する:
- それらは再帰的に列挙可能であり、
- はそれぞれ多対一の削減を介して他のものに変換することができます。 すなわち、そのような集合AとBが与えられたとき、A={x:f(X)≤B}となるような全計算可能関数fが存在する。 これらの集合は、多対一等価（またはm-等価）であると言われています。
多-一簡約はチューリング簡約よりも”強い”：集合Aが集合Bに多-一簡約可能であれば、AはBにチューリング簡約可能であるが、逆は必ずしも成り立つとは限らない。 非可算集合の自然な例はすべて多対一同値であるが、再帰的に可算集合AとBを構成して、AがBにチューリング可約であるがBに多対一可約ではないようにすることは可能である。 すべての再帰的列挙可能集合は停止問題に対して多-一還元可能であり、したがって停止問題は多-一還元可能性およびチューリング還元可能性に関して最も複雑な再帰的列挙可能集合であることを示すことができる。 Post(1944)は、すべての再帰的列挙可能な集合が計算可能であるか、停止問題と同等のチューリングであるか、すなわち、それらの間にチューリング度の中間を持つ再帰的列挙可能な集合が存在しないかどうかを尋ねた。
中間結果として、Postは単純、超単純、超単純集合のような再帰的に列挙可能な集合の自然な型を定義しました。 ポストは、これらの集合が厳密に計算可能な集合と多-一還元性に関して停止問題の間にあることを示した。 ポストはまた、それらのいくつかはチューリング還元性よりも強い他の還元性概念の下で厳密に中間的であることを示した。 しかし、ポストは中間チューリング度の再帰的に列挙可能なセットの存在の主な問題を開いたままにしました。 10年後、KleeneとPostは1954年に計算可能な集合と停止問題の間に中間チューリング度があることを示したが、これらの次数のいずれかが再帰的に列挙可能な集合を含むことを示すことはできなかった。 この直後、FriedbergとMuchnikは、再帰的に列挙可能な中間次数の集合の存在を確立することによって、Postの問題を独立して解決しました。 この画期的な結果は、再帰的に列挙可能な集合のチューリング度の広い研究を開き、非常に複雑で自明でない構造を持つことが判明しました。
再帰的に列挙可能ではない集合は無数にあり、すべての集合のチューリング度の調査は再帰的に列挙可能なチューリング度の調査と同様に再帰理論の中心的なものである。 特別な性質を持つ多くの度が構築されました：その度に関連して計算可能なすべての関数が（非相対化された）計算可能な関数によってmajorized hyperimmune-free度; すべてのx>cに対してg(x)<f(x)が成り立つようなgに依存する定数cが存在するという意味で、すべての計算可能関数gを支配する関数fを計算することができる高度、アルゴリズム的にランダムな集合を含むランダム度、1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の1-一般集合の停止問題の下の次数。
任意の（必ずしも再帰的に列挙可能ではない）チューリング度の研究には、チューリングジャンプの研究が含まれる。 任意の集合のチューリング-ジャンプは常に元の集合よりも高いチューリング次数を持ち、フリードバーグの定理は、停止問題を計算する任意の集合は別の集合のチューリング-ジャンプとして得ることができることを示している。 ポストの定理は、チューリングジャンプ演算と算術階層との間に密接な関係を確立しており、これは算術における定義可能性に基づいて自然数の特定の部分集合の分類である。
チューリング度に関する最近の多くの研究は、チューリング度の集合と再帰的に列挙可能な集合を含むチューリング度の集合の全体的な構造に焦点を当てている。 A deep theorem of Shore and Slaman(1999)は、次数xをそのチューリングジャンプの次数に写像する関数は、チューリング次数の半順序で定義可能であると述べている。 Ambos-Spies and Fejer(2006)による最近の調査では、この研究とその歴史的進歩の概要が示されています。
その他
再帰理論の研究の進行中の領域は、チューリング還元性以外の還元性関係を研究しています。 Post(1944)はいくつかの強力な還元可能性を導入し、真理値表還元可能性を意味するために命名された。 強い還元性を実装するチューリングマシンは、どのオラクルが提示されているかにかかわらず、total関数を計算します。 弱い還元性は、還元過程がすべての神託について終了しない場合のものであり、チューリング還元性はその一例である。
強い還元性には次のものが含まれます:
一一還元可能性AがBに一一還元可能（または1-還元可能）であるとは、各nがAに含まれるような全計算可能な単射関数fが存在し、f(n)がBに含まれていることが必要であることである。 Aがbに多-1還元可能（またはm-還元可能）であるとは、各nがAに含まれるような全計算可能関数fが存在し、f(n)がBに含まれることと同値である。 真理値表還元可能性aが真理値表還元可能であるとは、aが与えられたオラクルに関係なく全関数を計算するoracle Turing machineを介してBにチューリング還元可能であることを意味する。 カントール空間のコンパクトさのために、これは、還元が（入力のみに依存して）単一の質問のリストをオラクルに同時に提示し、その答えを見たことが、最初のクエリに対するオラクルの答えに関係なく、追加の質問をすることなく出力を生成することができるということと同等である。 真理値表還元性の多くの変種も研究されている。
さらなる還元可能性（正、分離、接続詞、線形およびそれらの弱および有界バージョン）については、Reduction（再帰理論）の記事で議論されている。
強い還元性に関する主な研究は、すべての再帰的に可算な集合のクラスと自然数のすべての部分集合のクラスの両方について、それらの理論を比較することであった。 さらに，還元性間の関係を研究した。 例えば、すべてのチューリング次数は真理値表次数であるか、または無限に多くの真理値表次数の和集合であることが知られている。
チューリング還元性よりも弱い還元性（つまり、チューリング還元性によって暗示される還元性）も研究されている。 最もよく知られているのは、算術的還元性と超算術的還元性である。 これらの還元可能性は、算術の標準モデル上の定義可能性と密接に関連している。
Riceの定理と算術的階層編集
Riceは、すべての自明でないクラスC（すべてのr.e.集合ではないがいくつかのr.e.集合を含む）に対して、添字集合E={e:eth r.e. 集合We is in C}は、停止問題またはその補集合のいずれかがeに多対一還元可能である、すなわちeに多対一還元を用いて写像することができるという性質を持つ（詳細はライスの定理を参照）。 しかし、これらのインデックスセットの多くは、停止問題よりもさらに複雑です。 これらのタイプのセットは、算術階層を使用して分類できます。 例えば、すべての有限集合のクラスの添字集合FINはレベルΣ2にあり、すべての再帰集合のクラスの添字集合RECはレベルΣ3にあり、すべてのcofinite集合の添字集合COFINもレベルΣ3にあり、すべてのチューリング完全集合のクラスの添字集合COMPはレベルΣ4にある。 これらの階層レベルは帰納的に定義され、Σ n+1はΣ Nに対して再帰的に列挙可能なすべての集合だけを含み、Σ1は再帰的に列挙可能な集合を含む。 つまり、これらのレベルのすべてのセットは、与えられたインデックスセットに多対一に縮小することができます。
Reverse mathematicsEdit
reverse mathematicsのプログラムは、二次算術のサブシステムにおける数学の特定の定理を証明するためにどの集合存在公理が必要であるかを尋ねる。 この研究はHarvey Friedmanによって開始され、Stephen Simpsonらによって詳細に研究されました。Simpson(1999)はプログラムの詳細な議論を提供します。 問題の集合存在公理は、自然数の冪集合が様々な還元可能性の概念の下で閉じられているという公理に非公式に対応しています。 逆数学で研究されているそのような公理の中で最も弱いものは再帰的理解であり、これは自然の冪集合がチューリング還元性の下で閉じていることを述べている。
NumberingsEdit
番号付けは関数の列挙であり、eとxの二つのパラメータを持ち、入力xの番号付けにおけるe番目の関数の値を出力します。 ナンバリングは部分再帰的にすることができますが、そのメンバーの一部は完全再帰的である、つまり計算可能な関数です。 許容される番号は、他のすべてを翻訳できる番号です。 フリードバーグナンバリング（friedberg numbering）とは、全ての部分再帰関数の一対一のナンバリングであり、必ずしも許容されるナンバリングではない。 後の研究では、再帰的に列挙可能な集合のクラスのような他のクラスの番号付けも扱った。 ゴンチャロフは、例えば、再帰的に可算な集合のクラスを発見し、その数は再帰的同型に関して正確に2つのクラスに分類される。
優先度メソッド編集
詳細な説明については、記事Turing degreeのセクションポストの問題と優先度メソッドを参照してください。
Postの問題はpriorityメソッドと呼ばれるメソッドで解決されました。 このメソッドは、主に、特定のプロパティを持つ再帰的に列挙可能なセットを構築するために使用されます。 この方法を使用するには、構築されるセットの目的のプロパティは、要件として知られている目標の無限のリストに分割され、すべての要件を満た 各要件は、要件の優先度を表す自然数に割り当てられるため、最も重要な優先度には0が割り当てられ、最も重要な優先度には1が割り当てられます。 その後、セットは段階的に構築され、各段階は、セットに数字を追加するか、最終セットが要件を満たすようにセットから数字を禁止することによって、 優先順位は、そのようなイベントで何をすべきかを決定するために使用されます。
優先引数は再帰理論における多くの問題を解決するために採用されており、その複雑さに基づいて階層に分類されています(Soare1987)。 複雑な優先度引数は技術的であり、従うのが難しいため、伝統的には優先度引数なしで結果を証明すること、または優先度引数なしで証明された結果もそれなしで証明できるかどうかを確認することが望ましいと考えられてきました。 例えば、Kummerは、優先順位法を使用せずにFriedberg numbersingsの存在の証明に関する論文を発表しました。
再帰可算集合の格子編集
ポストは、任意の無限のr.eを含まない無限の補数を持つr.e.集合として単純なセットの概念を定義したとき。 セット、彼は包含の下で再帰的に列挙可能なセットの構造を研究し始めた。 この格子はよく研究された構造になった。 再帰集合は、集合とその補集合が両方とも再帰的に列挙可能である場合にのみ、集合が再帰的であるという基本的な結果によって、この構造で定義す 無限のr.e.集合は常に無限の再帰的部分集合を持つが、一方で単純な集合は存在するが、coinfinite再帰的なスーパーセットは持たない。 Post(1944)はすでに超単純集合と超単純集合を導入しており、後にはすべてのr.e.を満たすようなr.e.集合である最大集合が構築された。 超集合は与えられた極大集合の有限変形であるか、または共有限である。 この格子の研究におけるポストの当初の動機は、この性質を満たすすべての集合が再帰集合のチューリング度でも停止問題のチューリング度でもないような構造的概念を見つけることであった。 ポストはそのような特性を見つけることができず、彼の問題に対する解決策は代わりに優先度の方法を適用した。Harrington and Soare(1991)は最終的にそのような特性を見つけた。
自己同型問題編集
もう一つの重要な問題は、再帰理論的構造における自己同型の存在である。 これらの構造の一つは、有限差分法による包含の下で再帰的に列挙可能な集合の一つであり、この構造において、集合差分B−Aが有限であるための必要十分条件は、AがBの下にあることである。 極大集合（前の段落で定義されている）は、それらが非極大集合に対して自己同型ではないという性質を持っている、すなわち、先に述べた構造の下で再帰的な可算集合の自己同型が存在する場合、すべての極大集合は別の極大集合に写像される。 Soare(1974)は逆も成り立つこと、つまりすべての2つの極大集合は自己同型であることを示した。 したがって、極大集合は軌道を形成し、つまり、すべての自己同型は極大性を保持し、任意の2つの極大集合はある自己同型によって互いに変換される。 ハリントンは自己同型性のさらなる例を与えた：創造的な集合のそれ、停止問題と多対一に相当する集合。
再帰的に可算集合の格子のほかに、自己同型はすべての集合のチューリング度の構造とr.e.集合のチューリング度の構造についても研究されている。 どちらの場合も、Cooperはある度を他の度に写像する自明でない自己同型を構築したと主張する; しかし、この構成は検証されておらず、一部の同僚は、この構成に誤りが含まれており、チューリング度の自明でない自己同型があるかどうかの問題はまだこの分野での主な未解決の問題の一つであると信じている(Slaman and Woodin1986,Ambos-Spies and Fejer2006)。
コルモゴロフ
Kolmogorov complexity and algorithmic randomnessの分野は、Chaitin、Kolmogorov、Levin、Martin-Löf、Solomonoffによって1960年代から1970年代に開発されました（ここではアルファベット順に名前が付けられていますが、研究の大部分は独立しており、ランダム性の概念の統一は当時は理解されていませんでした）。 主なアイデアは、普遍的なチューリングマシンUを考慮し、U(p)がxを出力するような最短入力pの長さとして数（または文字列）xの複雑さを測定するこ このアプローチは、有限オブジェクトのランダム性の概念を呼び出すことによって、無限列（自然数の部分集合の特性関数と同等）がランダムであるかどうかを決定する以前の方法に革命をもたらした。 コルモゴロフの複雑さは、独立した研究の対象となっただけでなく、証明を得るためのツールとして他の科目にも適用されました。この分野にはまだ多くの未解決の問題があります。 そのため、この分野の最近の研究会議は2007年に開催され、Joseph MillerとAndre Niesによって未解決の問題のリストが維持されています。
周波数計算編集
再帰理論のこの枝は、次の質問を分析しました：0<m<nを持つ固定されたmとnに対して、関数Aは任意の異なるn入力x1、x2、。..,xn n個の数のタプルy1,y2,…式A(xk)=ykの少なくともmが真であるようなyn。 このような集合は(m,n)-再帰集合と呼ばれる。 再帰理論のこの枝の最初の主要な結果は、2m>nを持ついくつかのm,nに対して(m,n)-再帰である場合、集合が計算可能であるというTrakhtenbrotの結果である。 一方、Jockuschの半再帰集合（Jockuschが1968年にそれらを導入する前に既に非公式に知られていた）は、2m<n+1の場合に限り、(m,n)-再帰である集合の例である。 これらの集合には数え切れないほど多くのものがあり、このタイプの再帰的に列挙可能ではあるが計算不可能な集合もいくつかあります。 その後、Degtevは(1,n+1)-再帰的ではあるが(1,n)-再帰的ではない再帰的に列挙可能な集合の階層を確立しました。 ロシアの科学者による研究の長い段階の後、この主題は、上記の有界還元性および他の関連する概念に周波数計算をリンクした有界クエリ、上のビーゲルの論文によって西洋で再人気となった。 主要な結果の一つは、セットAが計算可能であることを述べているKummerの基数理論であった場合にのみ、いくつかのアルゴリズムは、N個の異なる数の各タプルのために列挙するようなn個の異なる数までN個の可能な選択肢と交差するn個の数のこのセットの基数の多くの可能な選択肢をN個の異なる数のタプルのためにn個の異なる数のタプルのためにn個の異なる数のタプルを列挙することがある。; これらの選択肢には真の基数が含まれていなければなりませんが、少なくとも一つの偽の基数は除外されます。
帰納的推論
これは学習理論の再帰理論的枝である。 これは、1967年からの限界での学習のE.マーク*ゴールドのモデルに基づいており、それ以来、学習のより多くのモデルを開発してきました。 一般的なシナリオは次のとおりです：計算可能な関数のクラスSが与えられた場合、(f(0),f(1),の形式の任意の入力に対して出力する学習器（つまり、再帰関数）がありますか。..,f(n))は仮説である。 学習者Mは、すべての計算可能関数の許容可能な番号付けについて以前に合意されたfのほぼすべての仮説が同じインデックスeである場合、関数fを学習します。Mは、MがS内のすべてのfを学習する場合、Sを学習します。基本的な結果は、すべての再帰的に列挙可能な関数のクラスは学習可能であるが、すべての計算可能関数のクラスRECは学習可能ではないということです。 多くの関連モデルが検討されており、正のデータから再帰的に列挙可能な集合のクラスの学習は、1967年以降のGoldの先駆的な論文から研究されたトピックで
チューリング計算可能性の一般化編集
再帰理論には、sacks(1990)によって記述されているように、算術還元可能性、超算術還元可能性、α再帰理論などのこの分野の一般化された概念の研究が含まれています。 これらの一般化された概念には、チューリング機械では実行できない還元性が含まれていますが、チューリング還元性の自然な一般化です。 これらの研究には、個々の数に対する定量化に加えて、自然数の集合に対する定量化を可能にすることによって、算術的階層とは異なる分析的階層を調 例えば、無限分岐を持たない再帰的（非バイナリ）木のすべての添字の集合は、Level≥1 1{\displaystyle\Pi}に対して完全である。_{1}^{1}}
分析階層の。 チューリング還元性と超数論的還元性は、有効記述集合論の分野で重要である。 構成可能度のさらに一般的な概念は、集合論で研究されている。
連続計算可能性理論編集
デジタル計算のための計算可能性理論はよく発達しています。 計算可能性理論は、微分方程式と連続力学系によってモデル化されたアナログコンピュータ、アナログ信号処理、アナログエレクトロニクス、ニューラルネットワーク、連続時間制御理論において起こるアナログ計算のためにあまり発達していない（Orponen1997;Moore1996）。
