TM停止問題
TMの停止問題は非可解であることの証明。
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をxxとしてから、xxを入力としたMhの動きとまったく同じ動きをする。
模倣の定義、「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を受理しないということになる。
言語Lを認識するように作りたいのだから、止まらないという答えで停止した場合は、「xを非受理、Tは停止」。
Lの定義が、「ρi（ここではx）がxに対して停・止・し・て！〜〜」なので、そんなxが入力された場合には受理しない、つまり「xを非受理、Tは停止」にするのである。
-
- 止まると答えがでて停止した場合（yesの矢印）
止まるという答えで停止した場合は、今度は、TMxの列xに対する動作を模倣する。(Tのこの部分を「Tの後半部」とする。)
先と同様に、xがxを受理する時、その時に限ってTの後半部はE(x）E(x)を受理する。
よって、TM xが列xに対して非受理状態で停止すれば、Tの後半部はE(x）E(x)を受理しない。
後半部が非受理なので、「Tは停止してxを受理しない」ということになる。
後半部は非受理となるが、中間部と接続して、最終的に「Tは停止してxを受理する」というようにする。
TM xが列xに対して受理状態で停止すれば、もちろんTの後半部はE(x)E(x)を受理する。
後半部が受理なので、「Tは停止してxを受理する」ということになる。
後半部は受理となるが、中間部と接続して、最終的に「Tは停止してxを受理しない」というようにする。
このTMxは列xに対して必ず止まるので、あとは言語Lを受理するようにTM Tの受理条件を作るだけである。
Lの定義が、「ρi（ここではx)がxに対して停止して受・理・し・な・い！！」で、この言語を認識するようにしたいのだから、
TM xが列xに対して非受理状態で停止した場合は「TM Tはxを受理状態で停止」する。 TM xが列xに対して受理状態で停止した場合は「TM Tはxを非受理状態で停止」する。
- 矛盾が生じる
以上でMhの仮定から作成したTM Tは言語Lを認識する必ず停止するTMであることから、これは矛盾である。
よってTM Mhは存在しない、つまりTMの停止問題は停止するTMでは解けないことが示せた。
