コンピュータに何が出来て、何が出来ないのか、についての話です。
＊本記事は個人的な思索をまとめたものなので、内容や記述の正当性についての保証はしかねます！
Unityも触っていますが、やはりプログラミング自体も面白く、そちらに多く時間を掛けている状況です。特にやはり、数学は避けられないということがはっきりしたので、自分のペースでいろいろ勉強しています。
数学ガールというのは名前自体は聞いたことはあったし、サンプルで軽く読んでみたら文章も良さげだったので、この本を購入。
対象としては、ある程度プログラミング経験のある人向けな感じですが、ド文型の自分でも分かりやすい内容だったので良かったです。改めて、数学というのは自発的な興味を持ってやれば、面白いものだなと思いました。
そんなワケでこの本の中でも扱っている停止性問題について、自分の頭の中の整理を兼ねて書いていきます。停止性問題 - Wikipediaという記事がありますが、特に証明の部分が分かりにくいような気がするので、その補足を自分なりにしつつ、改めて内容の理解を深めようという狙いです。
コンピュータが出来るコト
現代社会において、あらゆるモノや場所にコンピュータが存在しています。なので、何でも出来るように思えますが、コンピュータにも出来ないことがあるということです。出来ることと出来ないことの見極めは大事ですよね、出来ないこと以外は理論上全て出来るわけなので。
コンピュータ上で扱えるのは数字のみであり、コンピュータで出来ることは計算できることにのみ限られます。
コンピュータは0と1の世界とも言われますが、それは単に見た目の問題であり、人間の言う数字の5もコンピュータ上の101（二進法）も内容は同じです。要は数字で表現できるか、その数字がどんな意味を持っているか、ということが本質です。
そして、計算可能かどうかというのは有限回数内に計算が止まるか、ということになります。ただし、人間社会においてはコンピュータの運用にはコストもありますし、時間も有限なので、『現実的な時間内に終わる』かどうか、という条件が付きます。
というワケで計算可能かどうか、というコンピュータの働きにおいて重要な観点から出てくるのが『停止性問題』です。
つまりは、『あるプログラムが止まるかどうかを判定するプログラム』は作ることが出来るか、という問題です。
結論から言ってしまえば、そのようなプログラムは書くことが出来ません。それを証明するのには背理法を使うんですが、背理法というのも実際そこまでややこしいものではないような気がします。
反対を正しいと仮定する
論理の世界というのは、我々人間社会とは違ってはっきりしていて、白黒付くものです。つまり、白じゃないなら黒だし、黒じゃないなら白という風に、はっきりと分かれて決着が付きます。
これが人間社会だと白じゃないし黒でもないグレイかもしれないし、黒じゃないけど白でもない、みたいなことになってしまいがちです。
これが正しい！と証明したいものの反対を正しいと仮定し、論理を積み上げていく。その過程で矛盾が出てくるなら、前提が間違っていたことになる。つまり、黒じゃない！だから、これが白であることは正しい！というのが背理法における論理の流れです。
これは白黒はっきりしている論理の世界だから出来ることですよね。
Wikiの停止性問題を読み解く
プログラムを関数とも言われます。関数はFunctionの頭文字を取って、f(x)という風に表記もされます。
プログラムは処理の連なりですが、コンピュータにおける処理というのは、結局計算なので、一定の計算をする式という意味で関数です。入力を二倍にして返すプログラムは、y = 2xという関数として表現できます。何かをする、というのは計算なので特定の計算をするということで、一定の処理をするコードの塊を関数と呼ぶ、ということです。
混乱しやすいのはプログラミングの中にも関数があるわけですが、それはミニプログラム、サブプログラムと言われたりもします。プログラミングにおける関数と数学における関数は、一応微妙に文脈は違う点には注意すべきかもしれません。
そして、コンピュータ上で扱われるのは全てデータ、数字なので、プログラムもまた数字の集まり、データとも言えるわけです。
この問題で証明したいのは『あるプログラムにとあるデータを入力した時に停止するかどうか』を判断するプログラムは書くことが出来ない、ということです。
これを背理法で証明するために次のように仮定します。
『入力された関数Aの引数を入力されたデータxにした時、止まるかどうかを判断できるプログラムは書くことが出来る！』
止まらない関数
これが停止性問題 - WikipediaでのH(A, x)という関数ないし、プログラムになります。プログラムAに対して、xを入力した時に
A(x)
が止まるかどうかを判定する、というもの。HというのはHalt（停止）の頭文字です。
ここではより分かりやすくするのに、HaltCheck(A, x)という関数とします。
HaltCheck(A, x){
if( 関数Aは止まる ){
YESを出力
}
else{ //関数Aが止まらないなら・・・
NOを出力
}
}
YES, NOを出力する、ということですが、true, falseを返す、という意味での理解で大丈夫だと思います。
ありえないことを想定するのが背理法とは言え、既に怪しい部分があります。止まるかどうかを確認して出力するのはまだ分かります。しかし、計算が止まらない状態をどう判断するのでしょうか。
プログラムというのは処理の流れです。もし、その過程で止まらなくなる、計算が終わらない、つまり無限ループになってしまったら、プログラムはそこから抜け出せなくなってしまい、最終的な出力にまで進み、値を返すことは出来なくなります。それはHaltCheckという関数でも同じなはずです。なので、少なくとも内部で実際に関数Aにxを入力してみる、という方法で確認するというようなプログラムではないと思われます。
しかし、あくまでこれはそのようなプログラムが書ける、という仮定の下での話であり、実際に出来るかどうか、出来るとしてどういうコードになるのかを考える必要はありません。ここが背理法のややこしい部分です。正しいと思い込んで論を進めます！
次は、そのような魔法のプログラムHaltCheck( )が存在するとして、それを使った別のプログラムを考えてみよう！という内容です。
自分自身を入力する
前述の通り、関数（またはプログラム）自体も本質的にはデータであるので、あらゆる入力データxのうちのひとつとして考えることが出来ます。
つまり、ある関数に関数自身を入力する、というプログラムをHaltCheck( )を使って、書こうということです。
停止性問題 - WikipediaのM(A)のMはおそらくMyselfからきていると思うので、ここではMyselfCheck(A)という関数名にして扱っていきたいと思います。
あらゆる関数やあらゆるデータを対象とするHaltCheck(A, x)からすると、MyselfCheck(A)の対象はプログラムAそれ自身に絞られるので、HaltCheck( )が書けるのであれば、無限ループと組み合わせることで書くことが出来ます。
MyselfCheck(A){
if(HaltCheck(A, A) == NO){
M(A)が停止する
}
else{
while(true){ }
// 無限ループ。M(A)は止まらない
}
}
つまり、HaltCheck(A, A)という風にHaltCheckのふたつの引数にAを両方ぶち込むということでMyselfCheck(A)は実現可能なはずです。HaltCheckが可能なら。
HaltCheckという関数を使い、プログラムAにAを入力した時にNOと出力されたら停止し、そしてYESと出力されたら、M(A)は止まらないというのがMyselfCheck(A)の動作になります。
注意としてはYES, NOと止まるか止まらないかの関係がHaltCheckとは反対になっている点です。HaltCheckではAが止まる時にYESと出力し、止まらないと判断した時にはNOと出力することになっています。プログラミングとしては、単に論理をひっくり返すだけなのでこういうコードは書くことは可能です。
ここまでが、『入力された関数に入力されたデータを引数にした時、止まるかどうかを判断できるプログラムは書くことが出来る！』と仮定した場合に導き出される論理の積み重ねです。
問題は次です。
MyselfCheckにMyselfCheckを入力
MyselfCheckにMyselfCheckを入力したら、どうなるでしょうか。今までの積み重ねは論理上でのことであり、実際に確かめる術はないので、場合分けによって判断します。
MyselfCheck( MyselfCheck );
MyselfCheckが止まった
もし、MyselfCheckが止まったのなら、
HaltCheck(MyselfCheck, MyselfCheck)は、NOを出力したことになります。
しかし、NOならばHaltCheckの内部ではMyselfCheck(MyselfCheck)を止まらないと判断した、ということになり、MyselfCheckが止まったことと矛盾します。
MyselfCheckが止まらない
もし、MyselfCheckが止まらないのなら、
HaltCheck(MyselfCheck, MyselfCheck)は、YESを出力。
しかし、YESならばHaltCheckはMyselfCheck(MyselfCheck)を止まると判断したことになるので、これもまた矛盾。
どちらの場合でも矛盾が生じてしまうので、つまり、前提とする仮定が間違っていたことになります。よって、あるプログラムが止まるかどうかを判定するプログラムは作ることが出来ない、ということです。
まとめ！
というわけで、プログラマの数学を読んで学んだことを踏まえて、wikiにおける不足した記述を自分なりに補いつつ、論理を流れを辿ってみる、ということにチャレンジしてみました。
数学的思考、論理的な考え方はやはり大事だと思いますし、自分で１から組み立てられるようになりたいですね。
