アラン・チューリングを今知ろう!

理系人間であればだれでも知っているアラン・チューリングの名前。コンピューターサイエンスは、彼が創始したといっても過言ではない。ロンドンオリンピックが開催された2012年は生誕100周年だったこともあり、あちこちでチューリングの名前が取りあげられた。

しかし、チューリングの業績についてはあまり知らない人が多いのではないだろうか。チューリングマシン、チューリングボンベ、デリラ、エースといった彼の機械についてはあちこちで耳にするものの、その機械の素晴らしさが今ひとつ実感できないという人も多いはずだ。

チューリングマシンの仕組みの話を聞いても、あまりのシンプルさに「で?」と尋ねたくなってしまう。解説された本を読もうとすれば、哲学と論理学の用語が過剰に散りばめられた難解なものばかり。

チューリングは、純粋な数学者でありながら、工学的なセンスを存分にもっていた。チューリングマシンも、コンピューターの〝原型〟として考案したのではなく、ゲーデルの不完全性定理という純粋な数学的研究をおこなううえで、難解で偏頭痛が起きそうな論理学演算を用いるのではなく、わかりやすく理解しやすい具体的な〝仮想計算機械〟を用いて、数学の不完全性を証明しようとした。

チューリングは、「シンプルに考える」ということを尊重していた人であることは間違いない。ただ、挑んでいる課題があまりにも複雑なので、チューリングの仕事も多少複雑に見えるだけだ。

チューリングの思考は、どんな複雑な課題に対しても、本質を見抜き、シンプルに考え、正解に一直線にたどりつく。そこがハッカー的であり、チューリングの偉大なところなのだ。

アラン・チューリングとシャーロック・ホームズがときどき重なることがある。ホームズはこういっている。「事件の外見が複雑に見えれば見えるほど、その本質は単純なものなのだ」「過程の推理をことごとく消し去って、お客には出発点と結論だけを示すと、いささか安っぽすぎるが、ともかくびっくりさせる効果はじゅうぶんだ」。

アラン・チューリングが夢想した、そして実際につくろうとした機械を紹介しながら、チューリングの思考の旅をたどってみたい。

 

チューリング本はむずかしすぎる!

読者は、アラン・チューリングの名前は当然知っているだろう。そして、その功績がチューリングマシンに代表される「コンピューターサイエンスの創始」にあるということもご存知だろう。しかし、チューリングの偉大さを実感として知っている人はいったいどれだけいるだろうか。

アラン・チューリングを解説した本の多くが、なぜか哲学と論理学の専門用語が散りばめられていて、読むのに苦労をするようにできている。専門書であればしかたのないことだが、一般向けの本でもそうなのだ。

もちろん、チューリングがさまざまな仕事をおこなった背景には、深い哲学的な思索があってのことだろう。しかし、そのような深い哲学的な思想は、10代や20代ではなかなか理解することができない。頭で理解をしても、実感として感じることはむずかしいのだ。

そしてチューリングマシンを見せられると、あまりのシンプルさに、ともすると「自分でも思いつけたのではないか?」と思ってしまう。これも、なにもないところから発想するのと、すでにチューリングマシンやコンピューターの原理を知っていて発想するのではまったく違うということはわかる。しかし、チューリングマシンのシンプルさと、それにともなって語られる難解な哲学思想のギャップに、目がくらんでしまって、読者の本質的な理解を妨げているのではないかと思えるのだ。

話は横道にそれるが、ゼロ 0という数字の概念は、4世紀から5世紀ごろのインドで発見された。しばしば「無の概念」とともに語られ、無の乗算と無限の関係などが仏教哲学とともに語られる。

しかし、ゼロを使い始めた人たちは、ほんとうにそんなご立派な思想を背景にゼロを考えていたのだろうか。ひょっとして「なにもないということを表すのに、適当な記号がないから◯でも書いておけばいいよね」というきわめて卑近で単純なことが出発点になっているのかもしれない。

事実、インドでもゼロの概念が盛んに議論されるようになったのは、7世紀のことで、0が使われるようになってから300年後のことである。また、紀元前のバビロニアでは、数を表すときに空位を表すのにゼロにあたる記号を使っていた。今日の我々のゼロの使い方とほぼ同じだ。しかし、バビロニアで「ゼロの概念」に関する哲学的な議論がおこなわれた形跡は残っていない。まったく「適当な記号がないから◯でも書いておけばいいよね」という具合だったのだ。

つまり、チューリングの数々の仕事も、そもそもは単純な発想のものであって、それにまつわる哲学的な議論というのは、チューリングが思索を深めた後に生まれてきたものではないのか。

多くの筆者は、この時間的な深まりを無視して、最高点に達したチューリングと同じ高みにたって、過去のシンプルな着想を語ってしまう。ここにチューリング本の読みづらさがあるのではないかと思う。

もちろん、これは私個人の勝手な解釈で、チューリングは子供のころから、今日のコンピューター社会を正確に予測して、デジタルの原理を創始すべく数々の仕事をしていったのかもしれない。そうだとしたら、天才というより一種のモンスターだと思うが、実際どうであったかはだれにもわからない。

そこで、私は、間違っているかもしれないが、「チューリングは最初はきわめて単純な発想で仕事をし、後に深みを加えていった」と仮定して、チューリングの仕事を紹介してみたいと思う。その方が、あるいはそうしないと、チューリングという巨人の仕事を理解することはできないからだ。

 

コミュ障だったアラン・チューリング

アラン・マシソン・チューリングは、1912年6月23日に、イギリスのロンドンで生まれた。父親は裕福な行政官で、妻とともにインドに赴任していた。執事と料理人がいるような家庭で、アランはなに不自由なく豊かな幼少期を送った。

しかし、両親はアランの教育のことを考え、アランを英国で産み、教育も英国でおこなうことにした。アランは兄のジョンとともに、父の友人宅に預けられた。両親はときおり英国に帰ってくるものの、アランが寂しい幼少期をすごしたことは想像に難くない。母親も、年に数度、帰国し、子どもたちと会うが、去るときに車の後ろを見ると、幼いアランが泣きながら追いかけてくるという回想をしている。アランには愛情が不足していた。

そのためだろうか、アランはきわめて世話の焼ける問題児に育っていった。夢見がちで非社交的、人前にでると常におどおどし、

甲高い声でしゃべる。それが周囲の失笑を誘い、ますますアランは自分の殻に閉じこもっていくようになった。アスペルガー症候群の典型的な特徴を数多くもっていたとする研究者もいる。

アランが生涯で最も人と触れ合ったのは、ブレッチレーパークでエニグマ暗号に挑んでいた時期で、そこには暗号電文を処理し、整理する仕事で、たくさんの若い女性が働いていた。ブレッチレーパークで当時働いていた女性の証言によると、アランは女性とは仕事上必要な話し以外はしたことがなく、廊下で出会っても、目をそらし、壁際によって、指で壁をなぞりながらすれ違っていったという。

アランの仕事の素晴らしさは全員が理解していたので、アランをバカにしたり、さげす 蔑んだりするような女性はいなかったが、アランを恋愛対象としてみていた女性もいなかった(ただし、この時代にアランは生涯一度だけ、ある女性と婚約をしているが、自然消滅してしまった)。

1926年、14歳で、イギリス南西部のドーセットにある上流階級の子弟ばかりが通う私立学校シャーボーン校に進学するが、そこでの評価は最低だった。「基本的な訓練をせずに、自分の好きな数学の勉強ばかりをしている」「いつも不潔で、肌は脂ぎっている。爪の先はいつも汚れて黒い。服装もだらしなく、汚れている」「どの学校へいっても、社会にでても、問題児とみなされるだろう」。最低の評価で、アランにとって学生生活は鬱屈したものだったに違いない。

数学の教師はアランの才能に気がついていたが、それでも教えた方法を拒否して、常に自分なりの方法を見つけようとするアランの態度に閉口していたようだ。「もし、数学者になりたいのであったら、彼はここで時間を無駄にしている」とまでいっているので、匙を投げてしまったのかもしれない。 さじ

それでも、そのシャーボーン校を卒業するめどがついたころ、アランには一歳年上の親しい友人ができた。クリストファー・モルコムという人物だった。

二人は、いつもいっしょに行動し、二人の共通の話題である宇宙について語りあっていた。そして、英国で科学を学ぶのには最高水準であるケンブリッジ大学のトリニティカレッジへの進学を二人で目指していた。クリストファーはみごとに合格したが、アランは失敗した。ところが、クリストファーは飲んでいた牛乳から牛結核症にかかり、進学する前に急死してしまう。アランの悲しみは普通のものではなかった。

「この世に神はいない」という考えに取り憑かれ、一気に無神論者になってしまった。そして、クリストファーの代わりに、再度トリニティカレッジに挑戦し、クリストファーの分も後世に残るような仕事をやってのけようと決意する。アランは、「クリストファーにはまた会うことができる。いつも自分といっしょにいるような気がする」と考えていた。

