変数同志の足し算、引き算だけができる仮想的なコンピュータを考えます。現代のコンピュータと原理は一緒。プログラムを書いて、それでいろんなことができます。かけ算、割り算をして答えを求める、素因数分解する、ある数が素数かどうか判定する、100個の数値の中の最大値を求める、……。こうなるとなんでもできそうに思えてきます。どんなプログラムも、実行するとある程度の時間の後に止まるか、あるいは永遠に止まらないかのどちらかです。しかし、任意に与えられたプログラムを見て「このプログラムはいずれ止まる」、「永遠に止まらない」の判定をするプログラムは作れないことが証明できます。計算可能性という分野の停止問題と呼ばれます。現代のコンピュータも原理は同じだと考えられますから、要するにコンピュータにもできないことはあるのです。こういう本を大学のときに読み、面白い話があるもんだと感心しました。
前、チューリングマシンについて少し書きました。チューリングマシンは数学者アラン・チューリングが考えた仮想的な機械です。
さっきの、元は足し算と引き算しかできないコンピュータと同じで、たいしたことはできそうに思えません。でも実は素因数分解、与えられた数値の山から最大値を求めるなど、様々のことができることが示されます。そして、さらに「与えられたチューリングマシンを見て、『このチューリングマシンはいずれ止まる』『永遠に止まらない』を判定するチューリングマシンは作れない」ということが証明できるのです。やはり停止問題と呼ばれます。同じような話ですね。これ以上は勉強していないのでハッキリ言えませんが、実際、同じ話なのだと思います。
面白いのですが、この先は難しくなるのかも……。計算量の理論などにもつながります。例えばP≠NP予想とか。なんとなくの話ならすでに紹介した『暗号の数理』に分かりやすく説明してあります。
暗号が現実的な時間内に第三者に解読されてしまうかどうかは、計算量に関わる問題なのです。面白そうな話はたくさんあります。
