チューリングが挑んだ”不完全性”の証明と､その限界と失望〜暗号の仕組み”その６”

　前回｢その5｣では､古代ギリシャのカエサル暗号から換字式暗号が生まれ､これに鍵語を加え､複雑にしたものが”ヴィジュネル暗号”の発明に繋がり､それを解読したバベッジについて述べました。
　だが､ヴィジュネル暗号もその周期性に注目したカシスキーテストに突破され､更に文字の偏りを推測する”クリブ”攻撃により高度に複雑化したヴィジュネル暗号も姿を消す。
　そこで登場したのがエニグマ(謎)だが､原理はヴィジュネル暗号とほぼ同じだが､鍵語が天文学的な長さになる為に”謎の暗号”とされた。ポーランド人数学者らも機械式”ボンブ”(時限爆弾)を開発し､必死で対抗するも､ナチス軍は電子式暗号機を開発し､ビット演算をするローレンツ暗号を使い､連合国を翻弄する。
　そこで､英国暗号解読班のチューリングは電子式ボンブを､同僚のフラワーズは電子式解読機”コロッサス”を開発し､エニグマを攻略する。因みに､コロッサスを世界初の電子計算機であるとの説もある。
　そこで今日は､前回のバベッジに引き続き､エニグマ解読の第一人者とされるチューリングについて紹介します。

　”コンピューターを生んだ巨人”とも呼ばれるアラン･チューリングですが､彼が考案したチューリングマシンは､コンピュータの原理や概念となり､コンピュータ実機開発の原動力であり続けます。
　しかしチューリングは､最初からコンピュータの原理を考案しようとした訳ではない。つまり､チューリングマシンからコンピュータが生まれるまでには､複雑で長い物語がある。

　チューリングマシンの概念は､現代のコンピュータと極めてよく似た構造で､が故に”チューリングはコンピュータを発明した”と言われる。確かに､最初にそろばんや石盤が出て､次にパスカルの機械式計算機､更にバベッジの差分機関や階差機関が登場し､それからチューリングマシンが登場し､コンピューターの近代史が始まるかの様に解説される事が多い。
　だが､彼が考案したマシンは非常にシンプルなものである。事実､チューリングマシンとは､1936年に彼が発表した論文の中で”計算する”事を定義した仮想的な機械でした。
　構造は単純で､この計算機で計算し､機械がデータを出力できるならば計算でき､出力が不可能ならば計算できないと定義されているが､これこそがコンピューターの原理･本質そのものである。
　一方で､この機械には1本のテープとそれを読み取るヘッドが1つあるだけで､できる事はテープに文字を書く事とヘッドを右左に1文字分のみ移動する事と､文字を読み取る事だけです。がこれは､この機械で計算の手順を書き込む事が出来､その計算が可能である事を示した。
　以下､｢チューリングマシンとは・・｣を参考に主観を交え､大まかに纏めます。

チューリングVSヒルベルトVSゲーデル

　チューリングが論文を発表した数十年も前､当時多くの数学者に影響を与えた数学者ダフィット･ヒルベルト(1862-1943)は”数学が無矛盾である事を数学で証明する”との運動をはじめました。これはヒルベルトプログラムと呼ばれ､この目的は数学の命題が矛盾しない事を論証できるアルゴリズムを開発する事にあった。
　これを｢決定問題｣と呼ぶが､チューリングはこの決定問題を解決する為にチューリングマシンを開発した。彼は数学の難題を解決する為にチューリングマシンを用いた。結果､それがコンピュータの原理に適ってる事に気がつき､15年後に自身でもコンピュータ実機の開発を行っていた。

