FriedbergとMuchnikによる文 – ウィキペディア

Posted on January 24, 2019 by lordneo

before-content-x4

FriedbergとMuchnikの文 は、リチャード・M・フリードバーグとアルバート・ムチニクによって互いに独立して1956/1957年に証明された予測可能性と数学的論理の理論の結果です。それは、間にある再帰的にリスト可能なチューリングの学位があると言います 0 と 0 ‘ 横たわっている。したがって、決定的ではない再帰的にリスト可能な数量がありますが、チューリングのチューリングを減らすという意味では、保持問題よりも簡単です。 FriedbergとMuchnikは、彼らの証拠のための新しい証拠手法を開発しました 優先方法 また 優先議論 知られており、予測可能性理論の重要な手法になりました。

after-content-x4

エミル・ポストは、1944年の作業でチューリングの学位を調べ、再帰的にリスト可能なチューリングの学位を尋ねました 0 と 0 ‘ 与えます。この質問は次のとおりでした Postschesの問題 知られています。 Postが定義しました 単純な量 そして、多くの1つの削減の下で、それらはより強力なチューリングの削減のためにこれを示すことができずに、決定的な量と保持問題の間で厳密にあることを示すことができます。 J.C.E. Dekkerは1954年に、これは単純な量であるため不可能であることを示しました 0 ‘ 与えます。 ^[初め]この問題は、1956/57年に、フリードバーグとムチニクによって、互いに独立して新しく開発された優先方法によって解決されました。 1986年、アントニン・クチェラは、優先順位の議論には必要ない新しいソリューションを公開しました。

Table of Contents

アイディア [ 編集 | ソーステキストを編集します ]

次の証拠は、2004年のクーパーの提示に続き、フリードバーグとムチニクの元の証拠に基づいています。

2つの再帰的に登録可能な量が同時にあります

{displaystyle a}

$A$ と

{displaystyle b}

$B$ 構築された、それぞれがチューリングを減らすことはできません：

{displaystyle anot leq _ {t} b}

$Anot leq _{T}B$ と

after-content-x4

{displaystyle bnot leq _ {t} a}

$Bnot leq _{T}A$ 。これらの条件が満たされている場合、文の声明が続きます。 if

{displaystyle a}

$A$ また

{displaystyle b}

$B$ 他の量に減らすことができれば決定的であり、パルプの問題に埋め込まれる可能性のあるすべての量を減らすことができるので、AとBは入ることができません 0 ‘ 横たわっている。

これらの要件は、要件の無限のリストによって保証されます。多分

{displaystyle phi _ {0}、phi _ {1}、dotsc}

${displaystyle Phi _{0},Phi _{1},dotsc }$ オラクルそびえ立つ機械の予測可能なリスト。次に、すべてのマシンにあります

{displaystyle phi _ {i}}

$Phi_i$ 2つの要件：

私は落ちる

{displaystyle r_ {2i}}

$R_{{2i}}$ 満たされており、の削減はありません

{displaystyle a}

$A$ の上

{displaystyle b}

$B$ そしてそれは適用されます

{displaystyle anot leq _ {t} b}

$Anot leq _{T}B$ 。アナログ金箔

{displaystyle bnot leq _ {t} a}

$Bnot leq _{T}A$ 、私は落ちる

{displaystyle r_ {2i+1}}

$R_{{2i+1}}$ 満たされています。

要件は彼らの後です 優先順位 それを注文しました

{displaystyle r_ {0}}

$R_{{0}}$ 最優先事項、

{displaystyle r_ {1}}

$R_{1}$ 2番目に高いなど

有限量の計算可能な結果があります

{displaystyle a_ {0} subseteq a_ {1} subseteq a_ {2} subseteq dotsb}}

${displaystyle A_{0}subseteq A_{1}subseteq A_{2}subseteq dotsb }$ と

{displaystyle b_ {0} Subseteq B_ {1} Subseteq B_ {2} Subseteq Dotsb}}

${displaystyle B_{0}subseteq B_{1}subseteq B_{2}subseteq dotsb }$ 構築されています。 AとBは、これらの結果の無限の関連性です。

{displaystyle a = bigcup _ {iin mathbb {n}} a_ {i}}}

$A=bigcup _{{iin mathbb{N} }}A_{i}$ と

{displaystyle b = bigcup _ {iin mathbb {n}} b_ {i}}

$B=bigcup _{{iin mathbb{N} }}B_{i}$ 。結果は予測可能であるため、彼らの関連はそうです

{displaystyle a}

$A$ と

{displaystyle b}

$B$ 再帰的にリスト可能。

そうです

{displaystyle a_ {0} = b_ {0} = emptySet}

$A_{0}=B_{0}=emptyset$ 。の中に

