停止性問題

2日ほど前、会社の同期と「停止性問題って知ってる？」と議論をふっかけてきた。
そこから1時間ほど二人で停止性問題について議論した。
二人とも分からないなりに調べ考え、停止性問題の結論を理解するに至ったが、私はもやもやが晴れずその後いろいろと考えていた。
今回はその考えた内容を書いて行きたい。

 停止性問題とは http://ja.wikipedia.org/wiki/%E5%81%9C%E6%AD%A2%E6%80%A7%E5%95%8F%E9%A1%8C

このwikiがわかりづらい。
それぞれの項目が整理されていないからだ。
これを整理して考えよう。 この解説の問題点の一つは、省略すべきでないところを省略してしまっているところだ。

例えば変数と定数についてだ。
＞プログラムAにデータxを入力して実行する事をA(x)と書き、A(x)がyを出力するときy=A(x)と書く。
この表現は変数と定数がごちゃごちゃになっている。 

x,yともに変数としよう。yはxによって既定される。
すなわち y=f(x) 例えばxにaという値を代入しよう、
すると (x,y)=(a,f(a))　←x=a,y=f(a) となるわけだ。
これでx,yは変数であり、aは定数であると分かる。
（一般的にx,y等は変数を表すときに、a,bは定数を表すときに使われる） 
これから何が変数で何が定数なのかをハッキリさせながら議論していきたい。 


さて、停止性問題について考えよう。 

その前にアルゴリズムについて解説する。
アルゴリズムとは一定のルールに従い行われる処理である。
Wikipedia先生は分かりづらいので、goo辞書を引用する。

＞ある特定の問題を解いたり、課題を解決したりするための計算手順や処理手順のこと。これを図式化したものがフローチャートであり、コンピューターで処理するための具体的な手順を記述したものがプログラムである。イランの数学者・天文学者、アル＝フワーリズミーにちなむ。

つまり一定のルールで行われる処理である。
例えばアルゴリズムAを「f(x)にx=aを代入し、算出されたf(a)をyとする」と既定する。
このようにアルゴリズムに必要なのは「一定のルール」であり、アルゴリズムを起動するに必要なのは「そのルールに見合った入力（代入）」である。
（ルールに見合った、とはルール内で必要とされている変数にあったものを入力するという意味である。先の例では変数がxである。この状態で、z=aを代入するとしても、意味がない。
飽くまでルールに見合った値を入力する必要がある）

さて、アルゴリズムによっては永遠に終わらないものも存在する。
例えばアルゴリズムBを以下の用に定義しよう。
「変数xに対して、x>0ならばf(x)=x+1とする。そしてこのf(x)を新しいxとし、再び計算する。
x<=0ならばf(x)=0とする。」

このときx=1という値を代入してみよう。
x=1>0なので、ルールに従いf(1)=2となる。そしてこの"2"を再び代入する。(x=2とする)
x=2>0なので、ルールに従いf(2)=3となる。そしてこの"3"を再び代入する。(x=3とする)
x=3>0なので、ルールに従いf(3)=4となる。そしてこの"4"を再び代入する。(x=4とする)
・
・
・
と、このように何時まで経っても計算し続けるアルゴリズムが存在する。 
注意していただきたいのは、アルゴリズムBは無限に終わらない時と、有限で終わる時があるということである。
例えばx=1とすると上記のように無限に続くが、x=-1とするとf(-1)=0となり計算が終了するからである。
これは何を意味するかというと、同じアルゴリズムであっても、代入値によって挙動・結果が異なるということである。
これを覚えていて欲しい。 

さて、アルゴリズムについての解説が終わったところで停止性問題について考えよう。
「与えられたアルゴリズムが有限時間で計算が終わるものか、無限に計算し続けるものかを確かめるアルゴリズムは存在するか？」
これが停止性問題である。

WikipediaによるとH(A,x)というアルゴリズムを考えることで証明しようとしている。
すなわちH(A,x)は
＞A(x)が有限時間で停止する ⇒ H(A,x)は有限時間でYESを出力して停止する。
＞A(x)は有限時間では停止しない ⇒ H(A,x)は有限時間でNOを出力して停止する。
と定義される。