素晴らしい友情のようだが、これは友情ではなく、愛する気持ちだった。アランにとって、クリストファーは永遠の恋人だったのだ。当時、英国では同性愛は法に触れる行為であったために、二人の関係をあらわに、するようなことはしなかったが、今日ではこれがアランの初恋であったことがわかっている。

 

危機を迎えていた数学

翌年、アランはトリニティカレッジに合格したが、成績が足りず奨学金を受けられたなかっため、第二希望のキングズカレッジに進学した。このころ、「数学の危機」という一種の数学ブームが起きていた。

数学というのは、公理を使って、なにかを証明するゲームだ。公理というのは証明するのに使う基本ルールで、私たちがよく知っているものでは「ふたつの点があれば、直線で結ぶことができる」とか「a+bとb+a、a×bとb×aなど加算と乗算では前後を入れ替えても答えは同じになる」などだ。

このようなだれもが納得し当然と思う「公理」を使って、ある事象(たとえば三平方の定理など)を証明していくのが数学というゲームだ。そして、この時代までは、「完全な公理を用意すれば、宇宙のすべては証明できる」と考えられていた。

しかし、1930年、アランが4歳のころ、クルト・ゲーデルがこの伝統的な数学を破壊しかねない奇妙な証明をしてしまう。ゲーデルの不完全定理だ。

公理というのは、数学学会にリストが登録されているわけではなく、証明しようとするものが新たに公理をつくってかまわない。しかし、もちろんのこと、いい加減だったり、無理やりつくった公理だったりすれば、「この証明は公理に矛盾がある」などと批判を浴びることになる。

ゲーデルが発見したのは、この部分だった。証明者が慎重に慎重に公理を考案して、どこにもまったく矛盾が起きないようにしたとしよう。しかし、矛盾の起きない公理を使った場合は、必ず証明できない限界が生まれてしまう。逆に、すべてを証明できるような公理には、必ずどこかに矛盾があるということを証明してしまった。

つまり、数学は万能ではなく、限界があるということを証明してしまったのだ。完全だと思われていた数学は、実は不完全なものだったというのがゲーデルが突きつけた事実だった。これがゲーデルの不完全定理だ。

まるで、きちんと部屋のサイズを測って買ったカーペットなのに、2つの隅をあわせて敷くと、反対側の隅がずれてしまい、そちらをあわせて敷き直すと、今度は元の隅がずれてしまうような話だ。つまり、数学は完全な公理を用いて、世の中のすべてを証明できるわけではなく、公理が完全なら証明できない限界が生まれ、すべての現象を説明できるのであれば、その公理は不完全なものだと結論せざるを得ない。

ゲーデル以前の数学は、精密な公理系を設定すれば、世の中のすべてのことが論理的に証明できるという前提にたったものだった。ところが、実は数学には不完全定理という限界があることがわかってしまった。それは、数学は新たな地平を切り開いて、もう一段高い次元に入るのか、それとも数学は限界のある学問として袋小路に陥ってしまうかどうかの瀬戸際だった。これが「数学の危機」として、アランの時代に盛んに議論されたことだった。

アランは、キングズカレッジのマックス・ニューマンの数学基礎論の講義で、ゲーデルの不完全定理を学んで衝撃を受けた。そして、アランなりの方法でこの不完全定理に挑もうと夢中になっていった。

 

ディオファントス方程式に挑んだチューリング

アランが研究課題として選んだのが、ディオファントス方程式だった。

ディオファントスは古代ギリシャの数学者で、『算術』という本を著した。この本の中にはユニークな問題がたくさん載っていて、有名なフェルマーが「証明を発見したが、余白が狭すぎて書くことができない」とした、フェルマーの最終定理も、この『算術』の余白に書かれたものだった。

ディオファントスは整数を扱う代数学を研究し、彼の墓には次のような墓碑銘が刻まれているという。

ディオファントスの人生は、6分の1が少年期、12分の1が青年期であり、その後に7分の1が経って結婚し、結婚して5年で子供が生まれた。ところがその子はディオファントスの人生の半分しか生きずにこの世を去った。自分の子を失って、4年後にディオファントスもこの世を去った。

きわめて簡単な一次方程式で解けるので、暇つぶしに解いてみていただきたい。答えは84歳で、ディオファントスは14歳までが少年期、21歳までが青年期、33歳で結婚し、38歳で子どもが生まれた。子どもは42歳で、ディオファントスが80歳のときに死に、ディオファントスは84歳で亡くなった。

このディオファントスが『算術』の中で扱っていて、有名になったのがディオファントス方程式だ。ディオファントス方程式とは、変数が多すぎる方程式のことだ。

たとえば、3x-1=0というひとつの方程式にひとつの変数であれば、この変数xがいくつであるかは簡単に計算することができる。しかし、3x+4y=10のように、ひとつの方程式で変数がふたつある場合は、xとyを簡単に求めることはできない。いくつかの答えの組み合わせがでてきてしまう。このような単純なものであれば、グラフをつくってみれば、簡単に解の集合(グラフは直線になり、その直線すべてが解になる)を求めることができる。

しかし、2つの変数が2乗、3乗と高次元になっていくと、一定の方法では解けなくなるのだ。

アランが挑戦したのは、ディオファントス方程式の解法を発見することではない。「ディオファントス方程式の解を有限な手順で解けるかどうかを証明すること」だった。もちろん、アランは「有限の手順では解けない」と直感していた。これはフェルマーの最終定理を、一般のディオファントス方程式まで拡張して証明することになる。

一般的には、数にまつわる公理(a+b=b+a、a×b=b×aなど)は矛盾がないと考えられていた。ということは、このような矛盾のない公理系を使った場合、必ず証明できない問題が存在するはずだ。アランは、まず「証明できない問題が存在すること」をディオファントス方程式を例にして、証明しようとした。その証明できない実例を発見すれば、ゲーデルの不完全性定理をより細かく考察していくことができるようになるからだ。

このディオファントス方程式の問題は、1900年にパリで開催された国際数学者会議で、ファフィット・ヒルベルトが「古来より未解決な23の課題」として発表したもののうちのひとつだった。そのうちの第10問題は、「ディオファントス方程式の一般的で有限的な可解性判定方法を求めよ」というものだった。「有限的な可解性判定方法」とは、一定の手順で解ける方法があるかないかを見極めよということだ。

たとえば、中学校で習う2次方程式には「有限的な可解性」がある。2次方程式には解の公式というのがある。この解の公式は、一般的な2次の文字式を変形していくことで導きだすことができる。つまり、一定の手順を使って、機械的に解くことができる。もし、ディオファントス方程式でも解の公式がつくれのであれば、それは「有限的な可解性」があることになる。つまり、ヒルベルトの第10問題は、「ディオファントス方程式でも解の公式をつくることができるか、あるいはできないか。それを見極める方法を考えよ」というものに相当する。

一方で、そんな方法は存在しない、不可能だと証明できたら、「代数の公理を使っても解決できない問題が存在する」というゲーデルの不完全定理の実例を発見したことになる。

キングズカレッジでのアランは、寝ても覚めてもこの問題を考え続けた。

 

不完全性定理に挑むために生まれたチューリングマシン

ここで注目しなければならないのは、アランは「ディオファントス方程式が有限の手順で解ける」ことを証明しようとしたのではないことだ。これだったら、話は早い。一般的な解法を見つけてしまえば、証明は終わってしまう(もちろん、簡単なことではないが)。しかし、アランがやりたかったのは「有限の手順では解けないこと」を証明しようとしていた。いったいどのようにアプローチしたらいいだろうか?

最初にアランがおこなったのは、「人はどのように計算をしていくだろうか。その要素を細かく定義していこう」ということだった。たとえば、2+3という単純な計算でも、人はそうとう複雑な操作をおこなっている。まず先頭の数字を見る。その数字を記憶する。次を見ると加算記号が現れる。これを記憶し、計算モードを設定する。次の数字を見る。その数字を記憶する。最初に記憶した数字を呼びだす。計算モードに従って、計算操作をする。その結果をいったん記憶する。記憶した数字を解答欄に転写する。こうして、5という答えが求められる。

アランはこのような人の計算手順を要素に分解し、この要素を組み合わせて計算がなりたっていると考えた。もし、すべての計算手順の要素を完全に定義することができれば、それを組み合わせることでどのような計算だってできるはずだ。そして、重要なのは、このような計算は必ず「有限的な手順」になるのだ。

1÷3を計算すると、0・3333…となって、どこまでいっても計算が終わらず、無限の計算になってしまうように思えるが、やっていることは1÷3を延々と繰り返しているだけなので、有限な手順だといえる。あるいは、表記法を工夫して、1/3を答えにすれば、有限な手順で計算が終了する。

