相互関係[編集]自然数の集合のチューリング次数と、一階述語論理[4]を用いてその集合を定義する(算術的階層から見た)困難さの間には、密接な関係がある。そのような関係性を正確に示す一例がポストの定理である。弱い関係性として、例えばクルト・ゲーデルが不完全性定理の証明の中で示した例がある。ゲーデルの証明は、実効的な一階理論の論理的結果の集合は帰納的可算集合を成すこと、そしてもしその理論が十分強いならこの集合は計算不可能になることを示している。同様に、タルスキの定義不可能性定理(en)は定義可能性と計算可能性の両方の言葉で解釈することができる。再帰理論は二階算術(自然数と自然数の集合に関する形式的理論)とも関係している。特定の集合が計算可能だったり相対的に計算可能だったりする場合、それらの集合は二階算術の中の弱い体系内で定義できることがよくある。逆数学の研究プログラムは、よく知られた数学的定理に内在する計算不可能性を測る尺度としてこれらの体系を用いる。二階算術と逆数学に関する様々な話題を取り上げている。証明論の分野の研究対象には、二階算術とペアノ算術の他にも、ペアノ算術よりも弱い自然数に関する形式的体系などがある。(1998)を参照されたい)。原始帰納的算術において全域関数であることが証明可能な計算可能関数は原始帰納的なものに限られるが、ペアノ算術ではアッカーマン関数のような原始帰納的でない関数が全域関数であることを証明できる。いえペアノ算術でも全ての計算可能関数が全域関数と証明できる訳ではない。そのような関数としてはグッドスタインの定理から得られる例がある。名称問題[編集]数理論理学において、計算可能性とその一般化を研究する分野は、「再帰理論」と呼ばれてきた。theory」と呼ぶことを提案した。computable」という用語の方が自然で判り易いと主張している。そのため、近年では計算可能性理論と呼ぶ研究者が増えている[5]。「帰納的可算」といった用語の代わりとして使われるようになっている。ようにまだ納得していない研究者もいる。しても、研究対象のほとんどが計算可能でないことを表せていない点を指摘する人もいる[8]。改版するときに、そのように用語を変更した。再帰理論の鍵となる特性は、その結果や構造が自然数への計算可能な全単射において不変である点だとした。計算可能な全単射では集合の各要素を単に改名するだけで、その構造は変化させない。ユークリッド平面での回転が幾何学的形状を変化させないのと同じである。2つの無限の計算可能集合は計算可能な全単射でリンクされるので、これは全ての無限な計算可能集合に当てはまる(有限の計算可能集合については自明である)。よれば、再帰理論が対象とする集合は、計算可能な全単射で自然数と対応できるような計算不可能集合である。同学会は毎年、学術会議をいくつか開催している。訳注:リンクは原文ママ。いった文字列が題名にある論文が多数存在している(注:購読者以外は検索できない)。2004年2月15日、2006年1月9日参照。1998年8月24日、2006年1月9日参照。1998年8月28日、2006年1月9日参照。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。Cookieに関する声明モバイルビュ。