　そんな中の1930年､ハンガリーの数学者クルト･ゲーデルは｢不完全性定理｣を発表し､”数学が絶対ではない”事を証明する。これは世界の数学者にとって衝撃的な出来事で､それまで数学は完全な学問で､世の中の全ての現象は数学で記述ができると考えられていたからだ。従来は､世界を数学で記述できれば､この世界は数学の思い通りになると信じられていたのだ。
　だがこんな時代に､ゲーデルにより”数学は不完全であり､世界の全てを記述できるなどあり得ない”とされた。彼は”数学は思ったよりも無力である”という事を示そうとしたが､彼の説の真意はヒルベルトプログラムに近い無矛盾性からの見解であった為に､数学の万能性を信じ続ける学者も多くいた。
　但し､｢不完全性定理｣には誤解されてる部分が多いので補足するが､ゲーデルが示した”不完全性とは特定の形式体系における決定不能な命題の存在”であり､一般的な意味での”不完全性とは無関係"である。事実､数学の形式体系上での公理は真であり無矛盾であり､数学の完全性も成立し続けている。
　だが現実には､”数学は不完全な事が証明された”とする哲学的発言が広まり､誤用されている。事実､ゲーデルが不完全性定理の中で示したのは､”数学の無矛盾性を証明するにはヒルベルトプログラムを拡張する必要がある”という事だった。実際､この後に無矛盾性証明の為の様々な方法論が開発されていく。

　これに対し､”数学者は現実を受け入れ､新しい数学を構築する必要がある”と考えたチューリングは､古典的な代数学の世界でも数学の不完全性を証明しようと考えます。彼は旧来の数式の駆使ではなく､計算機をを用いた論理モデルでの証明を試みたのだ。
　つまり､チューリングマシンはどんな計算でもできる機械であり､それで計算できない問題があれば､数学の不完全性が証明される事になると・・(機械で計算不能だから代数学の不完全性が証明されるとは､随分と短絡的にも思えるが・・・)
　そこで､”どんな計算でもできるマシン”を定義する為に､チューリングが行ったのは計算を”要素”に分解する事だった。
　例えば､”1+2=3”という計算を要素に分解すると､まず”1という数字を記憶する”→”+記号を見て､演算の種類を記憶する”→”2という数字を記憶する”→”=記号を見て､記憶した数字を記憶した種類の演算をする”→”演算結果を記録する”という事を組み合わせて実行する。
　更に､この工程を分割できない要素にまで分解していけば､”紙テープ”と”0と1を書き込むヘッド”を備えるという仮想計算機の概念を定義出来る。後は､”0を書き込んで右に1コマ移動”や”紙テープの文字を読んで左に1コマ戻る”などの命令を並べたプログラムさえ書けば､計算の要素を全て備えるチューリングマシンはどんな計算でもこなせる筈だ。

　しかし次に､何でも計算できる筈のマシンに”計算できない問題が存在する”という矛盾を証明する必要がある。

不完全性の証明へ対角線論法

　そこで､チューリングはこの矛盾を証明する為に､カントール(1845-1918､独)が行った”対角線論法”を参考にした。
　因みに､カントールは”自然数と実数はどちらが多いか？”という問題をこの論法で証明しますが､素人が見ても実数の方が個数は多いと思うだろう。例えば､1と2の間だけで考えても､自然数は1と2の2個だけだが､実数は無限に作れる為､直感で見ても実数の方が多いと判断できる。
　だが､当り前の事を論理的に厳密な形で証明するのが数学という学問である。　
　そこでカントールが使ったのが”背理法”である。まず彼は”自然数と実数の個数は同じ”と仮定し､その矛盾を探した。矛盾が見つかれば”個数は同じではない”事が示せ､実数の方が多い事が証明できる。
　カントールはまず0と1の間の実数を無限に並べた表を作り､それに1から順に(タテに)背番号をつけていく(図1)。この表は縦横に無限に伸びるので､全ての実数が列挙され､全てに背番号がつけられてるので､実数と同じ数だけの自然数が存在する事になる。つまり､実数の個数と自然数(背番号)の個数は同じになる筈だ。

　ここで､(左端の0を除いた)斜めの対角線上の数に1を加えると､斜め方向に0.846243…という新しい実数が出現する(図2)。だが､この実数はこの表のどこかに書いてあるべきだ。なぜなら､この表には0と1の間の実数が無限に書いてある筈だからだ。
　しかし､この0.846243…という実数はどこにも存在しない。というのは､小数点1桁目に1を加えたので､まず背番号1の実数にはなり得ない。同じ理由で背番号2の実数でもないし､背番号3以降の実数でも同様である。
　この様に､0.846243…という実数は､表の中のどの実数とも違う事になる。が､これは”全ての実数が列挙される”事に矛盾をする。
　従って､”自然数と実数の個数は同じ”との仮定は矛盾し､”自然数と実数の個数は同じではない”事が証明できる。
　チューリングは､この論法を自身の計算機に適用し､数学の不完全性を証明しようとした。