賢明な読者はもうおわかりのことだろう。アランは、この仮想の体系を具体的なモデルで表現した。それはテープ(メモリと考えた方が私たちにはわかりやすい)とヘッド(読み取るだけでなく、テープに書きこむこともできる)

と内部メモリ(CPU内部のレジスタ)の3つの部品からできているものだった。これがチューリングマシンで、概念的には今日のコンピューターの原型になる。

ここでチューリングマシンの構造について説明しておこう。なお、アラン自身は計算機械と呼んでいるだけで、チューリングマシンと名づけられたのはずっと後のことだ。チューリングマシンの部品は、テープ、読み書きヘッド、本体の3つだ。テープには1と0の数字及び空白のいずれかが書かれていて、それをヘッドが読み取る。また、ヘッドはテープに数字を書きこむこともできる。また、本体の中にはプログラム(アルゴリズム)が格納されている。

そのプログラムとは、たとえば次のようなものだ。

状態1:1、P1、R →状態1

状態1: 、P1、R →状態2

状態2:1、P1、R →状態2

状態2: 、P 、L →状態3

状態3:1、P 、N →状態4

状態4:停止

チューリングマシンのプログラムは、「状態」「読み取ったテープの内容」「書きこむ内容」「ヘッドを移動させる方向」「ジャンプ先」という5つの要素からできている。テープには1、0、空白のみ読み書きできる。Pは「書きこみ命令」だ。ヘッドを移動させる方向は、左(L)、右(R)、移動しない(N)の3種類がある。

たとえば、1行目の「状態1」は、「テープの内容が1であったら、1を書きこみ、ヘッドを右に移動させ、次に状態1を実行せよ」ということになる。2行目の「状態1」は、「テープの内容が空白であったら、1を書きこみ、ヘッドを右に移動させ、次に状態2を実行せよ」ということになる。

これはいったいなにをしているのかわからないと思うが、実は足し算プログラムなのだ。テープに「1111 111」と書いてあった場合に、このプログラムを実行すると、「1111111」となって、4+3の答えが7であるということが求められる(2進数ではないことに注意。1の数で数を表している)。

このプログラムは、テープの内容が1であったら、1を書きこみ、ヘッドを右に移動させ、最初の空白(数の区切り)にも1を書きこみ、数字の終わりの空白を検出したら、ヘッドを左に戻して、最後の1を消すというものだ。これで足し算が実現できているが、足し算そのものをおこなっているわけではなく、テープの読み書き、ヘッドの移動という単純な行動で、足し算ができるというのがミソだ。

 

すべての問題を解けるチューリングマシン

アランは、このチューリングマシンを使って、ディオファントス方程式を解くプログラムをつくろうと考えたわけではない。ここからは、ディオファントス方程式を離れて、アランは「有限の手順では、解くことができない問題が存在する」ということを証明しようとしている。

そのためには、チューリングマシンが「有限の手順の機械」であることを証明して、それから「チューリングマシンにも解けない問題が存在する」ことを証明すればいい。

チューリングマシンが有限の手順の機械であることを証明するのは簡単だ。プログラムの1行だけを見ると、「読み取るテープの内容が0、1、空白の3種類」「テープに書きこむ内容が0、1、空白の3種類」「ヘッドの動く方向が左右、停止の3種類」しかない。つまり、1行のプログラムの内容は3×3×3=27通りしかないのだ。これは明らかに有限だ。

そして、この1行のプログラムは、通常の計算よりも細かい要素なので、もし有限の手順で解ける解法であれば、必ずチューリングマシンのアルゴリズムとして記述ができる。つまり、チューリングマシンは有限の手順で解ける問題であれば、必ずその解法をアルゴリズムとして記述できるマシンなのだ。

では、もし、有限の手順で解ける問題であればなんでも解くことが可能なチューリングマシンでも解けない問題があるとしたら、それはどういうことになるだろうか? それは、この世の中には「有限の手順では解けない問題が存在する」ということだ。これは、まさにゲーデルの不完全性定理の代数版だ。

アランは、ここまで考えを積み重ねてきて、ようやく道が見えてきた。それは「チューリングマシンでも解けない実例を探す」ことだった。そうすれば、「この世の中には有限の手順では解けない問題が存在する」ことの証明になる。

 

チューリングマシンにも解けない問題が存在した!

さて、いよいよアランが目指していた「有限の手順では解けない問題がある」を証明するときがやってきた。ちなみに、ディオファントス方程式が有限の手順で解けるか解けないかは、すでにアランは問題にしていない。アランは、すでに数学全体に思考をめぐらせているのだ。実際、ディオファントス方程式が有限な手順では解けないことが証明されたのは1970年のことになる。

アランが発見したのは「停止判定チューリングマシン」というものだ。この停止判定チューリングマシンは、別のチューリングマシンの紙テープとアルゴリズムをなぞるように検査して、そのチューリングマシンがちゃんと停止するか、それとも無限ループに入ってしまって永遠に停止しないかを判定する。停止判定チューリングマシンは、検査した対象のチューリングマシンが停止するなら「停止(1とテープに書きこむ)」、無限ループに入ってしまったら「停

止しない(0とテープに書きこむ)」を出力する。

無限に動き続けてしまうチューリングマシンをどうやって「停止しない」と判定するのか首をかしげる人もいるかと思うが、チューリングマシンが停止しないというのは無限ループに入ってしまったような場合だ。いわば、循環小数を求める計算を始めたような場合なので、この場合は、「同じことを何度も繰り返している」ということを検知すれば「停止しない」と判定することができる。

要は、検査対象のチューリングマシンを動かして、停止コマンドを見つけたら1、同じループを繰り返したら0と出力すればいいのだから、このようなチューリングマシンはつくれそうだ。

ここでアランは、だいたんな飛躍をする。停止判定チューリングマシンを改造して、検査対象のチューリングマシンが停止をするなら、自分が無限ループに入るというものにする。停止を出力する代わりに、

状態N:0、P0、R →状態N

状態N:1、P0、R →状態N

状態N: 、P0、R →状態N

のようなプログラムを入れてやればいい。こうすればテープの内容がなんであれ、0を書きこんで、ヘッドは永遠に右に移動し続けることになる。テープの長さは無限にあるという前提なので、このチューリングマシンは永遠に停止しない。検査対象のチューリングマシンが無限ループに入ってしまったら、「停止しない」を出力することはさきほどの停止判定チューリングマシンと変わらない。

ここで、アランは再びだいたんな発想の飛躍をして、ある思考実験をする。それは「この改造版停止判定チューリングマシン自身を、改造版停止判定チューリングマシンで判定させたらどうなるのか?」というものだった。なんだか、頭がおかしくなりそうな話だが、結論は簡単だ。

もし、この改造版停止判定チューリングマシンが停止するなら、検査する方の改造版停止判定チューリングマシンは無限ループに入ってしまって停止しない。もし、この改造版停止判定チューリングマシンが無限ループに入ってしまうのであれば、検査する方の改造版停止判定チューリングマシンは「停止しない」と出力して停止する。「停止するなら停止しない。停止しないなら、停止する」。中身は同じチューリングマシンなのに、これはどうしたことだろうか? 明らかに矛盾するのだ。

もうおわかりだと思うが、アランは背理法を使っているのだ。このような矛盾が起きるということは、前提が間違っていたに違いない。その前提とは「停止判定チューリングマシンが存在する」というものだ。しかし、その前提に立つと明らかな矛盾が生じるので、背理法によって「停止判定チューリングマシンは存在しない。

どうやってもつくれない」と結論することができる。

これは、すなわち、「チューリングマシンにもできないことがある」ということだ。ようやく、アランは、これで「有限の手順では解けない問題がある」ということを証明できた。

重要なのは、アランはこのチューリングマシンを、コンピューターを組み立てようとして考案したというわけではないことだ。あくまでも思考実験のために使うもので、このチューリングマシンを使って、有限手順の計算には限界があることを証明しようとしたのだ。

ある意味、コンピューターの発展とはまったく異なるところからでてきた発想だが、「人間がおこなっている計算手順を要素を分解して組み合わせる」という着想を合理的に突き詰めていくと、コンピューターと同じ構造にたどりついたというのが正しい見方だろう。

もちろん、アランはこのチューリングマシンを使って、さまざまな発見をしており、その発見は、後に実際のコンピューターを開発する際、あるいはコンピューター言語を開発する際に大いに参考されているので、「コンピューターサイエンスの創始者」であることは間違いない。むしろ、コンピューターなど影も形もない時代に、大脳皮質の中だけで、これだけ精密なモデルを構築していたことに、アランの偉大さがあるのだ。

