チューリング還元
チューリング還元（チューリングかんげん、）は、計算量理論における還元の一種である。アラン・チューリングの名がつけられた還元であり、問題 "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）」という用語を使った。