　ところでチューリングは(彼が言う所の)”数学の不完全さ”をどの様に証明したのだろうか。
　チューリングマシンは､紙テープに書かれたデータを読み込み､計算をする理論上の機械で､原理的にはだが､適切なプログラムを書きさえすれば､どの様な計算もできる筈だ。だが､万能である筈の機械でも計算できない実例を見つければ､”代数学は完全ではない＝数学は不完全である”事が証明できる事になるとした。
　そこで彼が編み出したものが”停止判定マシン”という理論である。
　彼は､このプログラムを読み込み､機械が無限ループに入り､永遠に計算し続けるのか､計算を終了し停止出来るかを判定する､別の”停止判定マシン”を想定した。
　しかし､この停止判定マシンが様々な矛盾を引き起こし､前提である”停止判定マシンが作れる”が否定される事になる。勿論､否定されれば､万能である筈のマシンにもできない事がある事が証明され､”数学にもできない計算が存在する”事が証明される。

　ここでチューリングは､様々な停止判定マシンのプログラムを停止判定マシンに評価させる一覧表を作り､対角線論法を使い､矛盾を指摘する。
　

停止判定マシンと最後の別れ

　表の一番左上には､TM1という停止判定マシンが､横に並んだ(TM1),(TM2),…と､それぞれの停止判定マシンが停止するかどうかを判定した結果で､停止の場合は”1”が､無限ループに入り停止しない場合は”0”が出力される。2行目はTM2という別の停止判定マシンが(TM1),(TM2),…と､各々の停止判定マシンが停止するかを判定した結果で､以下同様に記す(図3)。つまり､互いのマシンが互いを判定すると考えれば理解しやすい。
　ここで､対角線部の1101000…を反転させ､0010111…という新しい結果を作り出す(図4)。だが､この数の列は表の中にあるのだろうか？この表には､ありとあらゆる停止判定マシンの結果が列挙されてる筈だから､どこかに存在すべきである。が､対角線論法と同様に存在しない。
　事実､1行目の結果は1桁目が1が0に反転されてるから異なるし､2行目の結果も2桁目の1が0になってるからこれも違う。同様に､3桁目以下の結果も異なる。が故に､0010111…は存在しない(証明終)。

　以上より､”存在できない結果がある”との矛盾が導けたが､これは前提条件である”停止判定マシンが作れる”事の矛盾であり､結果として”作れない停止判定マシンが存在する”となる。つまり､どんな計算もできる筈のマシンにも(停止判定マシンが作れないので)”できない計算が存在する”事になる。
　チューリングは､計算の不完全さを(否定的にだが)証明し､｢計算の可能性とその決定問題への応用｣という論文に纏めた。つまり､”<計算には不可能なものがある>という事が<計算の可能性>であるならば､<可能か不可能かをどうやって決めたらいいのか>を問う事がその｢決定問題｣である”とした。
　彼は､この論文を発表し､数学者として認められ､米国への留学が決まり､アインシュタインやノイマンらと出会う。また､英国情報部もこの論文に注目し､エニグマ暗号の解読の研究に彼を抜擢する。
　一方で､チューリングの偉大さは､そのアプローチがハッカーに近い手法で(難しいとは言え)素人でも何とか理解できる範囲に収まってる事が大きいとされる。

