計算理論
計算理論（けいさんりろん、theory of computation）は、計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。
計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量も有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。
計算可能性理論
計算可能性理論は、ある問題がコンピュータで解くことができるかどうかを扱う。チューリングマシンの停止問題は計算可能性理論における最も重要な成果である。これは、定式化しやすく、かつチューリングマシンで解けない問題の具体例である。計算可能性理論の大部分はこの停止問題の結果に基づいて構築されている。
計算可能性理論は、数理論理学の再帰理論と密接に関連しており、再帰理論は物理的に実現可能な計算模型だけに限定しない研究とされている。多くの数学者や再帰理論研究者は再帰理論を計算可能性理論と呼ぶ。実際のところ、この2つの研究分野は、数学の研究室で行われているか、計算機科学の研究室で行われているかの違いしかない。
計算複雑性理論
計算複雑性理論は、問題がコンピュータで解けるかどうかだけでなく、その問題の困難さを扱う。時間計算量と空間計算量という2つの観点がある。時間計算量とは計算にかかるステップ数、空間計算量は計算に必要とされるメモリ量に相当する。
あるアルゴリズムが必要とする時間と空間を分析するため、時間や空間を問題の入力量の関数として表現する。例えば、長い数列から特定の数を見つけ出すという問題は、数列が長くなればなるほど難しくなる。数列に <math>n</math>個の数があるとき、その数列がソートされていなければ、一個一個の数を確認していくしかない。この場合、この問題の解法の時間計算量は入力量に比例して増大するといえる。
これを単純化するため、O記法が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は <math>O(n)</math> となる。
計算機科学の中でも最も重要な未解決の問題は、NPと呼ばれる計算複雑性クラスの問題が効率的に解けるかどうかである。詳しくは、P≠NP予想を参照されたい。
計算の形式的定義
チューリングマシン以外にも以下のような同等なモデル（チャーチ＝チューリングのテーゼ参照）が使われている。
- ラムダ計算
- 計算を1つの初期ラムダ式（入力を分離したい場合は2つのラムダ式）と有限個のラムダ項で表す。各ラムダ項は前のラムダ項にβ簡約を適用したものである。
- 組合せ論理
- ラムダ計算とよく似ているが、例えばラムダ計算では正規の形式ではない不動点演算子 Y は組合せ論理では正規に組み込まれているといった違いがある。
- μ再帰関数
- 複数の自然数を引数として1つの自然数を返す関数であり、原始再帰関数に基づいて構築され、それにμ再帰を施したもの。
- マルコフアルゴリズム
- 文字列に一種の文法規則を適用する文字列書き換え系。
- レジスタマシン
- コンピュータを抽象化したもの。多くの場合、無限サイズの自然数を格納できるレジスタを持ち、命令数は非常に少ない。チューリングマシンと比較すると無限のメモリが欠けているが、レジスタが無限サイズの自然数を格納できるので、それで代替される。
- P′′
- チューリングマシンと同様、無限長のテープに記号を記録し、命令セットは最小である。ただし、命令の種類はチューリングマシンとはだいぶ異なる。この命令セットに基づいて実装されたプログラミング言語がBrainfuckである。
汎用的な計算モデルだけでなく、特定の応用のためにもっと単純化された計算モデルを使う場合もある。正規表現は文字列パターンを指定するのによく使われる。また、それと等価な有限オートマトンは回路設計などに使われる。文脈自由文法はプログラミング言語の構文を定義するのに使われる。非決定性プッシュダウン・オートマトンは文脈自由文法と等価である。原始再帰関数は再帰関数のサブクラスを定義したものである。
モデルが異なれば得意分野も異なる。計算モデルの能力を測る方法として、そのモデルが生成できる形式言語のクラスを調べるという手法がある。詳しくはチョムスキー階層を参照されたい。
参考文献
- マイケル・シプサ、『計算理論の基礎』、渡辺 治 他訳、共立出版、2000年、ISBN 4-320-02948-8
- テンプレート:Cite book Part Two: Computability Theory, chapters 3–6, pp.123–222.
- テンプレート:Cite book 無料版はこちら: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html
- Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. 入門書
- Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 2ed Reading, MA: Addison-Wesley, 2001.
- Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. 上級者向け
- Hartley Rogers, Jr, Theory of Recursive Functions and Effective Computability, MIT Press, 1987, ISBN 0-262-68052-1
- Computability Logic: 対話型計算の理論。