{displaystyleS+1}

$s+1$ – 建設のステップが消えます

{displaystyle a_ {s}}

$A_{s}$ と

{displaystyle b_ {s}}

$B_{s}$ 金額

{displaystyle a_ {s+1} supseteq a_ {s}}

$A_{{s+1}}supseteq A_{s}$ と

{displaystyle b_ {s+1} supseteq b_ {s}}

$B_{{s+1}}supseteq B_{s}$ 構築されています。建設はからです戦略受け入れられました。各要件には1つがあります ストラテジー それはこの要件を満たそうとします。

戦略 [ 編集 | ソーステキストを編集します ]

直感 [ 編集 | ソーステキストを編集します ]

すべての戦略

{displaystyle r_ {2i}}

$R_{{2i}}$ 不平等を強制する必要があります

{displaystyle aneq phi _ {i} ^ {b}}

$Aneq Phi _{i}^{B}$ 適用可能です。これには2つのオプションがあります。 目撃者

{displaystyle x}

$x$ に

{displaystyle a}

$A$ さらに、ではありません

{displaystyle phi _ {i}^}}}

$Phi _{i}^{B}$ 嘘、または彼女はそれを証人に強制する

{displaystyle x}

$x$ あきらめます

{displaystyle phi _ {i}^}}}

$Phi _{i}^{B}$ 嘘をつき、決して後にいません

{displaystyle a}

$A$ 手に入れた。 2つの困難があります。一方ではそうです

{displaystyle phi _ {i}^}}}

$Phi _{i}^{B}$ 常に完全な関数と質問ではありません

{displaystyle phi _ {i}^{b}（x）}

$Phi _{i}^{B}(x)$ したがって、未定です。これは、戦略が

{displaystyleS}

$s$ – 最初の構造のみのステップ

{displaystyleS}

$s$ の計算の手順

{displaystyle phi _ {i}^{b}（x）}

$Phi _{i}^{B}(x)$ 実施した。もしも

{displaystyle phi _ {i}^{b}（x）}

$Phi _{i}^{B}(x)$ 後

{displaystylet}

$t$ ステップ、その後、戦略はの価値になります

{displaystyle phi _ {i}^{b}（x）}

$Phi _{i}^{B}(x)$ の中に

{displaystylet}

$t$ – 建設の建設を経験し、それに応じて決定することができます

{displaystyle x}

$x$ 後

{displaystyle a}

$A$ 取得するかどうか。保留

{displaystyle phi _ {i}^{b}（x）}

$Phi _{i}^{B}(x)$ そうではありません

{displaystyle phi _ {i}}

$Phi_i$ 全体の機能はなく、したがって、削減は削減されません。そうです

{displaystyle r_ {2i}}

$R_{{2i}}$ 自動的に満たされました。

一方、そうです

{displaystyle b}

$B$ の建設中

{displaystyle a}

$A$ 両方の数量が同時に構築されているため、まだ利用できません。したがって、Oracleマシンが受信します

{displaystyle phi _ {i}}

$Phi_i$ オラクルのように

{displaystyleS}

$s$ – 代わりにステップ

{displaystyle b}

$B$ 有限量

{displaystyle b_ {s}}

$B_{s}$ 。それが保持されている場合、Oracle Uringマシンは最終的に最終的に多くのOracleの問い合わせを尋ねることができます。後のすべての量を要求するだけで十分です

{displaystyle b_ {t}}

$B_t$ すべての数字で

{displaystyle xleq k}

$xleq k$ （

{displaystyle k}

$k$ の計算における最大のOracle要求です

{displaystyle phi _ {i}^{b}（x）}

$Phi _{i}^{B}(x)$ ）と

{displaystyle b_ {s}}

$B_{s}$ それを確実にすることに同意します

{displaystyle phi _ {i}^{b_ {s}}（x）= phi _ {i}^{b}（x）}

$Phi _{i}^{{B_{s}}}(x)=Phi _{i}^{B}(x)$ は。したがって、戦略は設定されます

{displaystyle k}

$k$ いつ

${displaystyle b}$

$B$ -制限 修正された、それは戦略がないことを意味します

{displaystyle r_ {2i+1}}

$R_{{2i+1}}$ 将来支払うことがあります

{displaystyle xleq k}

$xleq k$ に

{displaystyle b}

$B$ 追加。

戦略

{displaystyle r_ {2i+1}}

$R_{{2i+1}}$ 交換された役割で完全に類似しています

{displaystyle a}

$A$ と

{displaystyle b}

$B$ 。したがって、これらの戦略は類似している可能性があります

${displaystyle a}$

$A$ -制限 挿入

{displaystyle r_ {2i}}

