チューリング次数
チューリング次数の構造については大変多くの研究がある。以下に示す一覧は、知られている結果のごく一部を示すに過ぎない。一連の研究から得られた一つの一般的な結論は、チューリング次数の構造が極端に複雑だということである。
エミール・ポストは r.e.チューリング次数を研究し、0 と 0′の厳密に中間であるような r.e.次数は存在するか、と問うた。このような次数を構成する問題(または、それが不可能であることの証明)はポストの問題として知られるようになった。この問題は1950年代に Friedberg と Muchnik によって独立に解決され、そのような中間の r.e.次数が実在することが示された。彼らの証明方法は、r.e.次数を構成するための同じ新技法をそれぞれが導入したもので、これは優先度法として知られるようになった。今日、優先度法は r.e.集合について何らかの結果を得る際には主役となるテクニックである。
r.e.集合 X {\displaystyle X} を構成する上で、優先度法のアイディアは、 X {\displaystyle X} が満たさねばならない可算個の「要件」の列を作るというものである。 例えば、0 と 0′の中間である r.e.集合を作るには、全ての自然数 e {\displaystyle e} について要件 A e {\displaystyle A_{e}} と B e {\displaystyle B_{e}} を満たせば十分である。ここで、 A e {\displaystyle A_{e}} はインデクス e {\displaystyle e} が指す神託機械が X {\displaystyle X} から 0′ を計算できないという要件であり、 B e {\displaystyle B_{e}} はインデクス e {\displaystyle e} が指す(オラクルを持たない)チューリングマシンが X {\displaystyle X} を計算できないという要件である。