TOUCH THE SECURITY Powered by Security Service G

コラム

2018.01.15

チューリングマシン ~コンピューター科学の巨人アラン・チューリングの論理モデル~ 前半

コンピューター科学の巨人、アラン・チューリング。彼の考案した仮想のマシン=チューリングマシンはコンピューターの原理となり、その後、コンピューター実機の開発が始まる。しかし、チューリングは最初からコンピューターの原理を考案しようとしたわけではなかった。チューリングマシンからコンピューターが生まれるまでには長い物語がある。(前半)

1.映画「イミテーション・ゲーム」が描くチューリングとその功績

難しい題材をよくぞここまで娯楽として楽しめる作品に仕上げたものだと思う。映画「イミテーション・ゲーム」は、コンピューターの原理を発明したと言われる数学の巨人アラン・チューリングが、ヒトラーの最強暗号「エニグマ」の解読に挑み、間接的に多くの人の命を救った英雄物語である。

映画は陰の部分にも光があたる。幼い頃からゲイであり、女性に恋心を抱くことができなかったチューリング。当時のイギリスにおいて同性愛は犯罪行為であり、彼はそのことに悩み、最後は悲劇的な事件に巻き込まれる。しかし生涯で一度だけ、エニグマ解読の拠点ブレッチリーパークで同僚だった女性数学者ジョーン・クラークに恋をして、婚約をしている。それは恋心だったのか、それとも同僚数学者に対する敬意だったのか。その辺りも、美しくも切なく描き出されている。

イミテーション・ゲーム

イミテーション・ゲーム/エニグマと天才数学者の秘密
英政府が50年以上封印した、暗号解読の裏に隠された秘密とは?
ベネディクト・カンバーバッチが挑む、<天才数学者>の驚愕と感動の実話。

2.チューリングはコンピューターの原理を発明したのか

映画の中で描かれるエニグマ暗号の解読と共に、チューリングの大きな功績として「チューリングマシン」という、理論上の機械の考案が挙げられる。紙テープと書き込みヘッドからできている機械が、ヘッドが移動しながら、紙テープ上に0や1を書き込んでいく。そのヘッドの動く規則を決めてやることで、どんな計算もできるといった「論理モデル」だ。

チューリングマシンの概念は、現代のコンピューターと極めてよく似た構造で、ここから「チューリングはコンピューターの原理を発明した」と言われる。確かに、コンピューター科学の教科書を開くと、最初にそろばんや石盤の話が出て、次にパスカルの機械式計算機、そしてチャールズ・バベッジの差分機関、階差機関が登場し、それからチューリングマシンが登場して、コンピューターの近代史が始まるかのように解説をされている。

しかし、チューリングはコンピューターを発明しようとして、チューリングマシンを考案したわけではなく、純粋な数学的な難題を解決する手段に用いたのだ。結果、それがコンピューターの原理になっていることに後で気がつき、15年後に自身でもACE(エース)と呼ばれるコンピューターの開発を行う。

Pilot ACE3

By Antoine Taveneaux (Own work) [CC BY-SA 3.0], via Wikimedia Commons
ACEコンピューターはチューリングマシンの論理モデルを具現化したもの。
写真はプロトタイプモデルの「PILOT ACE」。

では、チューリングが解こうとしていた数学的な難題とはなにか。それは「数学の危機」を救うことだった。チューリングは、エニグマ暗号の解読で連合軍側の多くの市民の命を間接的に救ったヒーローだが、数学の危機を解決したことで、多くの数学者の命を救ったヒーローでもあるのだ。

3.数学の危機 ~ゲーデルの唱えた不完全性定理~

数学の危機とは、1930年、ハンガリーの数学者クルト・ゲーデルが証明した不完全性定理だ。これは世界の数学者にとって驚天動地のできごとだった。

それまで、数学は完全な学問だと思われていた。世の中のすべての現象は、数学で記述ができると考えられ、優秀な者が世界を数学で記述してしまえば、この世界は人類の思い通りになると信じられていたのである。

ここに「数学は不完全であり、世界のすべてを記述できるなどということはあり得ない」という不完全性定理が提唱される。数学は思ったよりも無力であると。しかしゲーデルの説は、論理学という数学の一分野からの見地であり、数学の万能性を依然信じ続ける学者も多かった。

「数学者はいち早く現実を受け入れ、それを前提に新しい数学を構築していく必要がある」
そう考えたチューリングは、代数学の世界でも数学の不完全性を証明しようと考えた。

