チューリング還元（チューリングかんげん、）は、計算量理論における還元の一種である。アラン・チューリングの名がつけられた還元であり、問題 "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）」という用語を使った。2つの集合 formula_1 に対して、formula_2 が formula_3 にチューリング還元可能（Turing reducible）であるとは、"B" に関する神託を与えられた神託機械を使って "A"の特性関数を計算可能であることをいう。これをと書く。他にも、"A" は B"-帰納的（B-recursive）または B"-計算可能（B-computable）であるともいう。"B"のオラクルを持つ神託機械があり、"A" を定義域とする部分関数を計算可能であるとき、"A" を B"-帰納的可算（B-recursively enumerable）または B"-計算可枚挙（B-computably enumerable）であるという。formula_2 が formula_3 にチューリング同値（Turing equivalent）であることを formula_7 で表し、formula_4 と formula_9 が共に成り立つ。チューリング同値な集合の同値類をチューリング次数（Turing degree）と呼ぶ。集合 formula_10 のチューリング次数を formula_11 と記述する。formula_12 という集合があるとき、全ての formula_13 について formula_14 なら、集合 formula_15 を formula_16 に対してチューリング困難（Turing hard）であるという。加えて formula_17 であるとき、formula_2 を formula_16 に対してチューリング完全（Turing complete）であるという。インデックス "e" のチューリングマシンが停止する入力値を formula_20 とする。ここで集合 formula_21 と formula_22 はチューリング同値である（formula_23 は対関数）。formula_4 という還元は、formula_25 から導かれる。対 formula_23 からクリーネのSmn定理により新たなインデックス formula_27 が構築でき、formula_27 を実装したプログラムは入力を無視してインデックス "e" のマシンに入力 "n" を与えたときの計算をシミュレートする。従ってインデックス formula_27 の機械はあらゆる入力で停止するか、無入力で停止する。つまり、formula_30 は全ての "e" と "n" について成り立つ。関数 "i" は計算可能なので、formula_9 となる。このような還元はチューリング還元でもあるが、同時に「多対一還元」でもある（後述）。チューリング還元よりも弱い還元を作る一般的手法が2つ存在する。第一は神託の回数や方法を制限する手法である。第二の手法はチューリング還元を実装するプログラムが使用する計算資源を制限する手法である。これはPのような計算量に関する研究で重要である。集合 "A" が "B" に多項式時間チューリング還元可能であるとは、多項式時間で "A" を "B" にチューリング還元できることをいう。対数領域還元などの概念も同様である。チャーチ＝チューリングのテーゼによれば、チューリング還元は実効的に計算可能な還元の最も汎用的な形式である。それにも関わらず、様々なより強い還元が検討されている。集合 "A" が集合 "B" をパラメータとしてペアノの公理を適用した式で定義可能な場合、"A" を "B" の中で算術的であるという。帰納順序 α が存在し、"A" が formula_41 （つまり、"B" のα回のチューリングジャンプ）から計算可能である場合、集合 "A" を "B" の中で超算術的（hyperarithmetical）であるという。相対構成可能性は集合論における重要な還元可能性の概念である。

出典:wikipedia