LVI-th stone: history of theoretical computer science

私は現在、理論計算機科学(Theoretical Computer Science)を大学院で専攻中である。今年も終わろうとしているのが年始に計画した理論計算幾科学の歴史についての調査がほとんど進んでいない事に気づいた。いろいろ年始に計画したのだがそれらもあまりうまく進んでいないのが現実だ。自分の中でいろいろ変化があったので、計画変更と言うわけでもあるのだが。

年始に計画した内今でも達成したく、かつ達成されていない物を調べた結果、以下の物が残った。
・窓に関しての歴史を調査する
・理論計算機科学の大まかな歴史を勉強する
・哲学に関しての書籍を最低５冊は読む

このうち、窓の調査については、来年以降に回すことを決め、哲学の本に関してもあと１冊で完了する予定である。しかし、２つ目の理論計算機科学の歴史に関しては多少の知識はあるのだが、その知識は統括的にかつ系統的にまとまった物ではない。ので、それを吸収したいと思っている。

理論計算幾何学といっても何かはあまりつかめない方も多いだろう。と書いておきながら、なさけないことに理論計算機科学の定義も私は明確には言えないのだ。理論計算機科学では”計算”を理論的に定義し、現実の多種多様な問題を”計算”によって解決するときいかに短い計算時間で解決できるかを追求する学問であるように思う。そしてこの理論計算機科学は離散数学と密接に関連している。というよりも離散数学に基づいている学問だ。またこの解決するまでに”計算”にかかる時間を用いて、それぞれの問題の難しさ（複雑さ）も定義されている。この”複雑さ”を通して、現実問題における解決の難しさを論ずることができるというわけだ。たとえば暗号技術などがいい例である。暗号技術は様々な学問を取り巻く研究対象であるが、計算機科学的な論点でいうと与えられた暗号文から基の文（平文という）を見つけるのにどれだけの計算量が必要であるか？といった問がたつ。現在使われている暗号が安全であるという根拠は”与えられた数Nが素数であるか判定するのは非常に難しい”という理論計算機科学の今のところの見解に依っているのだ。

理論計算機科学の歴史はそれほど古くない。1900年頃からの物だと私は認識している。このころから”計算”とは何かが定義され、その定義を使って問題を解くときどのくらいの計算が必要か？という研究が始まったということだ。その後”計算”する対象によって様々な理論計算機科学の分野ができたが、それは今のところだけでも非常に多岐にわたっており簡単には述べることはできないのが実際だ。それらを述べた書籍が無いかと現在調査中であるが、めぼしい物が見つかっていない。もしかすると自分でこつこつまとめなければならなくなるかもしれない。が、できれば書籍があることを望む。