4.チューリングによる不完全性定理の証明 ~チューリングマシン~

不完全性定理の証明にあたり、異色の数学者チューリングは、数式の駆使といった従来の発想を超え、先に述べた論理モデル「チューリングマシン」を用いた証明を試みた。発想はシンプルである。

チューリングマシンはどんな計算でもできるマシンであるが、チューリングマシンに計算できない問題があると証明できれば、この世の中に計算できない問題が存在することになる。

このような仮説の下、代数学的に数学の不完全性を証明しようとした。前提となる「どんな計算でもできるマシン(チューリングマシン)」を定義するにあたり、チューリングがまず行ったこと。それは、私たちが行っている「計算」を要素に分解することだ。

例えば「1+2=3」という計算の場合、私たちは「1という数字を記憶する」「+記号を見て、演算の種類を記憶する」「2という数字を記憶する」「=記号を見て、記憶した数字を記憶した種類の演算をする」「演算結果を記録する」ということを組み合わせて行う。

これをさらに分割できない要素にまで分解していった結果、「紙テープ」「0と1を書き込むことができるヘッド」を備える、仮想機械チューリングマシンの概念を定義した。あとは「0を書き込んで右に1コマ移動」「紙テープの文字を読んで、左に1コマ戻る」などの命令を並べた”プログラム”さえ書ければ、計算の要素機能をすべて備えているチューリングマシンは、どのような計算でもこなせるはずだ。

次はこの「何でも計算できるはずのマシン」に「計算できない問題が存在する」という、矛盾を証明する必要がある。

5.矛盾の証明 ~カントールの対角線論法~

この矛盾をどうやって証明すれば良いのか。そこでチューリングは、19世紀のドイツの数学者カントールが行った、ある数学の証明方法を参考にした。あまりに面白く、そして鮮やかなので、途中で騙されたような気にすらなる。騙されないように、注意深く読んでいただきたい。

カントールが挑んだのは、「自然数と実数はどちらが多いか」という問題だ。自然数というのは1、2、3…という普通の数のことで、実数というのは3.16や7.635などの小数や分数なども含む数のことだ。誰がどう見ても、実数の方が個数は多そうだ。なぜなら、1と2の間だけで考えると、自然数は1と2の2個しかないのに、実数の方は2.05、2,52432といくらでも作ることができる。実感としては、実数の方が多く感じる。しかし、本当にそうなのだろうか。

カントールは「実数の方が多い」ということをきちんと証明しようとして、ユニークなロジックを使った。まず、「自然数と実数の個数は同じ」という前提条件を立て、これの矛盾点を探す。矛盾が見つかれば、「個数は同じではない」ということが証明できる。カントールのとった方法はこうだ。

まず0と1の間の実数を無限に並べた表を作り、それに1から順に背番号をつけていく。この表は、右方向にも下方向にも無限に続く。無限に続くのだから、すべての実数が列挙され、それに背番号がつけられているので、同じ数だけの自然数がある。実数の個数と自然数(背番号)の個数は同じになっているという訳だ。

カントールの表1

0と1の間の実数を並べた表。右側と下側は無限に続くので、すべての実数が並べられていることになる。
実数に対する背番号が左に並んでいるが、これは自然数。従って0と1の間の自然数と実数の個数は同じになる。

この不思議な表のどこに矛盾があるのか。ここである操作を行う。それは斜めの対角線の部分の数字に1を加えてしまうのだ。すると、斜めに0.846243…という新しい実数が出てくる。

カントールの表2

斜めに1を加えて、新しい実数を作る。

この実数は、この表のどこかに書いてあるだろうか。書いてなければおかしい。なぜなら、この表には0と1の間の実数が無限に書いてあるはずなのだから、すべての実数がなければおかしなことになる。

しかし、この0.846243…という実数は、どこにも存在できないのだ。まず、背番号1の実数では絶対ない。なぜなら、小数点1桁目に1を加えたのだから、同じ数になるわけがない。背番号2の実数でも絶対にない。なぜなら、小数点2桁目に1を加えたのだから、同じ数になるわけがない。背番号3の実数でも絶対にない…。このように、0.846243…という実数は、表の中のどの実数とも違うことになる。これは「すべての実数が列挙されている」ということと矛盾をする。

つまり、「自然数(表における背番号)と実数の個数は同じ」という前提条件が間違っていて、「自然数と実数の個数は同じではない」ということが証明できた。チューリングは、この論法をチューリングマシンに適用して、数学の不完全生を証明しようとした。

後半へ続く

記事一覧に戻る