チューリング還元
2つの集合 A , B ⊆ N {\displaystyle A,B\subseteq \mathbb {N} } に対して、 A {\displaystyle A} が B {\displaystyle B} にチューリング還元可能(Turing reducible)であるとは、B に関する神託を与えられた神託機械を使って Aの特性関数を計算可能であることをいう。これを
A ≤ T B {\displaystyle A\leq _{T}B}
と書く。 他にも、A は B-帰納的(B-recursive)または B-計算可能(B-computable)であるともいう。
Bのオラクルを持つ神託機械があり、A を定義域とする部分関数を計算可能であるとき、A を B-帰納的可算(B-recursively enumerable)または B-計算可枚挙(B-computably enumerable)であるという。
A {\displaystyle A} が B {\displaystyle B} にチューリング同値(Turing equivalent)であることを A ≡ T B {\displaystyle A\equiv _{T}B} で表し、 A ≤ T B {\displaystyle A\leq _{T}B} と B ≤ T A {\displaystyle B\leq _{T}A} が共に成り立つ。