チューリング還元

計算可能性理論において、決定問題からのチューリング還元${\displaystyle A}$意思決定問題へ${\displaystyle B}$問題を決定するオラクルマシンです${\displaystyle A}$神託が与えられた${\displaystyle B}$（ロジャース 1967、ソアレ 1987）有限ステップで解くことができるアルゴリズムとして理解できます。${\displaystyle A}$解決するためのサブルーチンにアクセスできれば${\displaystyle B}$この概念は関数問題にも同様に応用できる。

チューリング還元から${\displaystyle A}$に${\displaystyle B}$存在する場合、すべてのアルゴリズム${\displaystyle B}$^{[ a ] は}、アルゴリズムを生成するために使用できます。${\displaystyle A}$アルゴリズムを挿入することにより${\displaystyle B}$Oracleマシンコンピューティングが稼働している各場所で${\displaystyle A}$オラクルに問い合わせる${\displaystyle B}$しかし、オラクルマシンはオラクルに何度も問い合わせる可能性があるため、結果として得られるアルゴリズムは、漸近的には、どちらのアルゴリズムよりも多くの時間を必要とする可能性があります。${\displaystyle B}$またはOracleマシンコンピューティング${\displaystyle A}$オラクルマシンが多項式時間で実行されるチューリング還元は、クック還元として知られています。

相対的計算可能性（当時は相対的還元可能性と呼ばれていた）の最初の正式な定義は、 1939年にアラン・チューリングによってオラクルマシンを用いて与えられた。その後、1943年と1952年にスティーブン・クリーネが再帰関数を用いて同等の概念を定義した。1944年にはエミール・ポストがこの概念を指すのに「チューリング還元可能性」という用語を用いた。

2つの集合が与えられた場合${\displaystyle A,B\subseteq \mathbb {N} }$自然数については、${\displaystyle A}$チューリングは還元可能か${\displaystyle B}$そして書く

${\displaystyle A\leq _{T}B}$

オラクルBで実行したときにAの特性関数を計算するオラクル マシンが存在する場合に限り、 AはB再帰的かつB計算可能であるとも言います。

オラクルBで実行したときにドメインAの部分関数を計算するオラクル マシンが存在する場合、A はB再帰的に列挙可能かつB計算可能列挙可能であると言われます。

私たちは言う${\displaystyle A}$チューリングは​${\displaystyle B}$そして書く${\displaystyle A\equiv _{T}B\,}$両方${\displaystyle A\leq _{T}B}$ そして${\displaystyle B\leq _{T}A.}$チューリング同値集合の同値類はチューリング次数と呼ばれます。集合のチューリング次数は${\displaystyle X}$書かれている${\displaystyle {\textbf {度}}(X)}$。

集合が与えられた${\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )}$、セット${\displaystyle A\subseteq \mathbb {N} }$チューリング困難と呼ばれる${\displaystyle {\mathcal {X}}}$もし${\displaystyle X\leq _{T}A}$ すべての人々のために${\displaystyle X\in {\mathcal {X}}}$加えて${\displaystyle A\in {\mathcal {X}}}$それから${\displaystyle A}$はチューリング完全と呼ばれます${\displaystyle {\mathcal {X}}}$。

させて${\displaystyle W_{e}}$インデックスeを持つチューリングマシンが停止する入力値の集合を表す。すると、集合は${\displaystyle A=\{e\mid e\in W_{e}\}}$そして${\displaystyle B=\{(e,n)\mid n\in W_{e}\}}$チューリング等価（ここでは）${\displaystyle (-,-)}$は有効なペアリング関数を表します。${\displaystyle A\leq _{T}B}$事実を利用して構築することができる${\displaystyle e\in A\Leftrightarrow (e,e)\in B}$ペアが与えられた場合${\displaystyle (e,n)}$新しいインデックス${\displaystyle i(e,n)}$S m n  定理を用いて構築することができ、それによってコード化されたプログラムは${\displaystyle i(e,n)}$入力を無視し、入力nに対するインデックスeのマシンの計算をシミュレートするだけです。特に、インデックス e のマシンは${\displaystyle i(e,n)}$入力があるたびに停止するか、入力がないときに停止するかのどちらかです。したがって${\displaystyle i(e,n)\in A\Leftrightarrow (e,n)\in B}$すべてのeとnに対して成り立つ。関数iは計算可能であるため、これは次のことを示している。${\displaystyle B\leq _{T}A}$ここで提示する還元は、チューリング還元だけでなく、後述する多対一還元も含む。

• すべての集合は、その補集合とチューリング同値である。
• すべての計算可能集合は、他のすべての集合にチューリング還元可能である。任意の計算可能集合はオラクルなしで計算できるため、与えられたオラクルを無視するオラクルマシンによって計算することができる。
• 関係$\displaystyle \leq _{T}}$推移的である:${\displaystyle A\leq _{T}B}$そして${\displaystyle B\leq _{T}C}$それから${\displaystyle A\leq _{T}C}$。 さらに、${\displaystyle A\leq _{T}A}$はすべての集合Aに対して成り立ち、したがって関係は$\displaystyle \leq _{T}}$これは予約注文です（部分注文ではありません。${\displaystyle A\leq _{T}B}$そして${\displaystyle B\leq _{T}A}$必ずしも意味するものではない${\displaystyle A=B}$)
• セットのペアがあります${\displaystyle (A,B)}$AはBにチューリング還元可能ではなく、BもAにチューリング還元可能ではない。 したがって$\displaystyle \leq _{T}}$全順序ではありません。
• 集合の減少列は無限に存在する$\displaystyle \leq _{T}}$したがって、この関係は根拠が十分ではない。
• すべての集合は、それ自身のチューリングジャンプにチューリング還元可能であるが、集合のチューリングジャンプは、元の集合にチューリング還元可能ではない。

