「計算可能な数について」

1936年、ケンブリッジ大学の若い数学者アラン・チューリングが、「計算可能な数について、決定問題への応用とともに」という論文を書き上げた。紙のテープに記号を書いては消し、一マスずつ動くだけの想像上の機械を定義し、その機械でも答えの出せない問いがあることを証明した論文である。数学の基礎をめぐる問いへの答えとして書かれたものだが、後になって、コンピュータという考えそのものの出発点と見なされるようになった。

問いは、数学の側から来た。20世紀の初め、ドイツの数学者ダフィット・ヒルベルトは、数学全体を揺るぎない土台の上に据え直そうとしていた。その計画の一つとして、1928年に「決定問題」と呼ばれる問いがはっきり掲げられた。ある論理式が与えられたとき、それが証明できるかどうかを、決まった手順を機械的に当てはめるだけで判定する方法はあるか、という問いである。そういう方法があれば、数学の問題は原理的にはすべて、手順を回すだけで片がつくことになる。

1931年、オーストリアのクルト・ゲーデルが、矛盾のない数学の体系には、正しいのにその体系の中では証明できない命題が必ず含まれることを示した。ヒルベルトの計画は大きく揺らいだが、決定問題はまだ残っていた。チューリングは1935年、ケンブリッジでマックス・ニューマンの講義を聴いてこの問題を知る。22歳か23歳の頃である。

答えるには、まず「機械的な手順」とは何かを定義しなければならない。誰もが分かったつもりで使っている言葉だが、厳密な定義はなかった。チューリングは、紙と鉛筆で計算している人間を思い浮かべた。当時、「コンピュータ」という言葉は、計算を仕事にする人間を指していた。その人がすることを、これ以上分けられないところまで分解していく。いま見ている記号を読む。決まりに従って、その記号を書き換えるか、そのままにする。隣のマスへ一つ動く。頭の中の状態を、決まりに従って次の状態へ変える。それだけである。

こうして定義されたのが、一本の長い紙テープと、それを一マスずつ読み書きする装置からなる機械だった。装置には有限個の状態があり、いまの状態と読んだ記号の組み合わせごとに、何を書き、どちらへ動き、次にどの状態になるかが表で決められている。規則の表を変えれば、足し算も、円周率の計算も、どんな計算でもできる。人間が手順に従ってできる計算は、すべてこの機械でできるはずだ、とチューリングは論じた。

そのうえで、この機械でも判定できない問いがあることを示した。ある機械の規則の表を渡されたとき、その機械が計算を永遠に続けて答えを出し続けるのか、どこかで行き詰まるのかを、すべての場合について正しく判定する機械は作れない。そういう機械があると仮定すると、それを自分自身に当てはめたときに矛盾が起きるのである。今日では、同じ趣旨の問題が、ある手続きが止まるかどうかを判定できるかという「停止問題」の形で教えられている。この結果から、決定問題の答えは否定的になる。証明できるかどうかを機械的に判定する一般的な方法は、存在しない。

実は、アメリカのプリンストンにいた論理学者アロンゾ・チャーチが、まったく別のやり方で、ほんの少し先に同じ結論に達していた。チューリングは論文に付録を加えて、二人の「計算できる」の定義が同じものを指すことを示し、その後プリンストンへ渡ってチャーチのもとで博士号を取った。人間が機械的な手順でできる計算は、この機械でできる計算とちょうど一致するという考えは、二人の名を取って「チャーチ＝チューリングのテーゼ」と呼ばれる。証明できる定理ではなく、計算という言葉の意味についての提案だが、これまで反例は見つかっていない。

否定的な答えだったが、副産物のほうが大きかった。規則の表そのものを記号に直してテープに書いておけば、それを読んで、その表どおりに振る舞う一台の機械が作れる。チューリングはこれを「万能機械」と呼んだ。計算ごとに別の機械を作る必要はない。一台の機械に、何をするかを書いたものを読ませればよい。機械と、それにさせる仕事を書いたものとが、分けられることになった。いまで言えば、ハードウェアとソフトウェアの区別である。

第二次世界大戦が始まると、チューリングはブレッチリー・パークで、ドイツ軍の暗号機の解読に加わった（エニグマの解読）。戦後はイギリス国立物理学研究所で、プログラムを記憶装置に蓄えて動く電子計算機の詳しい設計を書いた。同じ頃、アメリカではENIACが動き出し、数学者フォン・ノイマンがプログラムを記憶装置に蓄える方式をまとめた報告を書いている。ノイマンがチューリングの論文を知っていたことは同僚の証言から分かっているが、それが設計にどこまで影響したかには議論がある。

1950年には、機械は考えることができるかという問いを、人間と機械を文字のやりとりで見分けられるかという試験に置き換えた論文を書いた。のちに「チューリング・テスト」と呼ばれるものである。しかし1952年、当時のイギリスで犯罪とされていた同性間の関係を理由に有罪とされ、ホルモン剤の投与を受け入れさせられた。1954年、41歳で、青酸中毒で死んでいるのが見つかった。自殺と判断されたが、事故の可能性を指摘する人もいる。2013年、イギリス政府は彼に死後の恩赦を与えた。

1936年の論文に、電子回路も真空管も出てこない。出てくるのは、紙テープと、記号と、規則の表だけである。それでも、いま私たちが手にしている計算機は、電話もパソコンも、渡された命令を読んで、その通りに記号を書き換える一台の機械という点で、このとき紙の上に描かれた万能機械の子孫だと言える。同時にこの論文は、そうした機械でも、原理的に解けない問いがあることを最初に示したものでもあった。