チューリング還元
あらゆる集合は、その補集合とチューリング同値である。
あらゆる帰納的集合は他のあらゆる帰納的集合にチューリング還元可能である。これらの集合は神託なしで計算可能であるため、これらは神託を無視した神託機械で計算可能である。
関係 ≤ T {\displaystyle \leq _{T}} は推移的であり、 A ≤ T B {\displaystyle A\leq _{T}B} でかつ B ≤ T C {\displaystyle B\leq _{T}C} であるとき A ≤ T C {\displaystyle A\leq _{T}C} である。さらに A ≤ A {\displaystyle A\leq A} は全ての集合 A で成り立つので、関係 ≤ T {\displaystyle \leq _{T}} は擬順序関係である。
インデックス e のチューリングマシンが停止する入力値を W e {\displaystyle W_{e}} とする。ここで集合 A = { e ∣ e ∈ W e } {\displaystyle A=\{e\mid e\in W_{e}\}} と B = { ( e , n ) ∣ n ∈ W e } {\displaystyle B=\{(e,n)\mid n\in W_{e}\}} はチューリング同値である( ( e , n ) {\displaystyle (e,n)} は対関数)。 A ≤ T B {\displaystyle A\leq _{T}B} という還元は、 e ∈ A ⇔ ( e , e ) ∈ B {\displaystyle e\in A\Leftrightarrow (e,e)\in B} から導かれる。
チューリング還元(チューリングかんげん、英: Turing reduction)は、計算量理論における還元の一種である。アラン・チューリングの名がつけられた還元であり、問題 A が問題 B にチューリング還元されるとは、B が容易に解けると仮定したときに A が容易に解けることを意味する(Rogers 1967、Soare 1987)。より厳密に言えば、B を神託として備えた神託機械によってAが計算可能であることである。チューリング還元は決定問題にも関数問題にも適用できる。
A から B へのチューリング還元が存在するとき、B を解くあらゆるアルゴリズムは A を解くアルゴリズムを作成するのに使うことが可能である。これは、 A を計算する神託機械が B に関する神託を質問する箇所に B のアルゴリズムを挿入することで実現される。しかし、この神託機械は何回も神託を訊ねる可能性があり、A のアルゴリズムは時間的にも空間的にも B のアルゴリズムよりも計算資源を多く必要とする可能性がある。
アラン・チューリング(1939年)は、神託機械を用いて相対計算可能性(当時は相対還元可能性と称していた)に初めて形式的な定義を与えた。1943年と1952年、スティーヴン・コール・クリーネは同様の概念を帰納的関数を用いて定義した。1944年、エミール・ポストはこの概念を表すのに初めて「チューリング還元可能性(Turing reducibility)」という用語を使った。