このチューリングマシンを使った「数学の不完全性の証明」は大きな反響を巻き起こした。ゲーデルの不完全性定理は論理学的な証明であり、とても難解なものだった(ゲーデル自身もゲーデル数と呼ぶ概念を導入して、代数学的に論じられるように工夫をしている)。専門の数学者であっても、読んでいるだけで頭が痛くなってくるし、どこかに誤りがありそうで、よくわからない。反論をしたくても、どこに問題があるかわからなく、しかもなんとなくだまされた気になってしまう。一方で、アランのチューリングマシンは明快だ。具体的

な仮想機械を使って証明することで、だれにでも数学の不完全性が理解できるのだ。

アランは1936年、24歳のときに、その成果を「計算可能な数について、決定問題への応用とともに」という論文にまとめた。そして、奨学金を得て、米国のプリンストン大学に留学をして研究をすることになる。

米国では、わずか1年半で博士論文を仕上げてしまった。数学者としては順調すぎる成長ぶりだった。

プリンストン大学では、あのフォン・ノイマンと知り合い、年俸1500ドルでアシスタントにならないかと誘われた。しかし、アランは、その話を断って英国に帰ることにした。第2次世界大戦が始まろうとしており、自分も英国のために役に立ちたいと考えたからだ。

 

エニグマに挑んだアラン・チューリング

第2次世界大戦が始まる前年、ドイツとの戦争が避けられないと判断した英国政府はロンドン近郊のブレッチレーにある広大な屋敷を買いあげた。ここに防空学校を設立するという話だった。しかし、実は政府はここに暗号解読学校を設立した。

翌年ドイツとの戦争が始まると、このブレッチレーの屋敷には数学者と言語学者などが集められ、「ブレッチレーパーク」あるいは「ステーションX」という暗号名で呼ばれることになった。その存在は極秘扱いで、英国でも1970年代になってようやくBBCなどが報じ始めたほどだ。このブレッチレーパークにアランも招集されたのだ。

アランたちが挑んだ暗号は、当時、世界最強とも解読不可能ともいわれたヒトラーのエニグマ暗号だった。

エニグマとは「謎」という意味だ。実をいえば、アナログ暗号の原理はきわめて単純だ。

換字式暗号なのだ。たとえば、AをBに、BをCにと1文字ずらしして変えると、HACKERはIBDLFSとなる。これでも立派な暗号になり、エニグマ暗号もこのような換字式暗号の一種だった。ところが、換字の方式、つまり換字アルゴリズムが図抜けて複雑だったのだ。さきほどの「一文字ずらし」というアルゴリズムでは、法則性が単純すぎて簡単に見破られてしまう。少しトレーニングを積んだ解読者であれば、こんな単純な暗号は計算などもせずに目視で読めてしまう。

では、エニグマ暗号のアルゴリズムはどのように複雑だったのだろうか。エニグマ暗号に使われた主要部品は、ローターと呼ばれる26個の歯がついた歯車だった。この歯車の表と裏は26本の配線で繋がれている。

表側のAから入った電気信号は配線を伝わって裏側の別の文字に伝わる。つまり、Aに入った信号をシャッフルして別の文字として出力するわけで、ここで換字をおこなっているのだ。配線は規則性をもたないようにつくられているが、同じローターが製造され、すべてのエニグママシンに同じローターが装着できる。

しかし、これだけであれば「ランダムに入れ替える換字暗号」にすぎず、ローターを手に入れれば(実際、英国は実物のエニグママシンを手に入れていた)暗号は簡単に解読できてしまうし、この程度の暗号ならローターの配線がわからなくても、通信文をある程度集めれば高校生でもじゅうぶんに解読できるだろう。エニグマ暗号の複雑さは、この先にあるのだ。

ローターは1枚ではなく、合計3枚が製造されていた。もちろん、それぞれに内部配線は異なっている。平文はこの3枚のローターの内部配線を串刺しのように伝わって、複雑に変換されていく。Aという文字が1枚目のローターでCに変換され、2枚目のローターでさらにKに変換されて、3枚目のローターでさらにLに変換されるなどだ。

それでも、もしローターが固定されているなら、ある文字が別の文字に変換されるだけで複雑でもなんでもない。しかし、このローターは回転するようにできているのだ。エニグマ暗号機はタイプライターにこの3枚のローターがセットできるような形をしているが、1文字をタイプするごとにいちばん右のローターが1歯分回転する。こうなると、変換される文字がガラリと変わってしまう。つまりエニグマ暗号は1文字ごとに異なる文字変換がされる暗号システムなのだ。

ローターには1ヶ所ツメがついていて、このツメの位置が所定の位置にくると、左隣のローターを1歯分回転させる。つまり、打った文字が26字に達する前に、必ず真中のローターも1歯回転するのだ。さらにこの真中のローターにもツメがあるので、いちばん左側のローターも回転する。エニグマ暗号は、1文字ごとに変換の仕方が異なっていく。すべてのローターが回転して、最初と同じ位置に戻るまでには、26の3乗字=1万7576文字までの文であれば、同じ変換方式が使われずに済むのだ。ほとんどの通信文はそこまで長くないので、通信文は各文字ごとに異なる方式で文字変換がされていることになる。

さらにエニグマを複雑にしているのが、ローターの初期設定だ。3枚のローターは着脱式で入れ替えることができる。3枚のローターはそれぞれに内部配線が異なっているので、入れ替えるだけで換字法が変わる。3枚のローターを並べるやり方でも、3×2×1=6通りがある。

さらにそれぞれのローターの歯ごとにAからZの文字が刻まれていて、いちばん手前に表示される文字を設定することで、ローターの初期位置を変えることができるのだ。ローターの初期位置が異なれば、当然ながら換字方法は違ったものになる。これは各ローター26の設定方法があるから、26の3乗、つまり1万7576通りあり、さきほどの6通りとあわせて、結局エニグマの初期設定には10万5456通りあることになる。

この他プラグボードという機構も加わって、この組み合わせの数は20桁の膨大な数に達する。ただし、プラグボードは、単純に変換された文字をさらに別の文字に変換する機構で、暗号解読をする上では無視できることが発見されたので、ここで詳しく述べることはやめておこう。

いずれにしても10万通り以上の換字法があるエニグマ暗号を人力で解読しようとするのは無理だということだ。アランがエニグマ暗号に挑んだころには、ローターが5種類に増やされるなど、さらに難易度があがっていた。ローターの組み合わせは5×4×3=60通りになり、エニグマの換字方法は少なくても100万通りに達していたのだ。

なお、エニグマ暗号機の仕組み、そしてその解読にあたったポーランドのレイヤフスキーと英国のアラン・チューリングの話は、レトロハッカーズ第2巻『史上最強のエニグマ暗号が暴かれた日:アラン・チューリングとブレッチレーパーク』で詳しく紹介している。興味のある方は、そちらもあわせて読んでいただけると幸いだ。

 

ポーランドが作成したエニグマ設定データベース

このようなエニグマ暗号をドイツ軍は次のように運用していた。まずその日だけに使う日鍵が記載された暗号帳が各部隊に配布されていた。もちろん、この暗号帳の内容は極秘扱いで、水に溶けやすい水溶性インクで印刷されていた。もし、敵に奪われそうになった場合は、海や川に投げこむだけで、暗号の秘密は守られるのだ。ドイツ軍が暗号が解読されているらしいと感じた場合は、すぐに内容は改定され、新しい暗号帳が配布される。

この暗号帳に書いてあるのは、日付とローター設定と日鍵だ。たとえば、「1月15日、(3、1、2)、CJX」などと書いてある。1月15日、暗号担当者はエニグマ暗号機を取りだし、3番ローター、1番ローター、2番ローターの順にセットする。それから各ローターを回転させ、手前の窓にCJXが見えるようにセットする。この日にエニグマ暗号機を使う場合は、必ずこの設定で使うようにする。

暗号文を送るときは、まず通信鍵を担当者が勝手に決める。通信鍵も3文字で、この通信だけに使う鍵だ。通信鍵は、通信ごとに変える決まりになっている。この通信鍵をXBTと決めたとしよう。担当者は、まずさきほどの日鍵による設定で、XBTXBTと通信鍵を2回タイプする。通信鍵を2回送るのは、通信状態が悪い場合にも伝えられるようにするためだ。

通信鍵をタイプしたら、ローターを回転させて、通信鍵であるXBTにセットしなおす。この後平文を入力する。すると暗号化された暗号文が表示される(といっても1文字タイプするごとに文字のランプが点灯するという方式だから、1文字ずつ書きとめていかなければならない)。これを通常のモールス通信で打電する。

受け取った側も、同じ暗号帳を見て、ローターを(3、1、2)、CJXとセットする。そして受け取った暗号文の最初の6文字を入力すると、XBTXBTという平文が現れる。これが通信鍵なので、ローターをXBTにセットしなおし、それから残りの暗号文を入力すると平文が現れるという仕組みだ。

この暗号を解読するきっかけをつくったのは、ポーランドの数学者マリヤン・レイヤフスキーだ。彼は、複雑なエニグマ暗号の中からわずかな規則性を見つけようとした。

