TM停止問題・改
改訂版：TMの停止問題は非可解であることの証明。 旧版がカオスになったので書き直す。TM停止問題 - hat-tunの日記
L={ρi| TMρiは列ρiに対して停止して受理しない}
という言語が必ず停止するTMで認識できないことは証明されているとする。
まず問題を分析する。
- TM停止問題が非可解
インスタンスとしてTM Mと列ρ。
Mがρに対して停止するかどうかという問題が停止するTMで解けない＝Mがρに対して停止するかどうかはわからない。
次に、背理法による証明を試みる。
- TM停止問題を解ける、必ず停止するTM Mhが存在すると仮定する。
ここでMhは、インスタンスとしてTM Mと列ρをとる。
この仮定から、言語Lを認識するTM Tが存在してしまうことを示す。
１つでもそういうTが存在すれば反例として矛盾が生じる。 → そういうTを探す（作る）
- TM Tを作る
Tは言語Lを認識するように作りたい、つまりインスタンスとして列ρをとるものとする。
模倣の定義、「Tがxを入力とするMを模倣する，とは，Mがxを受理する場合に限りTがE(M)E(x)を受理する」
(E(M)，E(x)はそれぞれM, xを符号化してできた文字列)
を踏まえて、Tは入力xをxxとし・て・か・ら（この後を「Tの中間部」とする）、Mhのxxに対する動作を完全に模倣するように作る。
そのようにTを作ったので、Mhがxxを受理するとき、その時に限ってTの中間部はE(Mh)E(xx)を受理する。
ここで、仮定からTMxが列xに対して止まるかどうかの答えが出る。
-
- 止まらないと答えが出て停止した場合（Noの矢印）
Mhがxxを受理しなかったということなので、Tの中間部も同様にE(Mh)E(xx)を受理しない。
Tの入力はxであったが、中間部が非受理なので、したがってTは停止してxを受理しないということになる。
-
- 止まると答えがでて停止した場合（yesの矢印）
止まるという答えで停止した場合は、今度は、TMxの列xに対する動作を模倣する。(Tのこの部分を「Tの後半部」とする。)
先と同様に、xがxを受理する時、その時に限ってTの後半部はE(x）E(x)を受理する。
よって、TM xが列xに対して非受理状態で停止すれば、Tの後半部はE(x）E(x)を受理しない。
後半部は非受理となるが、中間部と接続して、最終的に「Tは停止してxを受理する」というように作る。
TM xが列xに対して受理状態で停止すれば、もちろんTの後半部はE(x)E(x)を受理する。
後半部は受理となるが、中間部と接続して、最終的に「Tは停止してxを受理しない」というように作る。
- 矛盾が生じる
以上でMhの仮定から作成したTM Tは言語Lを認識する必ず停止するTMであることから、これは矛盾である。
よってTM Mhは存在しない、つまりTMの停止問題は停止するTMでは解けないことが示せた。