ややこしいのが、ここでいうxは定数である。変数ではない。 
この表現が誤解を生みやすい。

アルゴリズムHは代入値（入力）に①アルゴリズムと②そのアルゴリズムに必要な代入値を必要とする。
もう少し細かく表現すると、アルゴリズムHは代入値（入力）に①アルゴリズムAlgと②そのアルゴリズムAlgに必要な代入値(例えばx=a)を必要とする。
つまり、アルゴリズムHはアルゴリズムAにx=aを入力したときに、Aが有限時間で計算できるか否かを判断するアルゴリズムなので、必然的に入力としてアルゴリズムAとx=aを必要とする、ということである。 

これ以上説明しても分かりやすくする自身はないので、アルゴリズムHの定義に移ろう。
アルゴリズムH(Alg=A(x)|x=a)は、アルゴリズムA(x)とそのアルゴリズムへの代入値x=aとして 　
　・A(a)が有限時間で停止する場合 ⇒ H(Alg=A(x)|x=a)=0を出力して停止する。 　
　・A(a)は有限時間では停止しない場合 ⇒ H(Alg=A(x)|x=a)=1を出力して停止する。
※A(x)とx=aの敷居に","を使わず"|"を使ったのには意味がある。それは後ほど解説する。 

表記の問題であるが、Hの特質として()の中に入るものが限定されている。
H(アルゴリズム|アルゴリズムへの代入値) である。
このためH(Alg=A(x)|x=a)と表記した。
つまり「入力するアルゴリズムはA(x)である、そのアルゴリズムA(x)に入力する値はx=a」である、ということを分かりやすくもれなく表現するために、上記のような表記にした。 

この表現は「Hは①アルゴリズムと②そのアルゴリズムへの代入値という2つの代入値が無いと計算できない」ということは示している。
代入値が2回出現するのでややこしい（笑）
言い換えると「Hは2つの情報をインプットする必要がある、ひとつは判定すべきアルゴリズムであり、もうひとつはそのアルゴリズムへの代入値である」 
先のアルゴリズムの説明でも記したが、同じアルゴリズムであっても、代入値によって挙動が異なる。

Hについて言うとH(Alg=A(x)|x=a)とH(Alg=A(x)|x=b)は違った結果をもたらす可能性がある。
（もちろん同じ結果をもたらす可能性もある）
つまり、同じアルゴリズムであっても、代入値によって挙動・結果が異なるということである。
念を押すがこのことを覚えていて欲しい。 

話を戻そう。Wikipediaでは停止性問題を証明するためアルゴリズムMを以下のように定義している。
＞M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとする。(H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。)

この説明、重要なところを省略しているうえに分かりづらい。
アルゴリズムAを使用する場合はその代入値についても言及する必要があり、そこを表記していないのである。
Wikipediaの定義では問題が多そうなのでここでは以下のように定義しよう。
アルゴリズムM(Alg=A(x)|x=a)はアルゴリズムH(Alg=A(x)|x=a)が 　
　・H(Alg=A(x)|x=a)=0の場合（A(a)が有限に計算できる場合）、M(Alg=A(x)|x=a)を再度計算する。 　
　・H(Alg=A(x)|x=a)=1の場合（※A(a)が無限計算になる場合）、M(Alg=A(x)|x=a)=1として計算を終了する。

ここで、前者のA(a)が有限に計算出来る場合は、再度計算させていることに注目して欲しい。
このようにわざとループさせることで「有限時間で計算できない」状況を作り出している。
Wikipediaで
＞H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。
と表記してあるのはこのことである。
分かりづらい。 

さて、Wikipediaではこの後M(M)を考えるととで背理法を用いて停止性問題に結論を出そうとしている。
すなわち
＞M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
＞M(M)が停止しないとすると、Mの定義よりH(M,M)=YES。Hの定義より、H(M,M)=YESとなるのはM(M)が停止するときのみなので、矛盾。
＞よって停止性問題を常に正しく解くプログラムHは存在しない。　
としている。

