Loading article…
計算可能性理論（再帰理論とも呼ばれる）は、数理論理学、コンピュータ科学、計算理論の一分野であり、1930年代に計算可能関数とチューリング次数の研究から始まった。その後、この分野は一般化された計算可能性と定義可能性の研究を含むまでに拡大した。これらの領域において、計算可能性理論は証明論や有効記述集合論と重なり合う。
計算可能性理論が扱う基本的な問題には、以下のようなものがある。
知識や方法論の面ではかなりの重複があるものの、数学的計算可能性理論家は相対的計算可能性の理論、還元可能性の概念、次数構造を研究し、コンピュータ科学分野の研究者は部分再帰階層の理論、形式手法、形式言語に焦点を当てている。どの数学的構成を効果的に実行できるかを研究することは、再帰数学と呼ばれることもある。[ a ]
計算可能性理論は、1930年代にクルト・ゲーデル、アロンゾ・チャーチ、ローザ・ペーター、アラン・チューリング、スティーブン・クリーネ、エミール・ポストらの研究によって始まった。[ 4 ] [ b ]
研究者たちが得た基本的な結果は、チューリング計算可能性を、非形式的な有効計算の概念の正しい形式化として確立した。1952年、これらの結果を受けて、クリーネは「チャーチのテーゼ」[ 5 ]： 300と「チューリングのテーゼ」[ 5 ]： 376という2つの名称を考案した。今日では、これらはしばしば単一の仮説、すなわちチャーチ＝チューリングのテーゼとして考えられており、アルゴリズムによって計算可能な関数はすべて計算可能な関数であると述べている。当初は懐疑的であったゲーデルも、1946年までにこのテーゼを支持する議論を展開した[ 6 ]： 84
「タルスキは講演の中で（そして私は正当だと思うが）一般再帰性（またはチューリングの計算可能性）の概念の非常に重要な点を強調している。この重要性は、この概念によって初めて興味深い認識論的概念、つまり選択された形式主義に依存しない概念に絶対的な概念を与えることに成功したという事実に大きく起因しているように思われる。」[ 6 ]： 84 [ 7 ]
有効計算の定義によって、数学には有効に決定できない問題が存在するという最初の証明がもたらされた。1936年、チャーチ[ 8 ] [ 9 ]とチューリング[ 10 ]（ゲーデルが不完全性定理を証明するために用いた手法に触発されて）は、それぞれ独立に決定問題が有効に決定できないことを示した。この結果は、任意の数学的命題が真か偽かを正しく決定できるアルゴリズム的手順は存在しないことを示した。
これらの初期例が確立された後、数学の多くの問題が決定不能であることが示されました。 [ c ] 1947年、マルコフとポストは、半群の語問題は効果的に決定できないことを示す独立した論文を発表しました。この結果を拡張して、ピョートル・ノビコフとウィリアム・ブーンは1950年代に、群の語問題は効果的に解けないことを独立に示しました。つまり、有限表示群の語が与えられたときに、その語によって表される要素が群の単位元であるかどうかを決定できる効果的な手順はありません。1970年、ユーリ・マティヤセビッチは（ジュリア・ロビンソンの結果を使用して）マティヤセビッチの定理を証明しました。これは、ヒルベルトの第10問題には効果的な解がないことを意味します。この問題は、整数上のディオファントス方程式が整数に解を持つかどうかを決定できる効果的な手順があるかどうかを問うものでした。
この分野で研究されている計算可能性の主な形式は、1936 年にチューリングによって導入されました。[ 10 ]自然数の集合は、与えられた数 n に対して、n が集合に含まれている場合は出力1で停止し、n が集合に含まれていない場合は出力 0 で停止するチューリングマシンが存在する場合、計算可能集合 (決定可能集合、再帰的集合、またはチューリング計算可能集合とも呼ばれる) であると言われます。自然数から自然数への関数fは、入力nに対して停止し、出力f ( n ) を返すチューリング マシンが存在する場合、(チューリング)計算可能関数、または再帰関数です。ここでチューリング マシンを使用する必要はありません。チューリング マシンと同じ計算能力を持つ計算モデルは他にもたくさんあります。たとえば、原始再帰とμ 演算子から得られるμ 再帰関数などです。
計算可能な関数と集合の用語は完全に標準化されていません。μ-再帰関数による定義と、ゲーデルによる再帰関数の別の定義により、チューリングマシンで計算可能な集合と関数は伝統的に再帰的という名称で呼ばれるようになりました。決定可能という言葉は、チューリングらの原著論文で使用されたドイツ語のEntscheidungsproblemに由来します。現代では、「計算可能な関数」という用語にはさまざまな定義があります。ナイジェル・J・カットランド[ 11 ]によれば、それは部分再帰関数（一部の入力に対して未定義になる可能性がある）であり、ロバート・I・ソア[ 12 ]によれば、それは全再帰関数です。この記事では、これらの慣例のうち2番目に従います。1996年にソア[ 13 ]は用語について追加のコメントをしました。
すべての自然数の集合が計算可能であるとは限りません。入力0で停止するチューリングマシン（の記述）の集合である停止問題は、計算不可能な集合のよく知られた例です。計算不可能な集合が多数存在する理由は、チューリングマシンは可算個しか存在せず、したがって計算可能な集合も可算個しか存在しないという事実から導き出されますが、カントールの定理によれば、自然数の集合は非可算個存在します。
停止問題は計算可能ではありませんが、プログラムの実行をシミュレートして、停止するプログラムの無限リストを生成することは可能です。したがって、停止問題は計算可能列挙可能（ce）集合の一例であり、これはチューリングマシンで列挙できる集合です（計算可能列挙可能の他の用語には、再帰的列挙可能や半決定可能などがあります）。言い換えれば、集合がceであるのは、それが何らかの計算可能な関数の値域である場合のみです。ce集合は一般には決定可能ではありませんが、計算可能性理論において詳細に研究されています。
上述の計算可能集合と計算可能関数の理論を起点として、計算可能性理論の分野は、密接に関連する多くのトピックの研究を含むまでに発展しました。これらは独立した研究分野ではなく、それぞれの分野が他の分野からアイデアや成果を取り入れており、ほとんどの計算可能性理論家はこれらの分野の大部分に精通しています。
数理論理学における計算可能性理論は、伝統的に相対的計算可能性に焦点を当ててきました。これは、1939 年にチューリングによって導入されたオラクル チューリング マシンを使用して定義されるチューリング計算可能性の一般化です。 [ 14 ]オラクル チューリング マシンは、通常のチューリング マシンの動作を実行することに加えて、特定の自然数の集合であるオラクルに質問をすることができる仮想的な装置です。オラクル マシンは、「 nはオラクル セットに含まれていますか？」という形式の質問のみを行うことができます。オラクル セットが計算可能でない場合でも、各質問には即座に正しく回答されます。したがって、計算不可能なオラクルを持つオラクル マシンは、オラクルを持たないチューリング マシンでは計算できない集合を計算できます。
非公式には、自然数の集合Aが集合Bにチューリング還元可能であるとは、オラクル マシンが、Bをオラクル 集合として実行されたときに、数がAに含まれるかどうかを正しく判定できる場合をいいます (この場合、集合AはBから(相対的に)計算可能であり、Bに関して再帰的であるとも言われます)。集合Aが集合Bにチューリング還元可能であり、かつBがAにチューリング還元可能である場合、これらの集合は同じチューリング次数(解けない次数とも呼ばれる) を持つと言われます。集合のチューリング次数は、その集合がどれだけ計算不可能であるかを正確に示します。
計算不可能な集合の自然な例（停止問題の変種を符号化する多くの異なる集合を含む）には、2つの共通点がある。
多対一還元可能性はチューリング還元可能性よりも「強い」。集合Aが集合Bに多対一還元可能であれば、AはBにチューリング還元可能だが、その逆は必ずしも成り立たない。計算不可能な集合の自然な例はすべて多対一同値であるが、A が B にチューリング還元可能だが多対一還元可能ではないような計算可能列挙可能集合 A と B を構成することは可能である。すべての計算可能列挙可能集合は停止問題に多対一還元可能であることが示されており、したがって停止問題は多対一還元可能性とチューリング還元可能性に関して最も複雑な計算可能列挙可能集合である。1944 年に Post [ 15 ]は、すべての計算可能列挙可能集合が停止問題に対して計算可能かチューリング同値かのいずれかであるか、つまり、その 2 つの中間のチューリング次数を持つ計算可能列挙可能集合が存在しないかどうかを問うた。
中間的な結果として、ポストは単純集合、超単純集合、超超単純集合のような計算可能列挙可能集合の自然型を定義した。ポストは、これらの集合が多対一還元性に関して計算可能集合と停止問題の間にあることを示した。ポストはまた、それらのいくつかがチューリング還元性よりも強い他の還元性の概念の下で厳密に中間的であることを示した。しかし、ポストは中間チューリング次数を持つ計算可能列挙可能集合の存在という主要な問題を未解決のまま残した。この問題はポストの問題として知られるようになった。10年後、クリーネとポストは1954年に、計算可能集合と停止問題のチューリング次数の間に中間チューリング次数が存在することを示したが、これらの次数のいずれかが計算可能列挙可能集合を含むことを示すことはできなかった。その直後、フリードバーグとムチニクは、中間次数を持つ計算可能列挙可能集合の存在を確立することによって、ポストの問題を独立に解決した。この画期的な成果は、計算可能列挙可能集合のチューリング次数に関する広範な研究の幕開けとなり、それらは非常に複雑で非自明な構造を持つことが明らかになった。
計算可能列挙不可能な集合は数えきれないほど多く存在し、すべての集合のチューリング次数を調べることは、計算可能列挙可能なチューリング次数を調べることと同様に、計算可能性理論において中心的な役割を果たしている。特別な性質を持つ多くの次数が構築された。例えば、その次数に関して計算可能なすべての関数が、（相対化されていない）計算可能な関数によって優位化される超免疫フリー次数、すべてのx > cに対してg(x) < f(x)となるような、gに依存する定数c が存在するという意味で、すべての計算可能な関数gを支配する関数f を計算できる高次数、アルゴリズム的にランダムな集合を含むランダム次数、 1-ジェネリック集合の1-ジェネリック次数、および極限計算可能集合の停止問題以下の次数などである。
任意の（必ずしも計算可能列挙可能とは限らない）チューリング次数に関する研究には、チューリングジャンプの研究が含まれる。集合Aが与えられたとき、Aのチューリングジャンプは、オラクルAで動作するオラクルチューリングマシンの停止問題の解を符号化する自然数の集合である。任意の集合のチューリングジャンプは常に元の集合よりも高いチューリング次数を持ち、フリードバーグの定理は、停止問題を計算する任意の集合は、別の集合のチューリングジャンプとして得られることを示している。ポストの定理は、チューリングジャンプ操作と算術階層との間に密接な関係があることを示している。算術階層とは、自然数の特定の部分集合を算術で定義可能かどうかに基づいて分類したものである。
チューリング次数に関する最近の研究の多くは、チューリング次数の集合の全体構造と、計算可能列挙可能集合を含むチューリング次数の集合に焦点を当てています。ShoreとSlamanの深い定理[ 16 ]は、次数xをそのチューリングジャンプの次数にマッピングする関数は、チューリング次数の半順序で定義可能であると述べています。Ambos-SpiesとFejerによる調査[ 17 ]は、この研究の概要と歴史的進展を示しています。
計算可能性理論における継続的な研究分野の一つに、チューリング還元可能性以外の還元可能性関係の研究がある。Post [ 15 ]は、真理値表還元可能性を意味することからそのように名付けられた、いくつかの強い還元可能性を導入した。強い還元可能性を実装するチューリングマシンは、どのオラクルが提示されても、全関数を計算する。弱い還元可能性とは、還元プロセスがすべてのオラクルに対して終了しない可能性があるものであり、チューリング還元可能性はその一例である。
強い還元可能性には以下が含まれる。
さらなる還元可能性（正、選言的、連言的、線形、およびそれらの弱バージョンと有界バージョン）については、記事「還元（計算可能性理論）」で議論されています。
強い還元可能性に関する主要な研究は、計算可能なすべての集合のクラスと自然数のすべての部分集合のクラスの両方について、それらの理論を比較することであった。さらに、還元可能性間の関係も研究されてきた。例えば、すべてのチューリング次数は真理値表の次数であるか、または無限個の真理値表の次数の和集合であるかのいずれかであることが知られている。
チューリング還元可能性よりも弱い還元可能性（すなわち、チューリング還元可能性によって導かれる還元可能性）も研究されてきた。最もよく知られているのは、算術還元可能性と超算術還元可能性である。これらの還元可能性は、算術の標準モデル上の定義可能性と密接に関連している。
ライスは、すべての非自明なクラスC (一部の ce セットを含むが、すべてではない) に対して、インデックス セットE = { e : e番目の ce セットW eはCに含まれる} は、停止問題またはその補集合のいずれかがEに多対一還元可能である、つまり、多対一還元を使用してEにマッピングできるという性質を持つことを示した (詳細はライスの定理を参照)。しかし、これらのインデックス セットの多くは、停止問題よりもさらに複雑である。これらのタイプのセットは、算術階層を使用して分類できる。たとえば、すべての有限セットのクラスのインデックス セット FIN はレベル Σ 2にあり、すべての再帰セットのクラスのインデックス セット REC はレベル Σ 3にあり、すべての余有限セットのインデックス セット COFIN もレベル Σ 3にあり、すべてのチューリング完全セットのクラスのインデックス セット COMP はレベル Σ 4にある。これらの階層レベルは帰納的に定義され、Σ n +1 はΣ nに対して計算可能列挙可能なすべての集合を含み、Σ 1は計算可能列挙可能な集合を含みます。ここで示されているインデックス集合は、それぞれのレベルにおいて完全であり、つまり、これらのレベルのすべての集合は、与えられたインデックス集合に多対一還元することができます。
逆数学のプログラムでは、2 階算術のサブシステムで数学の特定の定理を証明するためにどの集合存在公理が必要かを問う。この研究はハーヴェイ・フリードマンによって開始され、スティーブン・シンプソンらによって詳細に研究された。1999 年にシンプソン[ 18 ]はプログラムについて詳細な議論を行った。問題となっている集合存在公理は、非公式には、自然数の冪集合がさまざまな還元可能性の概念の下で閉じていることを示す公理に対応する。逆数学で研究されているそのような公理の中で最も弱いものは再帰的内包であり、これは自然数の冪集合がチューリング還元可能性の下で閉じていることを示す。
番号付けは関数の列挙であり、2 つのパラメータeとxを持ち、入力xに対して番号付けのe番目の関数の値を出力します。番号付けは、そのメンバーの一部が全計算可能関数であっても、部分計算可能になる場合があります。許容番号付けとは、他のすべての番号付けを変換できる番号付けのことです。フリードバーグ番号付け(発見者の名にちなんで名付けられました) は、すべての部分計算可能関数の 1 対 1 の番号付けであり、必ずしも許容番号付けではありません。後の研究では、計算可能列挙可能集合のクラスなど、他のクラスの番号付けも扱われました。たとえば、ゴンチャロフは、計算可能同型に関して番号付けがちょうど 2 つのクラスに分類される計算可能列挙可能集合のクラスを発見しました。
ポストの問題は、優先度法と呼ばれる方法で解決されました。この方法を用いた証明は、優先度論証と呼ばれます。この方法は主に、特定の性質を持つ計算可能列挙可能集合を構築するために用いられます。この方法を用いるには、構築する集合の望ましい性質を、要件と呼ばれる無限の目標リストに分解し、すべての要件を満たすことで、構築された集合が望ましい性質を持つようにします。各要件には、その要件の優先度を表す自然数が割り当てられます。つまり、最も重要な優先度には0、2番目に重要な優先度には1、といった具合です。次に、集合は段階的に構築され、各段階では、集合に数値を追加するか、集合から数値を排除することによって、1つ以上の要件を満たすように試み、最終的な集合が要件を満たすようにします。ある要件を満たすことで、別の要件が満たされなくなる場合もあります。このような場合の対処法は、優先度順序によって決定されます。
優先順位論は計算可能性理論の多くの問題を解決するために用いられており、その複雑さに基づいて階層に分類されている。[ 12 ]複雑な優先順位論は技術的で理解しにくい場合があるため、従来は優先順位論を用いずに結果を証明したり、優先順位論を用いて証明された結果が優先順位論を用いなくても証明できるかどうかを確認したりすることが望ましいと考えられてきた。例えば、Kummer は優先順位法を用いずにフリードバーグ番号の存在を証明する論文を発表した。
ポストが単純集合の概念を、無限の補集合が無限の ce 集合を含まない ce 集合として定義したとき、彼は包含関係の下での計算可能列挙可能集合の構造の研究を始めました。この束はよく研究された構造になりました。この構造では、集合が計算可能であるのは、集合とその補集合の両方が計算可能列挙可能である場合に限るという基本的な結果によって、計算可能集合を定義できます。無限 ce 集合は常に無限の計算可能部分集合を持ちますが、その一方で、単純集合は存在しますが、常に共無限の計算可能上位集合を持つとは限りません。ポスト[ 15 ]はすでにハイパー単純集合とハイパーハイパー単純集合を導入しており、後に最大集合が構築されました。最大集合とは、すべての ce 上位集合が、与えられた最大集合の有限変種であるか、または共有限であるような ce 集合です。ポストがこの格子を研究した当初の動機は、この性質を満たすすべての集合が計算可能集合のチューリング次数にも停止問題のチューリング次数にも含まれないような構造的概念を見つけることでした。ポストはそのような性質を見つけることができず、彼の問題の解決策は代わりに優先順位法を適用することでした。1991年にハリントンとソアレ[ 19 ]が最終的にそのような性質を発見しました。
もう 1 つの重要な問題は、計算可能性理論構造における自己同型の存在です。これらの構造の 1 つは、有限差分を法とする包含関係における計算可能列挙可能集合の 1 つです。この構造では、集合の差B − Aが有限である場合に限り、 AはBより小さいです。最大集合(前の段落で定義) は、非最大集合と自己同型にならないという性質を持ちます。つまり、前述の構造の下で計算可能列挙可能集合の自己同型が存在する場合、すべての最大集合は別の最大集合に写像されます。1974 年に Soare [ 20 ]は、その逆も成り立つこと、つまり、すべての 2 つの最大集合は自己同型であることを示しました。したがって、最大集合は軌道を形成します。つまり、すべての自己同型は最大性を保存し、任意の 2 つの最大集合は何らかの自己同型によって互いに変換されます。ハリントンは、保型性を示す別の例として、創造的集合、すなわち停止問題と多対一で同値な集合を挙げた。
計算可能列挙可能集合の格子に加えて、自己同型は、すべての集合のチューリング次数の構造、および ce 集合のチューリング次数の構造についても研究されています。どちらの場合も、クーパーは、ある次数を他の次数に写像する非自明な自己同型を構築したと主張していますが、この構成は検証されておらず、一部の同僚は、この構成には誤りがあり、チューリング次数の非自明な自己同型が存在するかどうかという問題は、この分野における主要な未解決問題の 1 つです。[ 21 ] [ 17 ]
コルモゴロフ複雑性とアルゴリズム的ランダム性の分野は、1960年代から1970年代にかけて、チャイティン、コルモゴロフ、レヴィン、マルティン＝レーフ、ソロモノフらによって発展しました（ここでは名前をアルファベット順に示しています。研究の多くは独立して行われ、当時はランダム性の概念の統一性は理解されていませんでした）。主なアイデアは、普遍チューリングマシンUを考え、数値（または文字列） xの複雑性を、U ( p )がxを出力する最短の入力pの長さとして測定することです。このアプローチは、有限オブジェクトに対するランダム性の概念を導入することで、無限列（あるいは自然数の部分集合の特性関数）がランダムであるかどうかを判断する従来の方法に革命をもたらしました。コルモゴロフ複雑性は、独立した研究対象となっただけでなく、証明を得るためのツールとして他の分野にも応用されています。この分野にはまだ多くの未解決問題があります。[ d ]
この計算可能性理論の分野では、次の問題を分析しました。0 < m < nを満たす固定されたmとnに対して、任意の異なるn 個の入力x 1、x 2、...、x nに対して、方程式 A ( x k ) = y k のうち少なくとも m 個が真となるような n 個の数値のタプルy 1 、y 2、 ...、 y n を計算することが可能な関数 A はどれか。このような集合は( m 、 n ) -再帰集合として知られています。この計算可能性理論の分野における最初の主要な結果は、あるm、nに対して 2 m > nを満たす集合が ( m、n )-再帰的であれば、その集合は計算可能であるという Trakhtenbrot の結果です。一方、ヨクシュの半再帰的集合（ヨクシュが1968年に導入する前から非公式には知られていた）は、2m < n + 1の場合に限り( m , n )-再帰的である集合の例である。このような集合は数えきれないほど多く、また、この種の計算可能列挙可能だが計算不可能な集合もいくつか存在する。後に、デグテフは、(1, n + 1)-再帰的だが (1, n )-再帰的ではない計算可能列挙可能集合の階層を確立した。ロシアの科学者による長期間の研究の後、この主題は、頻度計算を上述の限定還元可能性やその他の関連概念に結びつけた、ベイゲルの限定クエリに関する論文によって西側で再び普及した。主要な成果の一つは、クンマーの濃度定理[22][23]であり、これは、集合Aが計算可能であるのは、n個の入力x1 , x2 , ... , xnが与えられたときに、最大n個の出力を返すチューリングマシンが存在し、そのうちの1つが{x1, x2, ..., xn}∩Aの濃度である場合に限る（濃度にはn + 1個の可能な値しかない：0, ..., n）。 )
これは、学習理論の計算可能性理論の分野です。1967年のE.マーク・ゴールドの極限における学習モデルに基づいており、それ以来、ますます多くの学習モデルが開発されてきました。一般的なシナリオは次のとおりです。計算可能な関数のクラスSが与えられたとき、( f (0), f (1), ..., f ( n ))の形式の任意の入力に対して仮説を出力する学習者（つまり、計算可能な関数）が存在するかどうか。学習者Mは、すべての計算可能な関数の事前に合意された許容可能な番号付けに関して、ほとんどすべての仮説がfの同じインデックスeである場合に、関数fを学習します。Mは、 S内のすべてのfを学習する場合にSを学習します。基本的な結果として、すべての計算可能列挙可能な関数クラスは学習可能ですが、すべての計算可能な関数のクラスRECは学習できません。多くの関連モデルが検討されており、また、1967年のゴールドの先駆的な論文以降、正のデータからの計算可能列挙可能な集合のクラスの学習も研究されているトピックです。
計算可能性理論には、1990年にサックスが述べたように、算術還元可能性、超算術還元可能性、α再帰理論など、この分野の一般化された概念の研究が含まれます。 [ 24 ]これらの一般化された概念には、チューリングマシンでは実行できない還元可能性が含まれますが、それでもチューリング還元可能性の自然な一般化です。これらの研究には、個々の数値に対する量化に加えて自然数の集合に対する量化も許容する点で算術階層とは異なる解析的階層を調査するアプローチが含まれます。これらの分野は整列順序と木の理論に関連しています。たとえば、無限分岐のない計算可能な（非二分）木のすべてのインデックスの集合は、レベルに対して完全です。分析的階層の。チューリング還元可能性と超算術還元可能性は、有効記述集合論の分野で重要である。さらに一般的な構成可能性の度合いの概念は、集合論で研究されている。
デジタル計算の計算可能性理論は十分に発展している。アナログコンピュータ、アナログ信号処理、アナログ電子回路、人工ニューラルネットワーク、微分方程式や連続力学系でモデル化される連続時間制御理論で発生するアナログ計算の計算可能性理論は、それほど十分に発展していない。[ 25 ] [ 26 ]例えば、 Blum–Shub–Smale マシンモデルなどの計算モデルは、実数上の計算を形式化している。
自然数の集合のチューリング次数と、その集合を一階述語論理式で定義することの難しさ（算術階層の観点から）の間には密接な関係がある。このような関係の一つは、ポストの定理によって明確にされている。より弱い関係は、クルト・ゲーデルが完全性定理と不完全性定理の証明において示した。ゲーデルの証明は、有効な一階述語論理の論理的帰結の集合は計算可能な列挙可能な集合であり、理論が十分に強ければこの集合は計算不可能であることを示している。同様に、タルスキの不確定性定理は、定義可能性と計算可能性の両方の観点から解釈することができる。
計算可能性理論は、自然数と自然数の集合の形式理論である二階算術とも関連しています。特定の集合が計算可能であるか、または比較的計算可能であるという事実は、これらの集合が二階算術の弱い部分体系で定義できることを意味することがよくあります。逆算術プログラムは、これらの部分体系を使用して、よく知られた数学の定理に内在する非計算可能性を測定します。1999年に、Simpson [ 18 ]は、二階算術と逆算術の多くの側面について議論しました。
証明論の分野には、2 階算術とペアノ算術の研究、およびペアノ算術よりも弱い自然数の形式理論が含まれます。これらの弱いシステムの強さを分類する 1 つの方法は、システムが全関数であることを証明できる計算可能関数を特徴付けることです。[ 27 ]例えば、原始再帰算術では、証明可能な全関数は実際には原始再帰ですが、ペアノ算術では、アッカーマン関数のような原始再帰ではない関数が全関数であることを証明します。ただし、すべての全計算可能関数がペアノ算術で証明可能な全関数であるわけではありません。そのような関数の例は、グッドスタインの定理によって提供されます。
計算可能性とその一般化を扱う数理論理学の分野は、初期の頃から「再帰理論」と呼ばれてきました。この分野の著名な研究者であるロバート・I・ソアは、代わりに「計算可能性理論」と呼ぶべきだと提案しました[ 13 ]。彼は、チューリングの「計算可能」という言葉を使った用語の方が、クリーネが導入した「再帰的」という言葉を使った用語よりも自然で広く理解されていると主張しています。現代の多くの研究者は、この代替用語を使い始めています[ e ] 。これらの研究者は、部分再帰関数や再帰的に列挙可能な( re )集合の代わりに、部分計算可能関数や計算可能列挙可能( ce )集合などの用語も使用しています。しかし、フォートナウ[ 28 ]やシンプソンが説明しているように、すべての研究者が納得しているわけではありません。[ 29 ]一部の評論家は、再帰理論と計算可能性理論 という名称は、計算可能性理論で研究される対象の大部分が計算可能ではないという事実を伝えきれていないと主張している。[ 30 ]
1967年、ロジャース[ 31 ]は、計算可能性理論の重要な特性は、その結果と構造が自然数上の計算可能な全単射の下で不変であるべきだと提唱した（この提唱は、幾何学におけるエアランゲン・プログラムの考えに基づいている）。その考えは、計算可能な全単射は、集合内の構造を示すのではなく、単に集合内の数の名前を変更するだけであり、ユークリッド平面の回転がその上に描かれた線の幾何学的側面を何も変えないのと同様である。任意の2つの無限計算可能集合は計算可能な全単射によって結び付けられるため、この提案はすべての無限計算可能集合を特定する（有限計算可能集合は自明とみなされる）。ロジャースによれば、計算可能性理論で関心のある集合は、自然数の計算可能な全単射によって同値類に分割された非計算可能集合である。
計算可能性理論における主要な専門組織は、記号論理学会（Association for Symbolic Logic ）であり、毎年複数の研究会議を開催している。学際的な研究団体である 欧州計算可能性学会（Computability in Europe、CiE）も、毎年一連の会議を主催している。
クルト・ゲーデル（1946年）：タルスキは講演の中で（そして私は正当だと思うが）一般再帰性（あるいはチューリングの計算可能性）の概念の大きな重要性を強調した。この重要性は、この概念によって初めて、興味深い認識論的概念、すなわち選択された形式主義に依存しない概念に絶対的な概念を与えることに成功したという事実に大きく起因しているように思われる。
より正確に言うと、整数の関数は、算術を含む任意の形式体系において計算可能であるのは、それが算術において計算可能である場合に限る。ここで、関数fは、 Sにfを表す計算可能な項が存在する場合にSにおいて計算可能であると呼ばれる。（注：本書には、クルト・ゲーデルによる1946年の論文（チャールズ・パーソンズによる解説は144ページ以降に掲載）も収録されている。1990年版では、ゲーデル自身が150ページに脚注を追加している（この脚注は、デイビスによる1965年の編纂版に収録されたゲーデルの論文にも追加されていた）。）
