再帰理論
しかし、結局ポストは中間のチューリング次数を持つ帰納的可算集合が存在するかという主問題は未解決のまま残し、これはポストの問題(en)と呼ばれるようになった。10年後の1954年、クリーネとポストは計算可能集合と停止問題の間のチューリング次数が存在することは示せたが、そのチューリング次数に属する帰納的可算集合が存在するかは示せなかった。その直後、Friedberg と Muchnik がそれぞれ独立に中間次数の帰納的可算集合が存在することを示し、ポストの問題を解決した。この画期的な成果により、帰納的可算集合のチューリング次数に関する広範な研究が始まり、非常に複雑かつ自明でない構造の存在が明らかになった。
帰納的可算でない集合は非可算個存在しており、一般の集合のチューリング次数に関する研究も、帰納的可算なチューリング次数に関する研究と同様に、再帰理論における主要な研究対象である。様々な特定の次数が構成されている。
hyperimmune-free degrees:この次数から相対的に計算可能な関数は(非相対化された)計算可能関数によって majorize される
high degrees:この次数からは(全ての計算可能関数 g を支配するような)関数 f が相対的に計算可能。
さらに、Osherson は帰納的推論における「学習者; learner」という用語を「科学者; scientist」に代えることを提案し、著書 Systems that learn を改版するときに、そのように用語を変更した。
Rogers (1967) は、再帰理論の鍵となる特性は、その結果や構造が自然数への計算可能な全単射において不変である点だとした。すなわち、計算可能な全単射では集合の各要素を単に改名するだけで、その構造は変化させない。ユークリッド平面での回転が幾何学的形状を変化させないのと同じである。2つの無限の計算可能集合は計算可能な全単射でリンクされるので、これは全ての無限な計算可能集合に当てはまる(有限の計算可能集合については自明である)。Rogers によれば、再帰理論が対象とする集合は、計算可能な全単射で自然数と対応できるような計算不可能集合である。