チューリング還元

計算可能性理論では、決定問題から決定問題へのチューリング還元は、の神託が与えられた場合に問題 を決定する神託マシンです(Rogers 1967、Soare 1987)。 これは、を解くためのサブルーチンが利用可能であれば、を解くために使用できるアルゴリズムとして理解できます。 この概念は、関数問題にも同様に適用できます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

からへのチューリング還元が存在する場合、^[a]のすべてのアルゴリズムを使用して、のアルゴリズムを作成できます。そのためには、を計算するオラクルマシンが についてオラクルに問い合わせる各場所に のアルゴリズムを挿入します。ただし、オラクルマシンはオラクルに何度も問い合わせる可能性があるため、結果として得られるアルゴリズムは、 のアルゴリズムや を計算するオラクルマシンよりも漸近的に時間がかかる可能性があります。オラクルマシンが多項式時間で実行するチューリング還元は、クック還元と呼ばれます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\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 {\mathcal {X}}}$${\displaystyle {\mathcal {X}}}$

が、インデックスeのチューリングマシンが停止する入力値の集合を表すとします。このとき、集合と はチューリング等価です (ここで は有効なペアリング関数を表します)。という事実を使用して、 を示す簡約を構築できます。 ペア が与えられた場合、 s _mn定理を使用して新しいインデックスを構築できます。これにより、 によってコード化されたプログラムはその入力を無視し、入力nでのインデックスeのマシンの計算をシミュレートするだけです。特に、インデックス のマシンは、すべての入力で停止するか、入力なしで停止します。 したがって、すべてのeおよびnに対して成り立ちます。関数i は計算可能であるため、 が示されます。 ここで示す簡約は、チューリング簡約だけでなく、以下で説明する多対一簡約でもあります。 ${\displaystyle W_{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)}$${\displaystyle i(e,n)}$${\displaystyle i(e,n)}$${\displaystyle i(e,n)\in A\Leftrightarrow (e,n)\in B}$${\displaystyle B\leq _{T}A}$

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

集合から集合へのすべての簡約では、 の単一の要素が に含まれるかどうかを有限回のステップで判定する必要があるため、集合 のメンバーシップの照会は有限回しか実行できません。の 1 ビットを計算するために使用される集合に関する情報の量について説明する場合、これは関数の使用によって明確になります。正式には、簡約の使用とは、 のメンバーシップを判定する際に、各自然数を、その集合のメンバーシップが簡約によって照会された最大の自然数に送信する関数です。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle n}$${\displaystyle m}$${\displaystyle B}$${\displaystyle n}$${\displaystyle A}$

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

• 集合は、が にある場合にのみ要素が にあるような全計算可能関数が存在する場合、に多対一還元可能です。このような関数を使用して、チューリング還元を生成できます ( を計算し、オラクルに対してクエリを実行し、結果を解釈することによって)。${\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年。『 The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions 』、レイヴン、ニューヨーク。再版、ドーバー、2004年。ISBN 0-486-43228-9 。
• SC Kleene、1952年。『メタ数学入門』アムステルダム：北ホラント。
• SC Kleene と EL Post、1954 年。「再帰的不解の次数の上半格子」。Annals of Mathematics v. 2 n. 59、379–407。
• Post, EL (1944). 「再帰的に列挙可能な正の整数の集合とその決定問題」( PDF ) .アメリカ数学会誌. 50 (5): 284– 316. doi : 10.1090/s0002-9904-1944-08111-1 . 2015-12-17に閲覧。
• A. チューリング、1939 年。「序数に基づく論理体系」。ロンドン数学会紀要、第 2 巻第 45 号、161 ～ 228 ページ。M. デイビス編「The Undecidable」に再録、1965 年。
• H. Rogers、1967年。「再帰関数と実効計算可能性の理論」McGraw-Hill。
• R. Soare、1987年。「再帰的に列挙可能な集合と次数」、Springer。
• デイビス、マーティン(2006 年 11 月)。「チューリング還元性とは?」(PDF)。アメリカ数学会報。53 (10): 1218– 1219。2008年 1 月 16 日閲覧。

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