レイヤフスキーが注目したのは、XBTXBTと通信鍵が2度繰り返される点だ。このXBTXBTがCJEQITと暗号化されたとしよう。すると、この日の日鍵の設定下では、1文字目のXはCに変換される。ところが3文字あと(当然ローターは回転している)では、同じXがQに変換される。つまり、その日鍵の設定下では1文字目のXはCに変換されるが、4文字目のXはQに変換される。これは一種の規則性だ。

これだけだとなんら手がかりはないが、日鍵は1日同じものが使われるので、他の通信文では、たとえば通信鍵がEITEITと送信されるだろう。この日の通信文を集めてくれば、1文字目と4文字目の関係の対応表がつくれるはずだ。たとえば、次の図のようになる。

解読者には元の平文の文字がなにであるかはわからない。わからないが、とにかくその文字はこの日の日鍵では、1文字目ではAに変換され、同じ文字が4文字目ではIに変換される。この表は、同じ文字が1文字目と4文字目でどう変換されるかを対応させたものだ。

レイヤフスキーは、この対応表がこの日の日鍵の指紋になると考えた。この表は、もちろん日鍵が異なれば、がらっと変わる。なんとか、この表の構造のようなものを見つけることはできないだろうか。

レイヤフスキーは、試行錯誤のすえ、文字遊びのようなことを始めた。BはGに対応する。では、Gは?と見ると、表からTに対応することがわかる。ではTは?と見ると、Vに対応する。レイヤフスキーはこのような対応の連鎖をすべて紙に書きだしてみた。

B→G→T→V→O→F→B

Bに戻ってしまった。以降は同じ連鎖をたどるだけで、一種のループになる。すべてのループを書きだしてみると、

A→I→X→C→Q→M→D→K→Z→E→L→Y→N→S→A

B→G→T→V→O→F→B

H→R→W→P→U→J→H

14文字のループが1つ、6文字ループが2つ現れた。ケースによって、1文字ループから26文字ループまで現れる可能性がある。このループの数を文字数順に(0、0、0、0、0、2、0、0、0、0、0、0、0、1)と書き表しておこう。

同じようにして、通信鍵の2文字目と5文字目、3文字目と6文字目のループ構造を調べることができる。すると、たとえば、次のようなループ構造が現れるだろう。

(0、0、0、0、0、2、0、0、0、0、0、0、0、1)

(2、0、2、2、2)

(0、0、0、1、3、0、1)

面白いのは、プラグボード(文字を入れ替える機能)の設定にかかわらず、このループ構造は同じになることだ。上記のループ構造から、任意の2文字を入れ替えてみていただきたい。ループ構造の数値は変わらないのだ。

日鍵の設定は、ローターを入れる順序と、各ローターの初期設定により決まるので、さきほど計算したように10万5456通りある。レイヤフスキーは、すでに実物のエニグマ暗号機を入手していたので、すべての日鍵設定のループ構造を調べた。大量の動員をして、毎日500個ずつ調べ、約200日で、すべての設定のループ構造が明らかになった。

同じ日の通信文を複数手に入れれば、ドイツ軍が使っている日鍵下でのループ構造が調べられる。それから、調べあげたループ構造データベースを見れば、日鍵がわかる。日鍵がわかれば、通信鍵がわかり、通信鍵がわかれば暗号が解読できるというわけだ。

 

アラン・チューリングが考案したクリブアタック

こうしてポーランドのレイヤフスキーはエニグマ暗号を解読したが、ドイツ軍もバカではない。暗号が解読されているらしいことを察知すると、ローターの数を増やし、5枚のうちから3枚を使うようにした。さらには、4番目の追加ロータースロットも増設した。これだと、ローターの組み合わせが5×4×3×2=120通り、ローターの初期設定は26の4乗、合計で5483万7120通りとなり、レイヤスキーのようにループ構造のデータベースを手作業でつくっていく方法では無理になった。毎日500個ずつ調べていっても、全解読までに300年以上かかってしまうことになる。

そこで、いよいよ英国のブレッチレーパークの出番となる。中心となったのは、もちろんアラン・チューリングだ。アランは、レイヤフスキーとは異なったアプローチを考えた。それは、後にクリブアタックと呼ばれることになった手法だ。クリブとは「盗用、カンニング」などの意味で、今の言葉で言えばチートに近い互換のある言葉だ。

アランは、ドイツ軍の通信文で頻繁に使われそうな言葉、たとえばKommandeur(司令官)がどこの場所に入っているかを一気に決定しようとした。たとえば、暗号文が次のようなものだったとしよう。

AAGXH UKYUK NHGXH TKYUA NCLCWBPTAK NEPMF IUDOE PKAIQ XZCTI

まず先頭からの「AAGXHUKYUK」がKommandeurである可能性はあるだろうか? ないのである。なぜ、そういえるかというと、次の図のようにUがuという同じ文字に変換されることになってしまうからだ。エニグマ暗号機にはリフレクターと呼ばれる独特な機構が組みこまれていて、このリフレクターという発明があったために、エニグマは実用的な暗号機となった。しかし、アランはそこに注目をして、ある文字が同じ文字に変換されることはないということに気がつき、暗号を解読するテコにしたのだ。

リフレクターは、3枚のローターに取りつけられた反射板だ。Aのキーを押すと、Aキーに接続された線を伝わって電気信号が流れていく。その電気信号は、3枚のローターを通る間に、シャッフルされて、リフレクターにたどりつく。リフレクターもローターと同じように内部にシャッフルするための配線をもっているが、ローターと異なるのは、右から入った信号を左に出力するのではなく、再び右に戻すことだ。すると、信号は再び3枚のローターを通って、Aが暗号化されたGのランプを点灯させる。このGを読み取って、モールス信号で打電すると暗号文が送れるわけだ。

このとき、AのキーとGのランプは、1本の回路で結ばれていることになる。ここがエニグマ暗号機が高く評価された点だ。このときとまったく同じ設定のときに、Gキーを押すとどうなるだろうか? AとGは1本の回路で結ばれているのだから、Aのランプが光ることになる。

つまり、エニグマ暗号機は、設定を同じにさえすれば、平文を入力すれば暗号文が出力され、暗号文を入力すれば平文が出力されるのだ。同じエニグマ暗号器を使って、暗号化と復号化ができる。エニグマ暗号機は、実用を考えた仕組みになっていたのだ。

ところが、これは一種のセキュリティホールだった。リフレクターという機構の構造上、ある文字が同じ文字に暗号化されることはない。回路がつくれないからだ。ランダムに変換されるのがもっとも強力な暗号だが、ランダムであれば1/26の確率で同じ文字に変換されなければならない。アランは、目ざとく、ここに目をつけたのだ。

では、暗号文の2文字目以降「AGXHUKYUKN」がKommandeurである可能性はあるか。同じ文字に変換されている箇所がないので、その可能性は否定できない。では、確かめるためにはどうしたらいいだろうか?

最もシンプルな方法は、エニグマ暗号機を取りだして、日鍵設定(1、2、3)(AAAA)にセットし、kommandeurと入力してみて、 AGXHUKYUKNになるかどうかを確かめてみればいい。ならなければ、次は日鍵設定(1、2、3)(AAAB)を試し、最後の(3、4、5)(ZZZZ)までの5483万7120通りの設定で、kommandeurを入力してみることだ。もし、どこかでAGXHUKYUKNが現れれば、一気に日鍵設定がわかり、暗号文は解読できる。なければ、そこはkommandeurではなかったわけだから、次は、暗号文の3文字目からがkommandeurではないかと推定して、同じことを繰り返していく。

しかし、これを手作業でいちいちタイプしていたのでは、もちろん時間がいくらあっても足りない。そこで、アランはこの作業を自動化する機械を考案した。それが後にチューリングボンベと呼ばれる機械で、世界最初のコンピューターという人もいる。ただし、現在のコンピューターのようなプログラムを実行するタイプの計算機ではなかったことから、多くの場合はコンピューターとは認められてはいない。

では、このボンベの構造はどうなっていたのだろうか。実は、原理としてはエニグマ暗号機を数台、電線で結線したという単純なものだった。

まず、AGXHUKYUKNがkommandeurであるかどうかを確かめる場合、まず次のようにループになる部分を見つける。アランはこれをクリブループと呼んだ。

この3箇所にわたるクリブループを見つけたら、3台のエニグマ暗号機を用意する。1文字目、5文字目、9文字目のループなので、3台のエニグマ暗号機はそれぞれぞれ同じ初期設定にし、2台目は4文字進んだ状態、3台目は8文字進んだ状態にセットする。そして1台目のAの出力と2台目のaの入力を結線し、2台目のUの出力と3台目のuの入力を結線し、3台目のKの出力と1台目のkの出力を結線する。

