チューリング還元のソースを表示

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

== 定義 ==
2つの集合 <math>A,B \subseteq \mathbb{N}</math> に対して、<math>A</math> が <math>B</math> に'''チューリング還元可能'''（Turing reducible）であるとは、''B'' に関する神託を与えられた[[神託機械]]を使って ''A''の特性関数を計算可能であることをいう。これを
:<math>A \leq_T B</math> 
と書く。
他にも、''A'' は '''''B''-帰納的'''（B-recursive）または '''''B''-計算可能'''（B-computable）であるともいう。

''B''のオラクルを持つ神託機械があり、''A'' を[[定義域]]とする部分関数を計算可能であるとき、''A'' を '''''B''-[[帰納的可算集合|帰納的可算]]'''（B-recursively enumerable）または '''''B''-計算可枚挙'''（B-computably enumerable）であるという。

<math>A</math> が <math>B</math> に'''チューリング同値'''（Turing equivalent）であることを <math>A \equiv_T B</math> で表し、<math>A \leq_T B</math> と <math>B \leq_T A</math> が共に成り立つ。チューリング同値な集合の[[同値類]]を'''[[チューリング次数]]'''（Turing degree）と呼ぶ。集合 <math>X</math> のチューリング次数を <math>\textbf{deg}(X)</math> と記述する。

<math>\mathcal{X} \subseteq \mathcal{P}(\mathbb{N})</math> という集合があるとき、全ての <math>X \in \mathcal{X}</math> について <math>X \leq_T A</math> なら、集合 <math>A \subseteq \mathbb{N}</math> を <math>\mathcal{X}</math> に対して'''チューリング困難'''（Turing hard）であるという。加えて <math>A \in \mathcal{X}</math> であるとき、<math>A</math> を <math>\mathcal{X}</math> に対して'''チューリング完全'''（Turing complete）であるという。

==例==
インデックス ''e'' のチューリングマシンが停止する入力値を <math>W_e</math> とする。ここで集合 <math>A = \{e \mid e \in W_e\}</math> と <math>B = \{(e,n) \mid n \in W_e \}</math> はチューリング同値である（<math>(e,n)</math> は[[対関数]]）。<math>A \leq_T B</math> という還元は、<math>e \in A \Leftrightarrow (e,e) \in B</math> から導かれる。対 <math>(e,n)</math> からクリーネの[[Smn定理]]により新たなインデックス <math>i(e,n)</math> が構築でき、<math>i(e,n)</math> を実装したプログラムは入力を無視してインデックス ''e'' のマシンに入力 ''n'' を与えたときの計算をシミュレートする。従ってインデックス <math>i(e,n)</math> の機械はあらゆる入力で停止するか、無入力で停止する。つまり、<math>i(e,n) \in A \Leftrightarrow (e,n) \in B</math> は全ての ''e'' と ''n'' について成り立つ。関数 ''i'' は計算可能なので、<math>B \leq_T A</math> となる。このような還元はチューリング還元でもあるが、同時に「多対一還元」でもある（後述）。

== 特性 ==
* あらゆる集合は、その補集合とチューリング同値である。
* あらゆる[[帰納的集合]]は他のあらゆる帰納的集合にチューリング還元可能である。これらの集合は神託なしで計算可能であるため、これらは神託を無視した神託機械で計算可能である。
* 関係 <math>\leq_T</math> は推移的であり、<math>A \leq_T B</math> でかつ <math>B \leq_T C</math> であるとき <math>A \leq_T C</math> である。さらに <math>A \leq A</math> は全ての集合 ''A'' で成り立つので、関係 <math>\leq_T</math> は擬順序関係である。
* ''A'' が ''B'' にチューリング還元不可能で、同時に ''B'' が ''A'' にチューリング還元不可能な集合の対 <math>(A,B)</math> が存在する。従って、<math>\leq_T</math> は線形な順序関係ではない。
* <math>\leq_T</math> による集合の列では[[無限降下法|無限降下]]が可能である。従って、この関係は整礎（well-founded）ではない。
* あらゆる集合は自身のチューリングジャンプにチューリング還元可能であるが、その集合のチューリングジャンプは本来の集合にチューリング還元できない（注:チューリングジャンプとは、ある集合について、その集合の神託機械で求められない集合を生成する演算子またはその演算子で得られる集合。つまり、この一文は単にチューリングジャンプの性質を述べているに過ぎない）。

== より弱い還元 ==
チューリング還元よりも弱い還元を作る一般的手法が2つ存在する。第一は神託の回数や方法を制限する手法である。
* 集合 ''A'' が ''B'' に'''[[多対一還元|多対一還元可能]]'''であるとは、要素 ''n'' が ''A'' に含まれるかどうかを示す関数 ''f'' があるとき、''B'' に ''f''(''n'') が含まれることをいう。このような関数でチューリング還元を生成することもできる（''f''(''n'')を計算し、その結果が''B''に含まれるか神託を訊き、結果を翻訳する）。
* '''[[真理値表還元]]'''では、神託を一度に全部訊き、それらの解にブール関数（真理値表）を適用することで最終的な解が得られる。

第二の手法はチューリング還元を実装するプログラムが使用する計算資源を制限する手法である。これは[[P (計算量理論)|'''P''']]のような計算量に関する研究で重要である。集合 ''A'' が ''B'' に'''[[多項式時間変換|多項式時間チューリング還元可能]]'''であるとは、多項式時間で ''A'' を ''B'' にチューリング還元できることをいう。'''[[対数領域還元]]'''などの概念も同様である。

== より強い還元 ==
[[チャーチ＝チューリングのテーゼ]]によれば、チューリング還元は実効的に計算可能な還元の最も汎用的な形式である。それにも関わらず、様々なより強い還元が検討されている。集合 ''A'' が集合 ''B'' をパラメータとして[[ペアノの公理]]を適用した式で定義可能な場合、''A'' を ''B'' の中で算術的であるという。帰納順序 &alpha; が存在し、''A'' が <math>B^{(\alpha)}</math> （つまり、''B'' の&alpha;回のチューリングジャンプ）から計算可能である場合、集合 ''A'' を ''B'' の中で超算術的（hyperarithmetical）であるという。'''[[構成可能集合|相対構成可能性]]'''は集合論における重要な還元可能性の概念である。

==参考文献==
* M. Davis, ed., 1965.  ''The Undecidable&mdash;Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions'', Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9. 
* S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland.
* S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability". ''Annals of Mathematics'' v. 2 n. 59, 379--407.
* E. Post, 1944. "Recursively enumerable sets of positive integers and their decision problems." Bulletin of the American Mathematical Society, v. 50, pp. 284-316.  Reprinted in "The Undecidable", M. Davis ed., 1965.  
* A. Turing, 1939. "Systems of logic based on ordinals." ''Proceedings of the London Mathematics Society'', ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965. 
* H. Rogers, 1967. Theory of recursive functions and effective computability. McGraw-Hill.
* R. Soare, 1987. Recursively enumerable sets and degrees, Springer. 

==外部リンク==
* [http://www.nist.gov/dads/HTML/turingredctn.html NIST Dictionary of Algorithms and Data Structures: Turing reduction]

{{Normdaten}}
{{DEFAULTSORT:ちゆうりんくかんけん}}
[[Category:還元 (計算複雑性理論)]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]
[[Category:アラン・チューリング]]