チューリングマシンは何を示したのか

コンピューターの歴史をたどると、その理論的な原点として「チューリングマシン」にたどり着く。
１本の記録テープと１個の有限状態機械から成る、この仮想的な装置を知る人は少なくないかもしれないが、チューリングがどのような意図で「チューリングマシン」を提唱したかについて、知る人はより少ないと思う。
先に書いた「不完全性定理の最短理解 d:id:rikunora:20080524 」の続編として、ここではチューリングマシンの停止問題について書いておこう。

* wikipedia:チューリングマシン

チューリングが示したかったのは、あらゆる数学の問題を自動的に解くことができる「究極のアルゴリズム」は存在しない、ということだったのだ。
もしそのような「究極のアルゴリズム」が存在すれば、もう数学者はいらない。
アルゴリズムに従って機械的な作業を続けるだけで、数学の問題は次々と解けることになるのだから。
（「究極のアルゴリズム」とは、前回書いた「プログラムのミスを自動的に取り除いてくれる、バグ取りプログラム」と同等のものだ。）

チューリングの議論に必要となる考え方は、次の３点だ。
１．プログラムとは、１つの数で表すことができる。
２．プログラムの扱う入力データも、また１つの数で表すことができる。
３．プログラムの最終的な計算結果も、同様に１つの数で表すことができる。

チューリングの天才的なアイデアは「問題が解ける」という漠然とした言葉を、具体的に「マシンが停止する」という定義に置き換えたことだ。
マシンが無限ループに陥ることなく、最後に停止すれば、それは「解けた」ものと見なす。
マシンが無限ループに陥って、いつまでも終わることなく動作し続けたなら、それは「解けなかった」と見なす。

いま仮に、問題が解けるかどうかを自動的に判断できる「究極のプログラム」があったとしよう。
「究極のプログラム」とは、あるプログラムが最後に停止するか否かを見分けるプログラムのことである。
この「究極のプログラム」を使えば、以下のような「あらゆるプログラムの計算結果表」が作成できるだろう。

(ProgNo.xData)	1	2	3	4	5	6	7	・・・
プログラムNo.1	10	x	x	4	62	x	・・・
プログラムNo.2	4	345	2	6342	832	x	・・・
プログラムNo.3	135	x	9999	1	62	8	・・・
プログラムNo.4	x	x	0	4	62	x	・・・
プログラムNo.5	666	143	77	5	x	36	・・・
・・・

この結果表は、縦に考え得る全てのプログラムを順番に並べ、横に入力データを順番に並べたものだ。
表の中で x 印が付いているのが無限ループに陥って「解けなかった」ところ。
それ以外の数字は、実際にプログラムを動かして出た結果が書いてある。
（表に書き込んだ数字は、きっとこんな風になるだろうという一例であって、実在するコンピューターのコードではない。）
この表は縦にも横にも無限に広がっている。
なぜ「考え得る全てのプログラムを順番に並べる」ことができるのか。
それは、前提となる考え方
　１．プログラムとは、１つの数で表すことができる
ことによる。
プログラムとは１つの数なのだから、小さい方から順番に並べることができるはずだ。
プログラムと呼んではいるが、その中には停止することのない無意味なプログラムがあってもかまわない。
むしろ実際には、ほとんど無意味な数字を小さい方から順番に入れてゆく作業となるだろう。
その中に、たまたま動作するものが含まれていることがある、といった感じだ。

もちろん実際にこの結果表を作るのは、たいへんな時間と労力を要するだろう。
そして表は無限に続くのだから、決して完成することはないだろう。
それでも、プログラムが停止するかどうかを事前に見極めることができれば、理屈の上ではこの結果表を小さい方から順番に埋めてゆくことができるはずだ。

この結果表の中には「考え得る全てのプログラム」が含まれている。
なので、どんなプログラムが作り出す結果の列も、必ずこの結果表の中に入っているはずだ。
ここで、この結果表の左上から右下に続く対角線に着目する。
そして、対角線上の数字を拾ってきて、それに１づつ足した数字の列、というものを作ってみる。
もし対角線上にｘがあったら、それは０に置き換える。
このようにして作った数字の列は、この結果表の中には含まれていない。
なぜなら、数字の列は１列目と１個目の数字が違っているし、２列目とは２個目の数字が違っているし、３列目とは３個目の数字がちがっている、、、以下同様。

ところで、
　「対角線上の数字を拾ってきて、それに１づつ足した数字の列、というものを作る」
という作業は、やり方がはっきりとわかっている１つのアルゴリズムだ。
なので、そういうプログラムが、必ずやこの結果表の中にあるはずだ。
なぜかというと、もともとこの結果表は「考え得る全てのプログラム」が含まれているはずだったからである。
ところが、数字の列の作り方から考えて、この結果の列が表の中に含まれることはあり得ない。
これは矛盾している。

一体何がおかしかったのか。
そもそもこういう結果表が作成できる、と考えたことが矛盾の原因だ。
ということは、問題が解けるかどうかを自動的に判断できる「究極のプログラム」は、そもそもこの世に存在しない。

上記の説明で用いた
「対角線上の数字を取り出してきて加工し、表中にない数字の列を作り出す」
という方法を、「カントールの対角線論法」と言う。
この論法を用いて「数直線上の点の数は、自然数の数よりもずっとずっと多い」ことが示される。
おそらく、この世にある数学の問題の数は、コンピューターによって解くことができる問題の数よりも「ずっとずっと多い」のだろう。