このループは、もし「kommandeur」が「AGXHUKYUKN」になるのであれば、回路が成立するはずだ。回路の途中に豆電球でもつけておけば点灯することになる。しかし、「kommandeur」が「AGXHUKYUKN」以外の暗号文に変換されるのであれば、回路は成立しないだろう。

この状態に3台のエニグマ暗号機をセットし、あとは初期設定を自動的に変更していける機構をつけ加えた。つまり、すべての初期設定をしらみつぶしに調べていって、「kommandeur」が「AGXHUKYUKN」に変換される初期設定を見つけようというのだ。初期設定は機械的に変更されていくので、解読者はただ見守って、ランプが点灯をするのを待っていればよかった。

実際には、エニグマ暗号機のローターを内部に組みこんだ機械で、動作中はローターが回転するので、話し声が聞こえないほどやかましい音をたて、うまくヒットすると、輪をかけてやかましいベルが鳴り響き停止するといった機械だったようだ。

このようなクリブは、連合軍の他の部署からの情報も役に立った。多くはドイツ兵捕虜の尋問によってもたらされたものだ。その情報によると、ある電文の続報を送信する場合、冒頭に「2300の続き」=FORTZWEI DREI NUL NULなどと打つ決まりになっていた。2300とは23時00分に送信した電文の意味だ。

これなどは、送信履歴を調べてあてはまりそうな電文を推測し、その送信時間をクリブにして、ボンベにかければ、きわめてスピーディーにローターの設定が特定できたという。

アランは、もちろん、この他にもドイツ軍の運用上の欠点を徹底的についた。たとえばドイツ軍は前日の日鍵によるルーター設定と翌日の日鍵によるルーター設定をまったく重ならないようにするルールをつくっていた。ある日が(1、3、4)のルーター設定だとすると、翌日は(5、3、2)という設定は使わない。なぜなら、3番ルーターが2日続けて同じ位置にきてしまうからだ。ドイツ軍は、それで日鍵のセキュリティレベルがあがったと考えていたが、実は逆で、これは初歩的な誤りだ。なぜなら、ある日が(1、3、4)であったら、翌日は(1以外、3以外、4以外)の設定を使わざるを得ず、本来なら5×4×3=60通りのルーター設定を調べなければならないが、この運用の欠点を知っていれば、調べなければならない組み合わせはかえって少なくなるのだ。

また、ローターの初期設定、たとえば(AXE)などについても、ひと月の間に同じ設定を使ってはならないというルールもあった。これも一見、日鍵のセキュリティレベルをあげるように見えるが、現実は逆で、とくに月末は調べなければならない初期設定が大幅に減る。その月に使った初期設定はもう調べる必要がないからだ。

そのため、アランたちは月末になると、だいたい午前中で仕事は終わり、午後はチューリングボンベが日鍵を発見するのを待ちながら、テニスをしたり、お茶を楽しんでいたという。だいたい1つのクリブループを調べるのに15分程度ですんだという。

このボンベは、確かに現在のコンピューターとは大きく異なっている。回路が内蔵された歯車=ローターを回転させて、回路が成立する状態を探すだけの機械だからだ。デジタル的な考え方はまったくなく、アナログ式だった。しかし、アナログコンピューターとしてはもっとも複雑なものだっただろう。

 

エニグマを上回る複雑さのタニー暗号

アランはエニグマ以外にも、ブレッチレーでローレンツ暗号機の解読を手伝っている。このローレンツ暗号機は、連合軍側は「タニー」と呼んでいたもので、エニグマ以上の複雑さだった。しかも、30台程度しか製造されず、ドイツ軍の中枢の人物のみが使うことが許されたもので、当然、きわめて機密性の高い内容がやりとりされていた。

タニーは、エニグマのように暗号化された文字ランプが光るのを読み取って、モールス信号で送るなどという手間が必要なかった。ただキーボードから電文を入力すれば、内部で暗号化され、そのまま暗号化された電気信号が送り先のタニーに伝わる。受け取り側は、なにもしなくても、タニーに接続されたプリンターから復号化された電文が印刷されてくるので、それを読めばいいだけだった。

このタニーの暗号化の仕組みはきわめて強力だった。原理としては、文字をコード化し、そこに擬似乱数を加えてしまうという方法だったのだ。もし、擬似ではなく、精度の高い乱数を使うことができたら、原理的には解読が不能になる最強の暗号だ。

今、「加える」といったが、タニーでは厳密には排他的論理和(XOR)をおこなう。これは、加える2つの数をビットごとに比べて、同じであれば0、異なっていれば1とするものだ。タニーは、文字を2進数のコードにして、そこに2進数の擬似乱数を排他的論理和演算して、暗号文をつくりだすという方式だった。

これはきわめてうまいやり方だった。受け取り側の復号化が簡単になるのだ。たとえば、平文の文字コードが1011で、使用する擬似乱数が0101だったとしよう。この2つの数の排他的論理和をとると1110となる。これが暗号文として送られる。1110を受け取った側では、同じ擬似乱数0101をやはり排他的論理和演算すると、平文の1011がでてくるのだ。送る方も受け取る方も同じ擬似乱数を排他的論理和演算するだけで、暗号化もできるし復号化もできるというものだった。

これはタニーの素晴らしい工夫だったが、エニグマと同じように、この素晴らしさが同時にセキュリティホールにもなっていた。なぜなら、ブレッチレーの解読班は、擬似乱数がいくつであるかを知ることなく解読する方法を見つけてしまったからだ。

今、同じ擬似乱数kを使って、2つの文字が暗号化されているとしよう。この暗号化された2つの文字は、(x+k)、(y+k)として表すことができる。この暗号化された2つの文字の排他的論理和を求めると、x+yとなるのだ。擬似乱数kはどこに消えてしまったのか? タニーの演算は排他的論理和であることを思いだしてほしい。排他的論理和は、各ビットを比べて、同じであったら0、異なっていたら1にするというものだった。つまり、同じ数同士の排他的論理和を求めると、どのビットも同じなのだから、必ず0になるのだ!

ブレッチレーの解読班がとったのは、次のような方法だった。まず電文の中から地名クリブ、たとえばLONDON、OXFORDと思われる暗号部分を抜きだし、そこの排他的論理和を求めてしまう。すると、6文字のよくわからない文字が得られるが、擬似乱数部分は消えて、単純に地名を2つ排他的論理和演算したものになっている。あとは、片っ端からありえそうな地名を当てはめていき、この文字列に排他的論理和演算をしてやる。あたっていれば、その地名が消えて、意味のある地名が浮かびあがってくる。それはもうひとつの別の地名のはずだ。

あたっていなければ、意味のない文字列がでてくるだけだろう。もちろん、実際の解読はこんな簡単ではない。なぜなら、使われる擬似乱数は1文字ごとに変わっていくからだ。擬似乱数はどうやって生成されているのか、それは膨大な統計処理をおこなって、周期的な特徴を割りだし、擬似乱数の生成法を推定する必要があった。

そのためには、手作業などでは無理で、タニー解読班のマックス・ニューマンは、電子計算機を開発するように迫られた。これが、コロッサ

スだ。

コロッサスは1943年12月に完成した。暗号文がパンチされた紙テープから、毎秒5000文字を読みこみ、擬似乱数の規則性を発見し、さきほどのクリブアタックに使えそうな箇所を指摘するという電子計算機だった。1946年2月に完成エニアック ENIACよりも早くに開発された電子計算機だったが、暗号解読専用計算機であったこと、英国政府が戦後もその存在を秘密にしていたことなどから、〝世界初のコンピューター〟と呼ばれることは少ない。

アランは、タニーの解読には深くは関わっていない。アランの属していたのはあくまでもエニグマ解読班で、タニー解読班では、助っ人として数週間手伝ったにすぎない。それでも、アランは、この排他的論理和で乱数部分を消去し、2つの加えた文字列から片方を推定して解読していくクリブアタックの方法を考案してしまった。

その後、アランは再びエニグマ解読班に戻ったので、コロッサスの開発にはまったくタッチしていない。しかし、そのとき、アランは別の電子デバイスプロジェクトを立ち上げていた。ブレッチレーパークから数km離れたハンスロープパークにある仮兵舎を仕事場としてデリラと呼ばれる暗号音声通話機の開発を始めるのだ。

これはまさにタニーの音声版だった。音声データをデジタルサンプリングし、そこに擬似乱数を排他的論理和演算する。これを普通の電話回線や無線で送れば、盗聴されても雑音にしか聞こえない。しかし、受け取る側では同じ擬似乱数を排他的論理和演算してやれば、元の音声が復元できるというものだ。

このデリラは、回線状態がいい環境ではうまく動作したが、ノイズを拾いやすい環境で使うと、アラン自身の回想によると「突然、ライフル銃を打ったようなパーンという大きな音がした」という現象が起こる。通信担当者は、小さな音ですら聞き逃すまいと、ヘッドフォンをして聞いているのだから、なかなか実用とならなかった。

