チューリング還元

チューリング還元（チューリングかんげん、英: 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つの集合 $A,B\subseteq \mathbb {N}$ に対して、$A$ が $B$ にチューリング還元可能（Turing reducible）であるとは、B に関する神託を与えられた神託機械を使って Aの特性関数を計算可能であることをいう。これを

$A\leq _{T}B$

と書く。 他にも、A は B-帰納的（B-recursive）または B-計算可能（B-computable）であるともいう。

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

$A$ が $B$ にチューリング同値（Turing equivalent）であることを $A\equiv _{T}B$ で表し、$A\leq _{T}B$ と $B\leq _{T}A$ が共に成り立つ。チューリング同値な集合の同値類をチューリング次数（Turing degree）と呼ぶ。集合 $X$ のチューリング次数を ${\textbf {deg}}(X)$ と記述する。

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

例

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

特性

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

より弱い還元

チューリング還元よりも弱い還元を作る一般的手法が2つ存在する。第一は神託の回数や方法を制限する手法である。

• 集合 A が B に多対一還元可能であるとは、要素 n が A に含まれるかどうかを示す関数 f があるとき、B に f(n) が含まれることをいう。このような関数でチューリング還元を生成することもできる（f(n)を計算し、その結果がBに含まれるか神託を訊き、結果を翻訳する）。
• 真理値表還元では、神託を一度に全部訊き、それらの解にブール関数（真理値表）を適用することで最終的な解が得られる。

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

より強い還元

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

参考文献

• M. Davis, ed., 1965. The Undecidable—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.

外部リンク

• NIST Dictionary of Algorithms and Data Structures: Turing reduction