Aritalab:Lecture/Algorithm/Halting Problem - Revision history

Adm: /* 矛盾の導き方 */

2017-08-22T03:09:26Z

‎矛盾の導き方

Adm: /* ポストの対応問題 */

2011-12-19T11:49:20Z

‎ポストの対応問題

Adm: /* ポストの対応問題 */

2011-12-19T11:47:36Z

‎ポストの対応問題

Adm: /* ポストの対応問題 */

2011-12-19T11:47:07Z

‎ポストの対応問題

Adm: /* 矛盾の導き方 */

2011-10-31T05:13:37Z

‎矛盾の導き方

Adm at 04:27, 31 October 2011

2011-10-31T04:27:35Z

Adm: /* ポストの対応問題 */

2011-10-26T02:48:00Z

‎ポストの対応問題

Adm: /* ポストの対応問題 */

2011-10-26T02:46:59Z

‎ポストの対応問題

Adm: /* 問題を解くということ */

2011-10-26T02:46:12Z

‎問題を解くということ

Adm: /* ポストの対応問題 */

2011-10-26T02:43:07Z

‎ポストの対応問題

@@ Line 18: / Line 18: @@
 ===矛盾の導き方===
-任意のプログラム P と入力 x を受け取って、P が止まるか否かを有限時間で YES/NO と答えられるプログラム C(P, x) があると仮定します。（C をコンパイラと考えると分かりやすい。）C は必ず有限時間で止まり、C(P, P) という入力（つまりプログラム P 自身を数値に置き換えて入力にしてしまう）に対しても YES/NO と答えます。ここで、このコンパイラプログラム C に細工をして、C(P, P) が YES なら無限ループさせ（無限ループを付け加えるのは簡単）、C(P, P) が NO なら YES と出力して停止する C' を作成します。この新しいコンパイラ C' に C' 自身を数値に置き換えた値を入力するとどうなるでしょうか。
+任意のプログラム P と入力 x を受け取って、P が止まるか否かを有限時間で YES/NO と答えられるプログラム C(P, x) があると仮定します。（C をコンパイラと考えると分かりやすい。）C は必ず有限時間で止まり、C(P, P) という入力（つまりプログラム P 自身を入力にしてしまう）に対しても YES/NO と答えます。ここで、このプログラム C に細工をして、C(P, P) が YES なら無限ループさせ（無限ループを付け加えるのは簡単）、C(P, P) が NO なら YES と出力して停止する（１引数の）プログラム C'　を作成します。この新しいプログラム C' に C' 自身を入力するとどうなるでしょう。
-* C'(C', C') が停止する場合
+* C'(C') が停止する場合
-: C(C', C') が NO となるため、プログラム C' は 入力 C' に対して停止しないことになります。ですから、C'(C', C') が停止するのは矛盾です。
+: C'の定義より、C(C', C') は NO 、プログラム C' に入力 C' を入れると停止しないことになる。しかし、これは C'(C') が停止する場合とした仮定と矛盾。
-* C'(C', C') が停止しない場合
+* C'(C') が停止しない場合
-: C(C', C') が YES となるため、プログラム C' は入力 C' に対して停止しなくてはなりません。やはり矛盾になります。
+: C'の定義より、C(C', C') は YES 、プログラム C' に入力 C' を入れると停止することになる。しかし、これはC'(C') が停止しない場合という仮定と矛盾。
-<!----
+つまり前提が間違っており、停止性を判定できるプログラム C(P, x) は存在しないことになります。
-証明のポイントは、プログラム P がプログラム自身を引数にとる部分です。停止する・しないを {0, 1} であらわすと &Nu; &times; &Nu; &rarr; {0, 1} という関数を意味します。自分自身を入力にするプログラム
-この関数全体は &Nu; 上のべき集合に一致します。
----->
-−
-<ref>矛盾の導出には、あらゆるプログラムを自然数と1:1に対応付けるゲーデル数という概念を用いており、カントールの対角線論法と同じ議論になっています。</ref>
 ==ポストの対応問題==

@@ Line 52: / Line 52: @@
 解は存在しない。左端になれる対は <math>\textstyle \frac{0}{01}</math> しかなく、その後は <math>\textstyle \frac{101}{011}</math> しか繋げられないため
-いかなる文字列の対を用意されても、解の有無を判定できるアルゴリズム（計算機プログラム）はあるでしょうか。そうしたアルゴリズムは存在しないことが理論的に証明できてしまいます。つまり、どのような文字列の対与えられても解があるときに YES と答えられるプログラムは（どんなに時間のかかるアルゴリズムを許したとしても）存在しません。もし存在すると仮定すると、 停止性問題が解けてしまうことを利用します。
+いかなる文字列の対を用意されても、解の有無を判定できるアルゴリズム（計算機プログラム）は存在しないことが理論的に証明できてしまいます。つまり、どのような文字列の対与えられても解があるときに YES と答えられるプログラムは（どんなに時間のかかるアルゴリズムを許したとしても）存在しません。もし存在すると仮定すると、 停止性問題が解けてしまうことを利用します。
 ===停止性問題の変換===

← Older revision		Revision as of 11:47, 19 December 2011
Line 40:		Line 40:


−	分数の形で書いたのでちょっとわかりにくいかもしれませんが、要するに上半分と下半分にそれぞれ別の文字列が書かれているトランプが何パターンか用意されているとします。各パターンのカードをいくらでも使って良いから、うまく並べることで上側と下側の文字列を一致させられるか、という問題です。いくつか例を考えましょう。	+	分数の形で書いたのでわかりにくいかもしれませんが、要するに上半分と下半分にそれぞれ別の文字列が書かれているトランプが何パターンか用意されているとします。各パターンのカードをいくらでも使って良いから、うまく並べることで上側と下側の文字列を一致させられるか、という問題です。いくつか例を考えましょう。

	;例		;例

@@ Line 37: / Line 37: @@
 ;ポストの対応問題
-あるアルファベット &Sigma; からなる語 k 対 <math>\textstyle \{ \frac{x_1}{y_1}, \frac{x_2}{y_2}, ... , \frac{x_k}{y_k} \} \ (x_i, y_i \in \Sigma^*)</math> に対し、重複を許して並べることで上側と下側に同じ文字列を一致させる <math>x_{i_1}, x_{i_2}, ... , x_{i_n} = y_{i_1}, y_{i_2}, ... , y_{i_n} \ (1 \leq i_1, i_2, ... i_n \leq k)</math> ことができるか。
+: あるアルファベット &Sigma; からなる語 k 対 <math>\textstyle \{ \frac{x_1}{y_1}, \frac{x_2}{y_2}, ... , \frac{x_k}{y_k} \} \ (x_i, y_i \in \Sigma^*)</math> に対し、重複を許して並べることで上側と下側に同じ文字列を一致させる <math>x_{i_1}, x_{i_2}, ... , x_{i_n} = y_{i_1}, y_{i_2}, ... , y_{i_n} \ (1 \leq i_1, i_2, ... i_n \leq k)</math> ことができるか。
 ;例
@@ Line 47: / Line 50: @@
 { 0, 1 } &isin; &Sigma; <math>\textstyle \{ \frac{0}{01}, \frac{101}{011}, \frac{111}{10} \}</math> は解をもつか。
-解は存在しない
+解は存在しない。左端になれる対は <math>\textstyle \frac{0}{01}</math> しかなく、その後は <math>\textstyle \frac{101}{011}</math> しか繋げられないため
-この問題を解くアルゴリズムは存在しません。つまり、どのような文字列の対を与えられても解があるときに YES と答えられるプログラムは（どんなに時間のかかるアルゴリズムを許したとしても）存在しません。もし存在すると仮定すると、 停止性問題が解けてしまうことを利用します。
+いかなる文字列の対を用意されても、解の有無を判定できるアルゴリズム（計算機プログラム）はあるでしょうか。そうしたアルゴリズムは存在しないことが理論的に証明できてしまいます。つまり、どのような文字列の対与えられても解があるときに YES と答えられるプログラムは（どんなに時間のかかるアルゴリズムを許したとしても）存在しません。もし存在すると仮定すると、 停止性問題が解けてしまうことを利用します。
 ===停止性問題の変換===
@@ Line 191: / Line 194: @@
 * チューリングマシンが任意の入力に対して受理するか否かという問題は、ポストの対応問題の部分問題になっている。
 * ポストの対応問題を解くプログラムがあるなら、チューリングマシンの停止性問題が解けてしまう。
+* チューリングマシンの停止性問題を解くプログラムは存在しないので、ポストの対応問題を解くプログラムも無い。
 ;参考
 <references/>

@@ Line 23: / Line 23: @@
 : C(C', C') が NO となるため、プログラム C' は 入力 C' に対して停止しないことになります。ですから、C'(C', C') が停止するのは矛盾です。
 * C'(C', C') が停止しない場合
-: C(C', C') が YES となるため、プログラム C' は入力 C' に対して停止しなくてはなりません。やはり矛盾になります。<ref>矛盾の導出には、あらゆるプログラムを自然数と1:1に対応付けるゲーデル数という概念を用いており、カントールの対角線論法と同じ議論になっています。</ref>
+: C(C', C') が YES となるため、プログラム C' は入力 C' に対して停止しなくてはなりません。やはり矛盾になります。
 ==ポストの対応問題==

@@ Line 3: / Line 3: @@
 * 必ず停止する（無限ループに陥らない）
 * 必ず正しい答えをだす
-ことが要求されます。例えば、階乗を計算するプログラムがあったとして、入力する値によって無限ループに陥ったり、計算結果が間違っている可能性があるとしたら、皆さんもプログラムは "バグがある" と思うでしょう。
+ことが要求されます。例えば、階乗を計算するプログラムがあったとします。入力する値によって無限ループに陥ったり、計算結果が間違っている可能性があるとしたら、皆さんもプログラムは "バグがある" と思うでしょう。
-チューリング機械が "解ける" 問題の範囲とはどのようなものでしょう。ここでは
+チューリング機械が "解ける" 問題の範囲とはどのようなものでしょうか。ここでは
 * 任意のプログラムが無限ループを含むかどうか　（停止性問題）
 * 文字列が上下に 1 対記されたカードを与えられた時、重複を許して並べることで上側の文字列と下側の文字列を一致させることができるか （ポストの対応問題）

@@ Line 80: / Line 80: @@
 {| class="wikitable"
-! TM の動作
+!width="15%"| TM の動作
 ! 記号対
 ! 解説
@@ Line 93: / Line 93: @@
+|
 |-
-|rowspan="2"| &sigma;(q<sub>0</sub>, 1) &rarr; (q<sub>1</sub>, 0, +1)
+|rowspan="2"| &delta;(q<sub>0</sub>, 1) &rarr;<br/> (q<sub>1</sub>, 0, +1)
+|
 {| style="border-collapse:collapse"
@@ Line 110: / Line 110: @@
 | その後、区切り記号 # まで (0/0), (1/1), (#/#) を用いて入力列を補完します
 |-
-|rowspan="2"| &sigma;(q<sub>1</sub>, 0) &rarr; (q<sub>5</sub>, 1, +1)
+|rowspan="2"| &delta;(q<sub>1</sub>, 0) &rarr;<br/> (q<sub>5</sub>, 1, +1)
+|
 {| style="border-collapse:collapse"
@@ Line 127: / Line 127: @@
 | ヘッドの左側まで入力列を補完します
 |-
-| &sigma;(q<sub>5</sub>, 1) &rarr; (q<sub>3</sub>, 0, -1)
+| &delta;(q<sub>5</sub>, 1) &rarr;<br/> (q<sub>3</sub>, 0, -1)
+|
 {| style="border-collapse:collapse"
@@ Line 136: / Line 136: @@
 | テープ記号 1 を読んで 0 を書き込み、ヘッドを左に移動します。(1q<sub>5</sub>1/q<sub>3</sub>10) を使います
 |-
-|rowspan="2"| &sigma;(q<sub>3</sub>, 1) &rarr; (q<sub>3</sub>, 0, -1)
+|rowspan="2"| &delta;(q<sub>3</sub>, 1) &rarr;<br/> (q<sub>3</sub>, 0, -1)
+|
 {| style="border-collapse:collapse"
@@ Line 153: / Line 153: @@
 | 補完します
 |-
-| rowspan="3"| &sigma;(q<sub>3</sub>, 0) &rarr; (q<sub>YES</sub>, 0, +1)
+| rowspan="3"| &delta;(q<sub>3</sub>, 0) &rarr;<br/> (q<sub>YES</sub>, 0, +1)
+|
 {| style="border-collapse:collapse"
@@ Line 179: / Line 179: @@
 |}
-つまり以下のことがわかりました。
+結果として、以下のことがわかりました。
 * チューリングマシンが任意の入力に対して受理するか否かという問題は、ポストの対応問題の部分問題になっている。
-* ポストの対応問題を解くプログラムがあるなら、チューリングマシンの停止性問題が解ける。
+* ポストの対応問題を解くプログラムがあるなら、チューリングマシンの停止性問題が解けてしまう。
 ;参考
 <references/>