計算理論とは
日記、その他計算とはなんなのか，計算の複雑さとはなんなのかについて詳しく検討する分野。分かりやすいモチベーションとして，ある計算を行うのにどれくらいの時間がかかるのか，また，どれくらいのメモリを必要とするのかについて知りたいとする。この疑問を突き詰めると，そもそもその計算は実行可能なのかどうか，計算とはなんなのかという問題にたどり着く。つまり，計算の性質について具体的に調べるには計算という概念自体を厳密に定式化する必要があるということ。
計算の定義
計算と計算をするもの（機械）は表裏一体で，計算について定義するには計算をする機械（計算の行い方）を定義する必要がある。それはつまり，計算機のモデルを考えるということ。計算機のモデルにはさまざまなものがあるが，代表的なのはやはりチューリングマシン。チューリングマシンは無限のテープの上に，左右への移動とテープ上の情報を読み書きのできる装置を考えたもの。もちろん計算モデルはチューリングマシンだけではなく，他にも多くある。有限オートマトン，プッシュダウンオートマトン，レジスタマシン，ラムダ計算，セルオートマトンなど。各計算モデルの計算能力はそれぞれ異なる。ここでいう計算能力というのは，簡潔に言えば他の計算モデルを自身の上にシミュレートできるかどうかということ。
これらの計算モデルは，動作によってより細かく分類することができたりする。とくに，チューリングマシンについては決定性チューリングマシン，非決定性チューリングマシン，マルチテープチューリングマシン，ユニバーサルチューリングマシンなど。これらは，判定問題においては計算能力は等価だと言えるが，計算時間や空間の複雑性においてはカテゴリーが別れ得る。例えば非決定性チューリングマシンによって多項式時間Pで解かれる問題群はNP問題，決定性チューリングマシンによって多項式時間Pで解かれる問題群はP問題と呼ばれる。一般にNPとPが同じ集合であるかどうかは明らかになっていない。（P≠NP問題）
計算の性質
これらの計算機を理論として厳密に定めることで，計算の性質について議論することが可能になる。ここで興味のある計算の性質というのは，
- 計算が終了できるかどうか（無限ループしないか）
- 計算にかかる時間はどれくらいか（時間）
- 計算に必要なメモリはどれくらいか（空間）
などが主な対象。
基本的には，答えがYesかNoかで答えることができる判定問題（決定問題）と呼ばれる問題群を対象にして議論をすることが多いようだ。これらの問題に対して，そもそも計算を終了させることができる類の問題なのかどうか？実行できたとして，それは現実のリソース（計算時間，メモリ）で実現させることができるのだろうか？ そういった問いに答えるのが計算量の理論の一つの目的ではある。これらを分析するために，ほとんどの場合チューリングマシンが計算機のモデルとして使われる。その理由としては，単に扱いやすく，証明が比較的容易であること，現実のコンピュータの挙動に近いことなどが挙げられるらしい。
実際にある計算に対しての計算時間や必要なメモリ量を分析するためには，フォーマルなチューリングマシンの定義が必須なので，ここでは触れないことにする。しかし基本的な発想としては，計算時間を処理に必要な試行錯誤の回数，メモリ量を処理に必要となるテープの長さと考えて議論する。
計算理論はコンピュータとは独立の”理論”である
計算理論は，現実に存在するコンピュータの存在を完全に無視しても成り立つ。むしろ，現実にガチャガチャ動作する計算機の背後にある計算そのものの本質を探る理論である。計算理論で扱う計算時間やメモリといった概念は，ある計算に何秒かかるか，とか，何バイト使用するかといったような具体的な話ではなく，計算の構造そのものを考えた時に，ある計算に本質的に備わっている量のことを指している。それゆえに，現行のコンピュータの性能に惑わされずに，理想的なコンピュータの性能やその限界を探ることができる。たとえば，時間を巻き戻すことのできるようなコンピュータが存在しても囲碁の問題を効率解くことはできないらしい*1。
参考
Turing machine - Wikipedia
Model of computation - Wikipedia
Computational Complexity: A Modern Approach Introduction to the Theory
of Computation
計算理論の基礎（上に同じ）