Wikipediaでの定義とここでの定義が異なるので、この部分をもう一度考えていきたい。 

そもそもM(M)は何を意味しているのであろう？
これはM(M|A,x=a)という表記になる。
ここで"|"を使ったのはH(Alg=A(x)|x=a)の時と同じである。
つまりM(アルゴリズム|代入値)を意味する。
Mに必要な①アルゴリズムと②代入値である。
　①アルゴリズム=M
しかしこのアルゴリズムM自体が代入値を必要とする。
ここで必要な代入値は
　②-1アルゴリズムA
　②-2そのアルゴリズムAに代入する値x=a
である。

M(M|A,x=a)ではまだ必要な情報が省略されている。
より正確な表現をするのであれば、
M(Alg=M(Alg')|Alg'=A(x),x=a) と表記するのが良い。
Alg=M(Alg')は「Mはインプットとしてアルゴリズムが必要です」ということを表している。
Alg'=A(x),x=aは「必要なAlg'をアルゴリズムA(x)、さらにそのアルゴリズムA(x)に必要な代入値xをaとします」ということを表している。 

ここまで来てやっとアルゴリズムM(M)を考えることができる。
（正確にはM(Alg=M(Alg')|Alg'=A(x),x=a)を考えることができる） 

ここからWikipediaの背理法の展開をなぞっていこう。
M(Alg=M(Alg')|Alg'=A(x),x=a)が停止したとしよう。
Mの定義からこの場合、 H(Alg=M(Alg')|Alg'=A(x),x=a)=1 となる。
これはM(Alg=A(x)|x=a)が有限時間で計算できず、無限に計算することを意味している。
※表記が複雑で頭が混乱するが定義に立ち返りゆっくり考えて欲しい。M(A(a)はアルゴリズムA(x)にx=aを代入したものを有限時間で計算できるかを判定するものである。

ここからが問題である。
Wikipediaによると、
＞M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
となっている。

今回の定義に翻訳し直すと、
M(Alg=M(Alg')|Alg'=A(x),x=a)が停止したとすると、Mの定義よりH(Alg=M(Alg')|Alg'=A(x),x=a)=1。
Hの定義よりH(Alg=M(Alg')|Alg=A(x),x=a)=1となるのはM(Alg=A(x)|x=a)が停止しないときのみなので、矛盾。
となる。
最後に「矛盾」とあるが、これは最初に「停止した」と仮定したのに対し、結論で「停止しない」となったためである。 



だが、これは矛盾しない。



主語を入れてもう一度書いてみよう。
最初に停止したと仮定したものは「M(Alg=M(Alg')|Alg=A(x),x=a)」である。
結論で停止しないと出たものは「M(Alg=A(x)|x=a)」である。
矛盾しないではないか。 

よくわからない人は、「同じアルゴリズムであっても、代入値によって結論が異なる」ということを思い出して欲しい。
M(Alg=M(Alg')|Alg'=A(x),x=a)とM(Alg=A(x)|x=a)は異なる。
両方とも代入値として①アルゴリズムと②そのアルゴリズムに代入する値を必要とする。
前者は①=M(Alg')、②=Alg'=A(x),x=aであり
後者は①=A(x)、②=x=aである。

代入値が異なるため、それぞれ違う結果が出て良いのである。 

従ってWikipediaにある証明法は間違っている。

ここまで頑張ってWikipediaの背理法が間違いであるとこを証明していた。
といっても、所詮素人の主張であり、プロの目から見れば間違いがあるとは思う。
（例えば「M(Alg=M(Alg')|Alg'=A(x),x=a)とM(Alg=A(x)|x=a)はその性質上同じ結論に至らねばならない」などである。それが言えれば「矛盾」が成立する）
また私の主張が合っていたとしても、他の方法で停止性問題が証明されていれば「有限時間に計算できるか否かを判断するアルゴリズムは存在しない」という結論は変わらない（と思われる）。

いずれにせよ、楽しい思考ができた。この機会を与えてくれた同期には感謝する。