しかし、数学者であったアランが、チューリングボンベ、デリラと実際の電子機器の開発にたずさわった経験は大きかった。アランには、ぜひ、実際につくってみたいアイディアがあった。それは、若いころから暖めてきた万能チューリングマシンだった。

 

コンピューターの原理を備えていた万能チューリングマシン

万能チューリングマシンは、アランが24歳のときに発表したチューリングマシンを拡張したものだ。チューリングマシンは、与えられたプログラム通りの仕事しかできない。しかし、自由にプログラムを与えられる仕組みさえあれば、チューリングマシンはいろいろな仕事をすることができる。

アランは、チューリングマシンで使うテープ部分を3つの領域にわけた。ひとつは従来どおり、記録されているデータを読み書きする部分(データ部)だ。もうひとつは、プログラムをあらかじめ書いておく部分(プログラム部分)だ。そして、最後にチューリングマシンが計算のために使う作業部分だ。

万能チューリングマシンは、まずプログラム部分にヘッドを移動し、そこに書かれている命令を読み取る。

それからその命令に従って、データ部の数値を読み書きし、次の命令を読むために再びプログラム部を読みにいくという動作をする。

これは、アラン自身、はっきりと意識していたわけではないが、いわゆるプログラム内蔵方式で、いわゆるノイマン型コンピューターのかなめ 要となるアイディアだった。プログラム内蔵方式の利点を考えるには、プログラムを

内蔵していない方式と比べてみるとわかりやすい。

プログラムを内蔵していないコンピューターの典型がENIACだ。ENIACは、電卓を線で結んだような構造をしている。「2倍する電卓」「6を加える電卓」…などを線で結び、最初に数値を入力すると、その数値がリレーのように次の電卓に送られ、最終的な答えがでてくるというものだ。異なる計算をしたいときには、線をつなぎ変えてやらなければならない。ENIACの場合は、大砲の弾道の飛び方を計算する目的のために開発されたので、これでよかったが、複雑な計算はむずかしかった。

このようなプログラムを内蔵できないコンピューターでは、今日のプログラミングでごくあたり前に使われる条件分岐、ジャンプといったことができず、たとえば「変数aが10より大きくなるまで、aに1を加えていく」といったことができない。つまり、プログラムを内蔵できないコンピューターは電卓での計算を自動化したもので、いわゆるコンピューター的な複雑な判断はできないのだ。このような複雑な計算、判断ができるのがプログラム内蔵方式の大きなメリットだった。

アランは、このプログラム内蔵方式について、24歳のときに書いた「計算可能な数について、決定問題への応用とともに」ですでに触れていて、公平に見て、最初にプログラム内蔵方式=ノイマン型コンピューターのアイディアを公表したのはアランだということができる。ここがアラン・チューリングが「コンピューターの概念を創始した男」といわれるゆえんだ。

ENIACやその次世代機EDVACの開発に携わったフォン・ノイマンは、当然アランの論文を知っていた。知っていたどころか、ENIAC、EDVACの主要な開発メンバーに読むことを義務づけていた。ENIACがプログラムを内蔵しない方式であるこの限界に気がついていた中心的な開発メンバーであるジョン・モークリーとプレス・エッカートは、ノイマンとの議論の中でプログラム内蔵方式の考え方を具体的にしていった。それがなぜ、今日、プログラム内蔵方式が「ノイマン型」と呼ばれるようになったのかについては、レトロハッカーズ第6巻『真空管と十進法:世界初のコンピューター、ENIAC』をお読みいただきたい。

しかし、アランにしても、ノイマンにしても、モークリーとエッカートにしても、プログラム内蔵方式がそれほど革命的なアイディアだとは思っていなかったかもしれない。複雑な計算を機械にさせるには、プログラムを内蔵させる方式にするのは当然のことであり、この4人であれば、人から教わらなくても、自分でプログラム内蔵方式の考え方にたどりつくことができたはずだ。

1871年に死去したチャールズ・バベッジが死の直前まで開発していた機械式コンピューター、アナリティカルエンジンでも、バベッジはプログラムをパンチカードで読みこませ、しかも一部を歯車メモリーに蓄え、条件分岐やジャンプをさせるという、プログラム内蔵方式にきわめて近い構造を採用している(ただし、完成させることはできなかったが)。

アランは、自分が考案したコンピューター、「万能チューリングマシン」を現実のものとしたいと願うようになる。そして、そのチャンスは意外にも早くやってきた。

 

いよいよブレインをつくるぞ!

1945年6月、ナチスドイツが降伏をし、第2次世界大戦の終わりが見えてきたころ、国立物理学研究所から一人の男がアランを訪ねてきた。ジョン・ウォームスリーという人物で、新設された数学研究部門の部長だった。ウォームスリーは、バベッジとアランを熱烈に信奉するまだ若い数学者で、当然アランのチューリングマシンの論文も読んでいた。以前から、「チューリングマシンをハードウェア化する」計画を温めていた。戦争のめどがつくと、アランのブレッチレーパークでの仕事も終わる。ならばと、さっそくアランを口説きにやってきたのだ。

アランにとって、断る理由はなかった。むしろ大歓迎で、友人たちに「いよいよブレインをつくるぞ!」と触れて回ったという。アランはすぐに国立物理学研究所に移り、このブレインの設計の仕事を始めた。このブレインは、ACE=Automatic Computing Engineと名づけられた。ウォームスリーもアランもバベッジを尊敬していたので、バベッジのアナリティカルエンジンに倣ったネーミングだった。 アランは猛烈な勢いで仕事を進め、約半年で設計を終え、48ページの計画書と52枚の図面を作成した。その見積によると、製作費用は1万1200ポンドということだった。これは現在の貨幣価値に換算すると、約7億円程度になるという。

アランの設計には注目すべき点がある。それはハードウェアをできるだけシンプルにして、複雑さはソフトウェア(プログラム)で補おうという設計思想が見られることだ。たとえば、かけ算をするのに、かけ算専用の回路を用意するのではなく、プログラムで複数回足しあわせるようにする。これは今日のコンピューター設計のRISC思想に通じるものだった。ただし、今日のRISCは回路を単純化することにより演算全体の高速化をねらうものだったが、アランのねらいは複雑なハードウェアを開発するには、必要な技術がまだ不足していること、全体が複雑になり制御がむずかしくなってしまうこと、開発費が膨らんでしまうことを考えてのことだった。

しかし、これはハードウェア開発チームとの軋轢を生んだ。ハードウェア開発チームは、アランの考え方とは逆に、必要な演算はどんどんハードウェア化すべきで、プログラムを単純にすべきだと主張した。これにも一理あった。なぜなら、当時プログラムを格納しておくメモリーは、水銀遅延線ぐらいしかなく、容量も少なく、開発費も高価だったからだ。水銀遅延線というのは、電気信号を水銀プールに超音波の形で流してやることで、その電気信号を保存しようというレトロな技術に基づいたものだった。

アランは、ハードウェアの開発チームの横で、膨大なソフトウェアを書き始めた。およそ、必要と思われるプログラムはあらかた書きあげてしまう。しかし、アランにとって国立物理学研究所はあまり居心地がよくなかったようだ。部下としてアランといっしょに仕事をした多くの技術者たちが、「チューリングは怒りっぽい人だ」と証言しているのだ。

アランに幸運をもたらしてくれたウォームスリーに対しても、アランは距離を置くようになった。最初は、万能チューリングマシンを実現する同志だと思ったが、いっしょに仕事をするうちに、ウォームスリーが「万能チューリングマシンの開発責任者」として、自分の名声を得たいのではないかと疑い始めたのだ。もちろん、ウォームスリーにはそういう気持ちがあったに違いない。しかし、それはアランを口説き、政府関係者に予算支出を認めさせ、必要な人員を手配し、プロジェクト全体を管理するウォームスリーにとっては当然の成功報酬でもある。アランは、きっと純粋すぎたのだ。

このACEプロジェクトには、あのコロッサスの開発を中心になっておこなった優秀なエンジニアであるトミー・フラワーズも参加していた。ACE開発の中心人物だった。しかし、フラワーズは郵政省の技術者であり、第二次世界大戦で壊滅状態になっていた英国の電話網を復興させる仕事を上司から命じられてしまった。フラワーズは、個人的にはACEの仕事を続けたかったが、役人という立場上、郵政省の仕事をしないわけにはいかない。そして、フラワーズがACEプロジェクトを去ると、人員不足、才能不足からACEプロジェクトは暗礁に乗りあげてしまった。

ウォームスリーは、計画を変更してACEのパイロット版をまず完成させることにしようと提案した。しかし、これにまっこうから反対したのがアランだった。アランは、パイロット版などをつくるのではなく、最初から完成品を目指さなければだめだとかたく 頑なだった。しかし、それには人材も人員も不足していた。結局、ウォームスリーはまずパイロット版を開発すると決定を下したが、アランはその仕事をいっさい無視し、一人で完成版ACE用のソフトウェアを書き続けた。パイロット版用のソフトウェアも必要なのだが、頼まれてもアランはまったく無視し続けたのだ。

