再帰理論
自然数の集合のチューリング次数と、一階述語論理を用いてその集合を定義する(算術的階層から見た)困難さの間には、密接な関係がある。そのような関係性を正確に示す一例がポストの定理である。より弱い関係性として、例えばクルト・ゲーデルが不完全性定理の証明の中で示した例がある。ゲーデルの証明は、実効的な一階理論の論理的結果の集合は帰納的可算集合を成すこと、そしてもしその理論が十分強いならこの集合は計算不可能になることを示している。同様に、タルスキの定義不可能性定理(en)は定義可能性と計算可能性の両方の言葉で解釈することができる。
再帰理論は二階算術(自然数と自然数の集合に関する形式的理論)とも関係している。特定の集合が計算可能だったり相対的に計算可能だったりする場合、それらの集合は二階算術の中の弱い体系内で定義できることがよくある。逆数学の研究プログラムは、よく知られた数学的定理に内在する計算不可能性を測る尺度としてこれらの体系を用いる。
A が B に一対一還元可能であるとは、全域計算可能な単射 f があり、n が A に属すことと f(n) が B に属すこととが同値になることをいう。
再帰理論を扱う国際的学術団体として記号論理学会(Association for Symbolic Logic)がある。同学会は毎年、学術会議をいくつか開催している。
コルモゴロフ複雑性とアルゴリズム的無作為性の分野は、1960年代から1970年代にかけてチャイティン、コルモゴロフ、Levin、Martin-Löf、Solomonof らが開拓した。中心となる考え方は、万能チューリング機械 U があるとき、数(あるいは文字列)x の複雑性を x が出力となるような U(p) の最短の入力 p の長さで表すというものである。これにより、無限の数列(自然数の部分集合を与える特性関数と等価)が無作為か否かの判定を、有限のオブジェクト群の無作為性から導くことができるようになった。コルモゴロフ複雑性は独立した研究分野というだけでなく、他の分野での証明に応用されるようになっている。未解決の問題も多く残されている。最近でも、2007年1月にこの分野に関する国際会議が開催され、未解決の問題の一覧が Joseph Miller と Andre Nies によって示された。