$R_{{2i}}$ – 証人の選択における戦略。制限により、既にアクティブな戦略の証人が使用できなくなるようになりました。

{displaystyle k}

$k$ は。解決策は、各戦略が、戦略によって優先順番に配置された制限のみを観察することです。彼らが戦略を認識します 怪我した 言い換えれば、彼女が引き起こした制限がより高い優先事項の戦略によって侵害された場合、彼女は新しい証人を選択し、正面から始まります。

今では、次のように、各戦略が最終的に何度も負傷したことを誘導的に示すことができます。つまり、ある時点で最終的に満たされます。そこには

{displaystyle r_ {0}}

$R_0$ 負傷することはありません。それは皆のためだからです

{displaystyle r_ {s+1}}

$R_{{s+1}}$ 最後に、優先順位が高い要件は多くあり、そのすべてが誘導要件が負傷した後に最終的に侵害されただけで、最終的に侵害されます。

{displaystyle r_ {s+1}}

$R_{{s+1}}$ また、優先度が高い戦略によってのみ侵害される可能性があるため、最終的に負傷しました。

形式化 [ 編集 | ソーステキストを編集します ]

フォームのすべての要件

{displaystyle r_ {2i}}

$R_{{2i}}$ 次のように手続き上で提示できる戦略があります。

可能性を選択してください 目撃者 バツために ${displaystyle aneq phi _ {i} ^ {b}}$
すべての後のステップで
s {displaystyleS}
$s$ 、次の条件のいずれかが適用されるかどうかを確認してください。
1. バツ 1つ以下にあります a – 優先度が高い照明。この場合はそうでした ${displaystyle r_ {2i}}$
2. ${displaystyle a_ {s}（x）= 0 = phi _ {i}^{b_ {s}}（x）[s]}$
${displaystyle x}$
多分と計算される最大のOracleリクエスト ${displaystyle phi _ {i}^{b_ {s}}（x）}$
すべての後のステップで ${displaystyleS}$

要求事項

{displaystyle r_ {2i+1}}

$R_{{2i+1}}$ AとBが交換されるアナログ戦略があります。

の戦略

{displaystyle n}

$n$ -teアクティビティを要件

{displaystyle n}

$n$ – （1）での建設のステップ。すべてのステップで

{displaystyleS}

$s$ すべて戦略です

{displaystyle r_ {k}}

$R_{k}$ ために

{displaystyle kleq s}

$kleq s$ アクティブ。これは、あらゆるステップで多くの戦略を考慮する必要があることを意味します。すべての戦略は予測可能であるため、すべてです

{displaystyle a_ {s}}

$A_{s}$ と

{displaystyle b_ {s}}

$B_{s}$ それに応じて。

上記のように、すべての戦略が最終的に何度も違反されます。また、要件を示す必要があります

{displaystyle r_ {i}}

$R_{i}$ 関連する戦略に違反しなくなった場合、それは満たされます。すべての戦略以来

{displaystyle r_ {i}}

$R_{i}$ （1）後に最終的に負傷して減少しただけで、2つの可能な結果が残っています（ここに

{displaystyle r_ {2i}}

$R_{{2i}}$ 表示されている、類似

{displaystyle r_ {2i+1}}

$R_{{2i+1}}$ ）：

同様に、それはすべての人であることを示すことができます

{displaystyle r_ {2i+1}}

$R_{{2i+1}}$ 満たされる。

S. B.クーパー： 計算可能性理論 。 Chapman＆Hall/CRC、2004年。ISBN1-58-488237-9
リチャード・M・フリードバーグ：比類のない程度の解決策の2つの再帰的に列挙可能なセット（Postの問題の解決策1944）。の：国立科学アカデミーの議事録。バンド 43 、 S. 236–238 （ pnas.org [PDF]）。
アントニン・クチェラ： Postの問題に対する代替の優先順位のないソリューション。の：コンピューターサイエンスのスプリンガー講義ノート。バンド 233 、1986、 S. 493–500 。
A. A. Muchnik：アルゴリズムの理論を減らす問題の不正行為について。（ロシア）。の： doklady akademii nauk sssr（n.s.）。バンド 108 、1956年、 S. 194–197 。

↑ J.C.E.Dekker： HyperSimpleセットの定理。の：アメリカ数学協会の議事録。バンド 5 、1954年、 S. 791–796 。

after-content-x4

FriedbergとMuchnikによる文 – ウィキペディア

アイディア [ 編集 | ソーステキストを編集します ]

戦略 [ 編集 | ソーステキストを編集します ]

直感 [ 編集 | ソーステキストを編集します ]

形式化 [ 編集 | ソーステキストを編集します ]

Recent Posts

Recent Comments

Archives

Categories

Meta