集合からのあらゆる削減は${\displaystyle A}$セットへ${\displaystyle B}$単一の要素が${\displaystyle A}$有限回のステップで、集合への所属に関するクエリを有限回しか実行できない。${\displaystyle B}$セットに関する情報の量${\displaystyle B}$1ビットを計算するために使用される${\displaystyle A}$議論されているように、これは使用関数によって正確になります。形式的には、還元の使用は、各自然数を${\displaystyle n}$最大の自然数${\displaystyle m}$そのセットのメンバー${\displaystyle B}$メンバーシップを決定する際に削減について質問されました${\displaystyle n}$で${\displaystyle A}$。

チューリング還元可能性よりも強力な還元を生成する一般的な方法は2つあります。1つ目は、オラクルクエリの数と方法を制限することです。

• セット${\displaystyle A}$多対一は${\displaystyle B}$計算可能な関数が全て存在する場合${\displaystyle f}$要素${\displaystyle n}$は${\displaystyle A}$かつその場合に限り${\displaystyle f(n)}$は${\displaystyle B}$このような関数は、チューリング還元を生成するために使用できます（計算によって）。${\displaystyle f(n)}$（オラクルに問い合わせを行い、その結果を解釈する）。
• 真理値表還元または弱真理値表還元は、すべてのオラクルクエリを同時に提示する必要があります。真理値表還元では、還元はブール関数（真理値表）も提供し、クエリに対する回答が与えられると、還元の最終的な回答が生成されます。弱真理値表還元では、還元はオラクルの回答を、与えられた回答に応じて（ただしオラクル自体は使用せずに）さらに計算するための基礎として使用します。言い換えれば、弱真理値表還元とは、還元の使用が計算可能な関数によって制限される還元のことです。このため、弱真理値表還元は「制限付きチューリング」還元と呼ばれることもあります。

より強い還元可能性の概念を生み出す2つ目の方法は、チューリング還元を実行するプログラムが使用できる計算リソースを制限することです。還元の計算複雑性に対するこれらの制限は、 Pのような部分再帰クラスを研究する際に重要です。集合Aは、多項式時間で集合に還元可能です。${\displaystyle B}$チューリング還元が存在する場合${\displaystyle A}$に${\displaystyle B}$これは多項式時間で実行されます。対数空間削減の概念も同様です。

これらの還元は、同値類へのより詳細な区別を提供し、チューリング還元よりも厳しい要件を満たすという意味で、より強力である。したがって、このような還元を見つけるのはより困難である。同じ集合に対するチューリング還元が存在する場合でも、ある集合から別の集合への多対一還元を構築する方法がない場合もある。

チャーチ＝チューリングのテーゼによれば、チューリング還元は、実効的に計算可能な還元の最も一般的な形式である。しかしながら、より弱い還元も考慮される。${\displaystyle A}$算術的であると言われている${\displaystyle B}$もし${\displaystyle A}$はペアノ算術の式で定義可能であり、${\displaystyle B}$パラメータとして。${\displaystyle A}$超算術的である${\displaystyle B}$再帰的な順序数 がある場合${\displaystyle \alpha }$そのため${\displaystyle A}$から計算可能$\displaystyle B^{(\alpha )}}$α反復チューリングジャンプ${\displaystyle B}$相対的構成可能性の概念は、集合論における重要な還元可能性の概念である。

• コイの減少

• M. Davis編、1965 年。 『決定不能性―決定不能命題、解決不能問題、計算可能関数に関する基礎論文集』、Raven、ニューヨーク。再版、Dover、2004 年。ISBN 0-486-43228-9。
• S.C. クリーネ、1952年。『メタ数学入門』アムステルダム：ノースホランド出版。
• SC クリーネとEL ポスト、1954 年。「再帰的解不能性の次数の上半格子」。Annals of Mathematics v. 2 n. 59、379–407。
• Post, EL (1944). "正の整数の再帰的に列挙可能な集合とその決定問題" ( PDF ) . Bulletin of the American Mathematical Society . 50 (5): 284– 316. doi : 10.1090/s0002-9904-1944-08111-1 . 2015-12-17に取得.
• A. チューリング、1939年。「順序数に基づく論理体系」。ロンドン数学会紀要、第2シリーズ、第45巻、 161-228頁。M. デイビス編『決定不能性』、1965年に再録。
• H. ロジャース、1967年。『再帰関数と有効計算可能性の理論』マグロウヒル。
• R. Soare、1987年。再帰的に列挙可能な集合と次数、Springer。
• Davis, Martin (2006年11月) 「チューリング還元可能性とは何か？」(PDF)アメリカ数学会報53 (10): 1218–1219 2008年1月16日取得

• NISTアルゴリズムとデータ構造の辞書：チューリング還元
• ケンブリッジ大学、アンドリュー・ピッツ、トビアス・コーン：計算理論
• ジャン・ガリエ教授のホームページ