還元（計算可能性理論）

計算可能性理論では、多くの還元関係（還元、還元可能性、還元可能性の概念とも呼ばれる）が研究されている。それらは、与えられた集合に対して、${\displaystyle A}$そして${\displaystyle B}$自然数の場合、メンバーシップを決定する方法を効果的に変換することは可能でしょうか。${\displaystyle B}$メンバーシップを決定する方法に${\displaystyle A}$この質問に対する答えが肯定的な場合、${\displaystyle A}$還元可能であると言われている${\displaystyle B}$。

還元可能性の概念の研究は、決定問題の研究に触発されている。多くの還元可能性の概念において、計算不可能な集合が集合に還元可能である場合、${\displaystyle A}$それから${\displaystyle A}$計算不可能でなければならない。これは、多くの集合が計算不可能であることを証明するための強力な手法となる。

還元可能性関係とは、自然数の集合上の二項関係であり、

• 反射律：すべての集合はそれ自身に還元可能である。
• 推移的:集合が${\displaystyle A}$集合に還元可能${\displaystyle B}$そして${\displaystyle B}$集合に還元可能${\displaystyle C}$それから${\displaystyle A}$還元可能${\displaystyle C}$。

これら2つの性質は、還元可能性が自然数の冪集合上の前順序であることを示唆している。しかし、すべての前順序が還元可能性の概念として研究されているわけではない。計算可能性理論で研究されている概念は、非形式的な性質を持ち、${\displaystyle A}$還元可能${\displaystyle B}$（おそらく非効果的な）意思決定手続きが${\displaystyle B}$意思決定手続きに効果的に変換できる${\displaystyle A}$異なる還元関係は、そのような変換プロセスで使用できる方法が異なる。

最も基本的な還元可能性の概念はチューリング還元可能性である。${\displaystyle A}$自然数の集合はチューリングに還元可能か${\displaystyle B}$オラクルチューリングマシンが存在し、それを実行すると${\displaystyle B}$オラクルセットとして、指示関数（特性関数）を計算します。${\displaystyle A}$同等に、${\displaystyle A}$チューリングは還元可能か${\displaystyle B}$指標関数を計算するアルゴリズムが存在する場合に限り、${\displaystyle A}$ただし、アルゴリズムには「Is${\displaystyle n}$で${\displaystyle B}$？。

チューリング還元可能性は、他の還元可能性の概念を分ける境界線となる。なぜなら、チャーチ＝チューリングのテーゼによれば、チューリング還元可能性は最も一般的で有効な還元可能性関係だからである。チューリング還元可能性を含意する還元可能性関係は強い還元可能性として知られるようになり、チューリング還元可能性によって含意される還元可能性関係は弱い還元可能性と呼ばれる。 言い換えれば、強い還元可能性関係とは、その次数がチューリング次数よりも細かい同値関係を形成する関係であり、弱い還元可能性関係とは、その次数がチューリング同値関係よりも粗い同値関係を形成する関係である。

強い還元可能性には以下が含まれる