2つのプロジェクトを同時進行させるようなことになってしまい、ますます人員不足が深刻となった。ウォームスリーは人員を補ったが、新しく入ってくるのは技術者というより、社内政治が大好きな連中ばかりだった。そして、優秀な技術者は国立物理学研究所を去っていき、ACEプロジェクトは完全に崩壊した。ついに、アランも1947年末に国立物理学研究所を辞任した。

アランが去ったあとの1950年5月、パイロット版ACEは完成をした。アランとしては、自分の設計とはいえ納得はしていなかっただろう。しかし、のちにイングリッシュ・エレクトロニクス社から デュース DEUCEという名前で商品化をされ、英国の電子産業の柱のひとつとなり、1970年代まで実際に使用されていたという。

 

誤解されているチューリングテスト

国立物理学研究所を去ったアランは、マンチェスター大学にあるマンチェスター計算機研究所の副所長に就任する。ここで、さまざまなコンピューター関連技術のアイディアを生みだしていった。アランは、不本意なことになってしまったACEとは別に、ここで万能チューリングマシンをもう一度つくろうとしたのだと思われる。

しかし、次第にアランの研究は計算機づくりを超えた深いところに入りこんでいった。人工知能だった。そもそもチューリングマシンがどのような発想で生まれたものだったかを思いだしていただきたい。人間の計算手順を要素別に分解して、それを組みわせる仮想機械がチューリングマシンだった。チューリングマシンを使っても計算できないものは、計算不能であると証明するための概念だった。これは人間の知能を機械で置き換えたものだ。アランにとって、コンピューターと人間の知能は同一のもので、初歩的なコンピューターが稼働する時代になったら、次は「人間の知能と比べられるほどのコンピューターをつくりたい」と考えるのは当然のことだ。

アランはこの時代に、有名なチューリングテストを考案している。一般的には、チューリングテストはある人工知能が人間と同じレベルに到達しているかを判定するテストだと思われている。それは次のような方法だ。

まず、回答者として人工知能と普通の人間が用意される。判定者は、テキストチャットなどの方法で、この人工知能と人間と会話をし、さまざまな質問をする。そして、判定者のうち30%の人が人工知能と人間を区別できなければ、この人工知能は人間の知能レベルに達していると判定されるというものだ。

しかし、賢明な読者のみなさんは、このチューリングテストの判定基準に疑問を感じることだろう。まず、30%という判断基準の根拠はなんなのか? どういう理屈で30%という基準が設定されるのか? さらに、「判定者の30%」というが、判定者の選考基準はどうなっているのだろうか? たとえば、3歳児なども判定者にしていいのだろうか? 一般の人ばかりの判定者グループと、人工知能の研究者ばかりの判定者グループでは、結果も大きく違ってくるのではないか?

もう、お気づきだと思う。アラン・チューリングとあろう者が、こんな雑な判定基準を提案するはずがないのだ。このチューリングテストは、アランが1950年10月にMind誌に発表した『計算機構と知能』という論文、というよりも社会エッセイに近い記事に登場するイミテーションゲームが元になっている。

このイミテーションゲームは、男性、女性、質問者の3人でおこなわれる。質問者は別室にいて、男性と女性の姿、声などから性別がわからない状態にされていて、5分間自由にさまざまな質問をし、どちらが男性で、どちらが女性であるかをあてるというものだ。男性は、できるだけ質問者が正解を得られるように回答し、女性は質問者が正解を見失うように回答していく。質問者が「あなたが男性ですね」と質問すれば、男性は「はい、そうです」と答え、女性も(質問者を惑わすために)「はい、そうです」と答えるだろう。

そして、アランは今から50年以内(つまり西暦2000年までに)には、女性を人工知能に置き換えて、このゲームをしたとしても、質問者はあてられる率が70%を超えることはできなくなっているだろうと予言している。

つまり、チューリングテスト(アラン自身はこの言葉を使っていない)は、人工知能の進化ぶりを判定するためのものではなく、あくまでも50年後にはその程度まで人工知能は進化しているだろうという予測なのだ。

予測なのだから、とくに70%という数値に確固たる根拠はなくても当然なのだ。ただし、人工知能の専門家たちが、このチューリングテストを誤解しているというわけではない。彼らは、人工知能の進化の一里塚としてアランの予測を使っているだけで、この70%以下の正答率(30%以上の質問者をだます)を超えることが、まずは必要なのだとして、世界中でこのイミテーションゲーム=チューリングテストのコンテストを開催している。しかし、チューリングテストに合格したからといって、それで「人工知能が人間を超えた」と考えているわけではない。多くの場合、メディアが「昔の偉大な天才が判定基準を示し、そのテストに合格した人工知能が出現した。機械が人間を超えた」と報道したがるため、世間にこのイミテーションゲームが、あたかも絶対的な判断基準であるかのような誤解を振りまいているだけだ。

アラン自身、この『計算機構と知能』の原稿を友人に、爆笑しながら読み聞かせていたという。実際、記事の中にはイミテーションゲームの質問と回答の実例も掲載されていて、その中には明らかに女性蔑視(女性は科学や計算に弱いということを茶化したもの)と思われる会話もある。チューリングテストは、アラン的なユーモアのひとつであり、半分ジョーク、半分本気といったところがほんとうではないだろうか。

 

イミテーションだったチューリングの社会的人生

このイミテーションゲームは、単なるジョークではなく、アランの根深いところからでてきたものかもしれない。

イミテーションゲームは、男性か女性かをあてるもので、しかも女性は人工知能が女性のふりをするというものだった。これはアランの人生そのままだった。

彼は高校生のときに、親友のクリストファーへの愛に目覚めて以来、ゲイであることを自覚していた。親しい友人たちにはゲイであることを隠さなかった。しかし、当時の英国では同性愛は犯罪であり、罰も決して軽いものではなかった。そのため、世間的には〝男性のふり〟をして生きなければならなかったのだ。

それはアランだけでなく、他のゲイたちも同じだった。そのため、映画館であるとか、鉄道ガードの下とか、ゲイたちの出会いの場が、世間から隠れるようにして自然発生的に生まれていった。アランも、夜や週末になると、そのような場所にでかけて、相手を求める生活をしていた。

しかし、1952年に問題を起こしてしまう。マンチェスターの映画館のそばで、ある男性と知り合い、肉体関係をもつにいたった。ところがこの男性が、泥棒の手引きとなり、アランの自宅に泥棒が侵入した。警察の捜査の過程で、アランとその男性が同性愛関係にあることが発覚する。当時の英国では、同性愛は犯罪だったため、チューリングは有罪判決を受け、化学療法を受けることになった。当時、過剰な性欲を抑えると考えられていた女性ホルモンの注射を受けることになったのだ。

そして、1954年、アランはなんの前兆もなく、唐突に自殺をしてしまう。自宅のベッドで死んでいるのを家政婦が発見した。検死により、青酸カリが検出され、枕元にかじりかけのリンゴが放置されていたことから、青酸カリ水溶液に浸したリンゴをかじっての自殺だと断定された(ただし、問題のリンゴの分析はおこなわれていない)。

アランは、その日の夜のコンピューターの使用予約をとっていたし、数日前には隣人の引っ越しパーティーがあり、そこでアランはとても上機嫌だったということから、自殺に見せかけた他殺ではないかという話もある。

しかし、アランには自殺したくなるような状況があった。この当時、暗号解読に関しては、アランが文句なく第一人者だった。しかも、その手法はコンピューターを駆使して暗号解読をする。世界でコンピューターが10台もない時代、アランは自由にそのコンピューターを使うことができた。米国のCIAや英国のMI6の後ろ盾があったからだ。

ところが、アランがゲイであることがわかると、諜報機関はアランを警戒するようになった。性的な問題を抱えている人物は、敵国のハニートラップに簡単に引っかかってしまうからだ。そのような理由から、アランは国家レベルの機密やコンピューターにアクセスする権利を剥奪されてしまう。

小さいときからコミュニケーションに問題を抱えていたナイーブなアランにとって、暗号とコンピューターのみが自分の世界だった。その世界にアクセスすることを禁じられたアランは、もう自分にはなにも残っていないと感じたのかもしれない。

2009年9月10日、当時の英国首相ゴードン・ブラウンは、アラン・チューリングを同性愛で告発したことを、政府として正式に謝罪した。「時計の針は戻すことはできないが、彼に対する処置はまったく不当であり、深い遺憾の意を表す機会を得たことを我々すべてが満足に思っている」とスピーチした。

2012年は、アラン・チューリング生誕100周年だった。アランの誕生日である6月23日、Googleのトップページには、チューリングマシンを模したロゴが掲げられた。