チューリング還元

チューリング還元（チューリングかんげん、英: 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）」という用語を使った。