　第2次世界大戦後､暗号解読を終えたチューリングは､エニグマ暗号の解読法を解説した｢プロフ･ブック｣と呼ばれる論文を執筆した。出来るだけ数式を使わずに実例を多く使い､理解しやすい内容に仕上げようとした。
　試行錯誤をしながらの執筆だったが､それを支えたのが､チューリングの生涯唯一の”女性”でもあり婚約者でもあるジョーン･クラークであった。が､この美しく切ない恋は実る事はなかった。更に彼は当時は犯罪だとされた”同性愛”を公表して逮捕される。後に名誉も剥奪され､逮捕後は科学的去勢を強要され､42の若さで自死を選ぶ。
　以上､前回｢その4｣と前々回｢その5｣同様に､パーソル･クロス･テクノロジーから長々とでした。

最後に〜同性愛か？リーマン予想か？

　映画｢イミテーション･ゲーム｣では”解読不可能と言われたエニグマ暗号に挑んだ､一人の天才数学者アラン･チューリング。英国政府が50年以上隠し続けた天才の真実の物語。時代に翻弄された男の秘密と数奇な人生とは・・・”との触れ込みだが､チューリングが本当に翻弄され､失意のどん底に突き落とされたは､万能である筈の(数学の不完全性を証明した筈の)チューリングマシンですら簡単に跳ね返した”リーマン予想”ではなかったか・・

　この作品では､連合軍を勝利に導く為に､エニグマを解読する為に心血を注ぐチューリングの真摯な姿が描かれている。エニグマ解読の完成がなければ第2次世界大戦の終了は､数年後に伸びたかもしれないとされるが､実際にはエニグマ解読がなくても､ナチスドイツは降伏寸前にあった。
　一方で､英国情報部は暗号解読班の中にロシア人スパイがいる噂を掴み､大戦終結前に暗号解読班を解散する。これにより､目的と行き場を失ったチューリングは自暴自棄となり､同性愛を自白し､彼の人生は大きく傾いていく。
　ただ､その後のコンピュータの大いなる発展と進化を考えると､もし彼が自殺していなければ､もっと評価されてただろう。少なくとも､アインシュタインやノイマンよりも・・・

　英国政府は後に､チューリングに対する扱いは不当だった事を認め､社会的復権がなされた。故に､この作品はこうした背景をベースしてる様に思える。
　一方で､自殺の真の原因は自身が開発した万能計算機を用いても､数学史上難攻不落とされる”リーマン予想”を証明出来なかったからではないかとも囁かれてはいる。
　事実､チューリングはリーマン予想が間違いである事をチューリングマシンで簡単に証明出来ると踏んでたらしい。が､世紀の難題は彼の人生と意志をいとも簡単に跳ねつけてしまう。何度も何度もプログラミングを変更しても・・・
　その2ヶ月後には精神を病み､青酸カリを塗った林檎を囓って自殺する。
　これは､多くの著名な数学者が難題に果敢に挑戦し､心を病み､死を選択したケースと同じである。事実､ゲーデルもカントールも自死には至らなかったが､”連続体仮説”という難題を前に精神と心を大きく病んでしまった。
　天才チューリングがそうなったとしても何ら不思議ではない。

　天才数学者の苦悩と運命で言えば､チューリングの死の理由として､リーマン予想が存在したとしても矛盾はない様に思える。つまり､エニグマの解読なんて最初からどうでもよかった。多分彼にとっては命題にすらなり得なかっただろう。
　つまり､”リーマン予想”という数学史上最大の難題こそが､チューリングにとって生涯を賭けた最大の難敵であったのだ。少なくとも”同性愛”の自白は､とるに足らない”間違い”に過ぎなかった。

　確かに､計算機を使って､”数学には計算できない問題がある”事を証明したチューリングは偉大ではあるが､かと言って､数学が不完全である事は勿論､数学の無矛盾性を証明した訳でもない。更に言えば､ゲーデルの証明を云々というのも無理がある。
　そうした自身の限界を克服しようと､チューリングはリーマン予想と対峙した。その為の仮想計算機であった筈だが､大きな壁に閉ざされてしまう。
　結局は､暗号解読の天才も数学の天才にはなり得なかったという事だろうか・・・

　噂では､アップルのロゴは､チューリングが毒リンゴを囓ったのをモチーフにしてるとの事だが､アップル側は正式には認めてはいない。
　しかし､チューリングが囓ったであろうリンゴがリーマン予想だったとしたら､これ程の皮肉もない。