• 一対一還元性：${\displaystyle A}$は 1-1 還元可能${\displaystyle B}$計算可能な1対1関数が存在する場合${\displaystyle f}$と${\displaystyle A(x)=B(f(x))}$すべての人々のために${\displaystyle x}$。
• 多対一還元性：${\displaystyle A}$多対一は${\displaystyle B}$計算可能な関数が存在する場合${\displaystyle f}$と${\displaystyle A(x)=B(f(x))}$すべての人々のために${\displaystyle x}$。
• 真理値表は簡約可能：${\displaystyle A}$真理値表は${\displaystyle B}$もし${\displaystyle A}$チューリングは還元可能か${\displaystyle B}$単一の（オラクル）チューリングマシンを介して、すべてのオラクルに対する全体関数を生成する。
• 弱い真理値表還元可能:${\displaystyle A}$弱い真理値表は${\displaystyle B}$チューリング還元がある場合${\displaystyle B}$に${\displaystyle A}$計算可能な関数${\displaystyle f}$それは使用を制限する。${\displaystyle A}$真理値表は${\displaystyle B}$、${\displaystyle A}$弱真理値表は、${\displaystyle B}$なぜなら、すべてのオラクルのツリー全体にわたる最大使用量を考慮することで、使用量の計算可能な上限を構築できるからであり、これは、すべてのオラクルに対して削減が完全である場合に存在する。
• 正の還元可能値:${\displaystyle A}$正に還元可能${\displaystyle B}$かつその場合に限り${\displaystyle A}$真理値表は${\displaystyle B}$すべての${\displaystyle x}$原子の形式からなる式${\displaystyle B(0),B(1),...}$これらの原子は and と or によって結合され、${\displaystyle a}$そして${\displaystyle b}$1 の場合${\displaystyle a=1}$そして${\displaystyle b=1}$等々。
• 列挙の還元可能性：正の還元可能性に似ており、列挙可能性の有効な手順に関連する。${\displaystyle A}$に${\displaystyle B}$。
• 選言的還元可能: 正の還元可能と同様だが、ORのみが許容されるという追加の制約がある。
• 連言的還元可能性：正の還元可能性と同様だが、andのみが許容されるという追加の制約がある。
• 線形還元性: 正の還元性に似ているが、すべての原子が次の形式であるという制約がある${\displaystyle B(n)}$排他的論理和で結合されます。言い換えれば、${\displaystyle A}$線形還元可能${\displaystyle B}$計算可能な関数が各に対して計算する場合に限る${\displaystyle x}$有限集合${\displaystyle F(x)}$明示的な数値リストとして与えられ、${\displaystyle x\in A}$かつその場合に限り${\displaystyle F(x)}$奇数個の要素を含む${\displaystyle B}$。

これらの多くはポスト（1944）によって導入された。ポストは、停止問題をチューリング還元できないような、計算不可能で計算可能な列挙可能な集合を探していた。1944年当時、彼はそのような集合を構築できなかったため、代わりに彼が導入した様々な還元可能性に関する類似の問題に取り組んだ。これらの還元可能性はその後多くの研究の対象となり、それらの間の多くの関係が明らかになっている。

チューリング還元可能性は最も一般的で有効な還元可能性ですが、より弱い還元可能性関係も一般的に研究されています。これらの還元可能性は、算術または集合論上の集合の相対的な定義可能性に関連しています。それらには以下が含まれます。

• 算術的還元可能性：集合${\displaystyle A}$集合内で算術的である${\displaystyle B}$もし${\displaystyle A}$は、追加の述語を持つペアノ算術の標準モデル上で定義可能である。${\displaystyle B}$。同様に、ポストの定理によれば、Aは算術的である。${\displaystyle B}$かつその場合に限り${\displaystyle A}$チューリングは還元可能か${\displaystyle B^{(n)}}$、${\displaystyle n}$thチューリングジャンプ${\displaystyle B}$ある自然数に対して${\displaystyle n}$算術的階層は、算術的還元可能性のより詳細な分類を提供する。
• 超算術的還元可能性：集合${\displaystyle A}$集合内で超算術的である${\displaystyle B}$もし${\displaystyle A}$は${\displaystyle \Delta _{1}^{1}}$定義可能（分析階層を参照）Peano算術の標準モデル上で述語を持つ${\displaystyle B}$同等に、${\displaystyle A}$超算術的である${\displaystyle B}$かつその場合に限り${\displaystyle A}$チューリングは還元可能か$\displaystyle B^{(\alpha )}}$、${\displaystyle \alpha }$thチューリングジャンプ${\displaystyle B}$一部の人にとって${\displaystyle B}$再帰的順序数${\displaystyle \alpha }$。
• 相対的構成可能性：集合${\displaystyle A}$集合から比較的構築可能${\displaystyle B}$もし${\displaystyle A}$は${\displaystyle L(B)}$ZFC集合論の最小推移モデルには、${\displaystyle B}$そしてすべての序数。

• スタンフォード哲学百科事典：再帰関数