再帰理論
ポストは単純集合(「無限帰納的可算集合を一つも含まないような無限補集合」を持つ帰納的可算集合)を定義し、そこから帰納的可算集合同士の包含関係を研究し始めた。この束 (lattice) は今日では詳細に研究された構造となっている。ある集合が帰納的である必要十分条件は、集合とその補集合が共に帰納的可算であることである。この基本的な結果を用いて、この構造内に帰納的集合を定義できる。無限帰納的可算集合は常に無限帰納的集合を部分集合として持つのに対し、単純集合は余無限 (coinfinite) な帰納的集合を上位集合として持たない。ポスト(1944)は既に超単純集合と超々単純集合を導入していた。後に極大集合 (maximal set) が構成されたが、これは帰納的可算である全ての上位集合が所与の極大集合の有限な変種かまたは余有限 (co-finite) であるような帰納的可算集合である。ポストがこの束を研究した元々の動機は、この性質を満たす全ての集合のチューリング次数が、帰納的集合と停止問題の何れのチューリング次数とも異なるということを構造的に示せないかという点にあった。ポストはそのような性質を見出すことはできず、彼の問題は代わりに優先度法を用いて解決されたが、Harrington と Soare (1991) はそのような性質をついに発見した。
数理論理学における再帰理論は、伝統的に相対計算可能性(relative computability)に注目してきた。これは、チューリングが1939年に神託機械を使って定義したチューリング計算可能性を一般化したものである。神託機械は、普通のチューリングマシンにオラクルへの質問機能を加えた仮説的な機械である。オラクルは自然数の特別な集合であり、「n はオラクル集合の中にあるか?」という形式の問いにだけ答えることができる。その回答は、たとえそのオラクル集合が計算不可能であっても即座に行われる。従って、計算不可能なオラクルを持った神託機械は、オラクルなしでは計算不可能な集合を計算することができる。
非形式的に言えば、自然数の集合 A が集合 B にチューリング還元可能であるとは、B をオラクル集合として持つ神託機械を用いれば、ある数が A に属するかどうかを正しく示せることを意味する(この例では、集合 A は B から(相対的に)計算可能、 B について再帰的とも称する)。集合 A が集合 B にチューリング還元可能であり、かつ、B が A にチューリング還元可能であるとき、これらの集合は同じチューリング次数(「決定不能性の次数」とも)を持つと言う。ある集合のチューリング次数は、その集合の計算不能な度合いの正確な尺度となる。