理論計算機科学

理論計算機科学（りろんけいさんきかがく、英語：theoretical computer science）または理論コンピュータ科学は、計算の理論的基礎を研究する学問で、計算機科学の一分野である。計算を数理モデル化して数学的に研究することを特徴としている^[1]^[2]^[3]。「数学的」という言葉は広義には公理的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、チューリングマシンなどの計算モデルを扱う。

この分野のテーマの例を以下に挙げる（特に意図や理由のある選出ではない）。

計算理論：ある関数に対する計算の可能性や複雑性を追求する学問。
ラムダ計算：計算機のモデルの一つであるラムダ計算を研究する学問。
アルゴリズム論：ある関数に対する具体的な算法の考案、あるいは既存の算法の解析を行う学問。
プログラム意味論: プログラムあるいはプログラミング言語の形式意味論^[4]

範囲

正確な研究範囲を述べるのは容易ではないが、ACM の Special Interest Group on Algorithms and Computation Theory（英語版） (SIGACT) は同グループの目的を理論計算機科学の振興であるとしており、その対象範囲を次のように定義している^[5]。

アルゴリズム、データ構造、計算複雑性理論、並列計算、分散計算、probabilistic computation、量子計算、オートマトン理論、情報理論、暗号理論、プログラム意味論と検証、機械学習、計算生物学、computational economics、計算幾何学、computational number theory and algebra。

ACMの学術誌 Transactions on Computation Theory ではこの一覧にさらに符号理論と計算論的学習理論（英語版）を加え、データベース、情報検索、経済モデル、ネットワークなどの理論計算機科学的側面をも含めている^[6]。このように範囲は広いが、計算機科学の理論畑の人間は応用畑とは違うという意識を持っていることがあり、「コンピューティングを支えている（より基本的な）科学」を研究しているという意識をもっていることがある^[7]。これは必ずしも対立を意味するものではなく、むしろ協力関係にあることを意味する。

$P\rightarrow Q$
数理論理学	オートマトン	数論	グラフ理論
$\Gamma \vdash x:Int$
型理論	圏論	計算幾何学	量子計算

歴史

アルゴリズムは何千年も前から存在していたが（例えば、2つの数の最大公約数を求めるユークリッドの互除法は今も使われている^[8]^[9]）、計算におけるアルゴリズムの定義を定式化したのはアラン・チューリング、アロンゾ・チャーチ、スティーヴン・クリーネで、1938年のことである。一方、二進法と数学の形式体系はそれ以前からあり、ゴットフリート・ライプニッツが17世紀に二進法を数学的に定式化し、19世紀にジョージ・ブールがブール論理/ブール代数を定式化した。^[10]論理的推論と数学的証明は古代から存在したが、1931年クルト・ゲーデルは自身の不完全性定理で、公理体系には証明できない限界が存在することを証明した。^[11]^[12]^[13]

それらの発展が論理学や計算可能性の現代的研究をもたらし、全体として理論計算機科学という分野を生み出した。1948年、クロード・シャノンによる『通信の数学的理論』から生まれた情報理論がこれに加わった。^[14]^[15]^[16]同じ頃ドナルド・ヘッブが脳における学習の数学的モデルを導入した。生物学的データがこの仮説を裏付けつつ、若干の修正が行われていき、ニューラルネットワークと並行分散処理が確立された。

20世紀初頭から始まった量子力学の発展により、量子の波動関数上で演算が可能ではないかという概念が生まれた。これはすなわち、複数の状態を同時並行的に計算できることを意味する。そこから20世紀後半に量子コンピュータの概念が生まれ、1990年代にはピーター・ショアが量子コンピュータを使えば素因数分解を多項式時間で解けることを示し、もし（数千万量子ビットを量子的に扱える量子コンピュータが）実現すれば公開鍵暗号システムも安全ではなくなることを示した。^[17]^[18]^[19]^[20]

理論計算機科学の研究はこれらを基盤としているが、他にも多くの数学問題や学際的問題を扱っている。

組織

ヨーロッパ理論計算機科学会（英語版）
ACM SIGACT（英語版）

脚注

[脚注の使い方]

^ Hartmanis, A. C. D. H. J., Henzinger, T., Leighton, J. H. N. J. T., & Nivat, M. (2006). Texts in Theoretical Computer Science An EATCS Series.
^ Hartmanis, A. C. D. H. J., Henzinger, T., Leighton, J. H. N. J. T., & Nivat, M. (2006). Monographs in Theoretical Computer Science An EATCS Series.
^ Hartmanis, J. (1981). Observations about the development of theoretical computer science. Annals of the History of Computing, 3(1), 42-51.
^ 横内寛文. (1994). プログラム意味論. 共立出版.
^ “SIGACT”. 2013年7月13日閲覧。
^ “ToCT”. 2010年6月9日閲覧。
^ “Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing”. 2009年3月29日閲覧。
^ 森井昌克, & 笠原正雄. (1992). ユークリッド互除法に基づく狭義 2 元 BCH 符号の復号について. 電子情報通信学会論文誌 A, 75(1), 144-147.
^ 堀口敏男. (1995). ユークリッド復号法を用いたリードソロモン符号の BCH 限界以上の復号. 電子情報通信学会論文誌 A, 78(5), 626-638.
^ Goodstein, R. L. (2007). Boolean algebra. Courier Corporation.
^ Berto, F. (2011). There's something about Gödel: the complete guide to the incompleteness theorem. John Wiley & Sons.
^ Smullyan, R. M. (1992). Gödel's incompleteness theorems. Oxford University Press on Demand.
^ 不完全性定理 / 菊池誠著 | 共立出版
^ Shanon, C. (1948). A mathematical theory of communication. Bell System Technical Journal, 27, 379-623.
^ Guizzo, E. M. (2003). The essential message: Claude Shannon and the making of information theory (Doctoral dissertation, Massachusetts Institute of Technology).
^ Gappmair, W. (1999). Claude E. Shannon: The 50th anniversary of information theory. IEEE Communications Magazine, 37(4), 102-105.
^ Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). IEEE.
^ Shor, P. W. (2002, May). Introduction to quantum algorithms. In Proceedings of Symposia in Applied Mathematics (Vol. 58, pp. 143-160).
^ Rieffel, E., & Polak, W. (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys (CSUR), 32(3), 300-335.
^ Pittenger, A. O. (2012). An introduction to quantum computing algorithms (Vol. 19). Springer Science & Business Media.

参考文献

Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0122063821. - 計算理論を中心にプログラム意味論なども扱っている。