数学徒然なるままに

P≠NP予想とアラン・チューリングについて

　ごきげんよう。初回はP≠NP予想について紹介するぞ。

　なに？数学ができないから、そんな話よしてくれって。

　そんなことはない。確かに多項式とか、チューリングマシンとかわけのわからない単語が連発してくるが、そこは飛ばしてもらって構わない。わかるところだけ読んでくれてもいい。問題は、それを読んあとに自分で調べたりして、理解を深めないことだ。このエッセイはその手助けに過ぎない。だから、今わからなくても構わない。もちろん、数学がわからなくてもわかるように説明するが、筆者は小説でも書くのが下手だからそこはご了承していただきたい。

　さて、本題に入る。これを読んでいるみなさまはアラン・チューリングをご存知だろうか？コンピュータに詳しい方ならご存知だろう。そう、我らが使っているコンピュータの生みの親でもある偉い博士なのだ。また、なんと第二次世界大戦の英雄でもある。

　では、英雄だから戦争に行って活躍したのか。そうじゃない。チューリング博士は直接戦場には行っていない。確かに、あの時代はどこもかしこも戦争だった。ここでいう戦場は撃った撃たれた、死んだ生き残ったが繰り返される戦場を指す。だが、チューリング博士は戦った。その相手はドイツのエニグマ暗号機だ。

　エニグマ暗号機とはドイツが誇った、暗号機で設定は無限大とも思われるほどある物で到底人間が解読するのは不可能とされていた。普通の人なら「これは解けない」と匙を投げてしまうだろう。

　だが、チューリング博士は違った。チューリング博士は「人間に解けないのであれば、機械にやらせればいい。」と考えた。チューリング博士はエニグマ暗号解読の前年にチューリングマシンという理論上存在するマシンを作った。これはどういうものかというと、ゲーテルの不完全性定理という難問を解くために作られたマシンだ。ゲーテルの不完全性定理とは、簡単に言うと「数学はすべての問題を解決することはできない。」という定理だ。巷では数学がすべてを解決するような風潮があると思う。（あくまで、著者の勝手な世間の解釈だが。）だが、数学はすべてを解くことはできないのだ。

　たとえば、とあるところに４人の子供がいてケーキを分けるとする。この時、量的に最良の分配はいくつか。この答えは１/4だ。それじゃあ、ピーマンのケーキが嫌いな子供たちにピーマンのケーキ分ける時の最良な分配はいくつだろうか。これは大人でも悩む問題だ。なぜなら、誰にケーキを一番多くやればいいのか、一番最年少を少なくするのか、威張っている人の量を減らすのか、それともこのケーキは分配せずにすべて捨ててしまうのか。この問題の答えは数学的に解けるのか。

　このようなピーマンのケーキ問題が数学的に解ける問題かどうかを判定するために作られたのが、チューリングマシンだ。これをチューリング博士はエニグマ解読に使おうとした。

　エニグマ解読をするためにはすべての設定を試す必要があった。チューリングマシンに書き込んだ設定は、簡単に言うと「設定が見つかったら、止まる」だった。それを見つけるためのやり方は、超高速で設定を一つ一つ調べていき、突き止めることだ。

　だが、これは上手く行かなかった。なぜなら無限とも思える設定をすべてを検索するのは今のコンピュータの処理能力でも不可能だ。当然、当時のコンピュータでも不可能だ。問題解決は難航を極めた。　

　だが、もしすべての設定を検索しなくてもいいとしたらどうだろう。無限の中から、有限の集合を取り出したら、コンピュータは検索をすることはできるのか？答えはイエスだ。処理可能な領域ならばコンピュータは計算をすることができる。

　チューリング博士のチームは、特定の言葉を使って、検索をかけると、その日の暗号名例文をすべて解読した。

　これだけを聞くと、コンピュータは暗号解読を起源とした便利な道具という認識になってしまうと思う。だが、コンピュータは先程も言ったとおり、数学の問題を解くための道具だ。

　では、コンピュータとはなんなのか。それは、「数学をアルゴリズムに変換して、機械が計算できるようにする機械」なのだ。つまり、数学をアルゴリズムという一定の規則に則って計算すれば、どんな問題も解決ができる夢のような機械だ。

　だが、作ったチューリング博士本人はこの考えに懐疑的になっていた。そこで出たのがP≠NP問題だった。

　この問題は「機械で解ける問題には限りがある。」という問題だった。先ほどのピーマンのケーキ問題を思い出してほしい。もし、ピーマンのケーキ問題に正解がある場合、機械がそれを判断することができるのか。それを実装できるアルゴリズムがあれば可能だ。だが、本当に同値、つまり全て同じ結果になるとなった時、本当に正しい答えを導き出すことはできるのか。

　これは人間の考えを揺るがす大きな問題だ。これに対して、一番恐ろしい結果を生み出している描写をしているアニメが「サイコパス」だ。あれは、人間が並列で高速処理をしている話だが、その世界のみんなは機械が全て管理していると思い込んでいた。この思い込みの根本にP≠NP問題の答えが間違いだと認識をした世界だった、という事ならば、機械が管理する社会は可能だということだ。もちろん、それが実現することは筆者はないと思っている。重要なのは「それが可能だ。」ということなのだ。

　こういう考える余地を残してくれたチューリング博士は青酸カリを飲んで自殺をしてしまった。悲しい結末になってしまったが、それでもチューリング博士が遺してくれた功績は計り知れないものがある。だからこそ、今こうして、我々はコンピュータを使えているということを覚えていてほしい。