チューリング還元
チューリング同値な集合の同値類をチューリング次数(Turing degree)と呼ぶ。集合 X {\displaystyle X} のチューリング次数を deg ( X ) {\displaystyle {\textbf {deg}}(X)} と記述する。
X ⊆ P ( N ) {\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )} という集合があるとき、全ての X ∈ X {\displaystyle X\in {\mathcal {X}}} について X ≤ T A {\displaystyle X\leq _{T}A} なら、集合 A ⊆ N {\displaystyle A\subseteq \mathbb {N} } を X {\displaystyle {\mathcal {X}}} に対してチューリング困難(Turing hard)であるという。加えて A ∈ X {\displaystyle A\in {\mathcal {X}}} であるとき、 A {\displaystyle A} を X {\displaystyle {\mathcal {X}}} に対してチューリング完全(Turing complete)であるという。