計算理論は、何が計算でき、またそれらの計算をどれだけ効率よく実行できるかを形式的に研究する分野である。数学と論理学の交点に位置し、通常は計算機科学の基礎分野の一つとみなされる。この分野の研究者は、抽象的な計算装置によってどの問題が解けるのか、そして解ける問題については、どの資源（時間、記憶、乱数）が必要になるのか、という二つの大きな問いを立てる。
主要な分野と概念
この主題は通常、相互に関連するいくつかの下位分野に分けられる。計算可能性理論（再帰理論とも呼ばれる）は、どのようなアルゴリズム的手続きによっても問題を解けるのかを調べる。典型的には、チューリング機械のような理想化された機械でモデル化される。計算量理論はこれをさらに進め、最良のアルゴリズムが必要とする資源に基づいて、解ける問題を分類する。第三の領域であるオートマトン理論と言語理論は、有限オートマトンやプッシュダウン・オートマトンのような制限された計算モデルと、それらが認識する文字列集合を調べる。
重要な区別
- 判定可能か未判定か: ある決定問題は、アルゴリズムによって常に正しく答えられる（判定可能）が、停止問題のように、証明可能に未判定なものもある。
- 扱いやすいか扱いにくいか: 判定可能な問題の中でも、計算量理論は、実用的な資源で解けるもの（しばしば「扱いやすい」と呼ばれる）と、実際には時間や空間を大量に要するとみられるものを分ける。
- 最悪時と平均時: 計算量は、個々の入力を解く最悪時コストでも、より細かな平均時解析でも測定できる。
歴史的背景
現代の計算理論は、アルゴリズムという概念を形式化し、数理論理学で提起された決定問題に答えようとした1930年代から1940年代にかけて成立した。影響力の大きい概念は、記号操作のための機械的手続きを定義した論理学者たちによって導入された。Church–Turing の見方は、チューリング機械を中心的な抽象モデルへと導いた。後の世代は、計算量クラスや問題間の還元を形式化し、アルゴリズムの難しさを比較するための言語を与えた。
応用と例
理論的関心にとどまらず、計算理論は多くの実用分野を支えている。計算量に関する結果はアルゴリズム設計の指針となり、改良されたアルゴリズムが得られそうにない場合を示す。計算可能性と判定可能性の研究は、プログラム検証、コンパイラ構築、そしてソフトウェアやハードウェアの正しさを証明するための形式手法に役立つ。暗号理論は、ある種の問題が難しいとみなされることに依存しており、その考え方は計算量理論に根ざしている。典型的な例には、停止問題（未判定）、オートマトン理論における各種の言語認識問題、そして分類（たとえば NP 完全）が実用上の見通しを形づくる最適化問題や充足可能性問題がある。
なぜ重要か
どの問題が解けるのか、そしてどの問題が効率よく解けるのかを理解することは、計算の根本的な限界を定める。この知識は、計算機科学者がどこに工学的努力を集中すべきか、いつ近似やヒューリスティックを探すべきか、そして信頼できるシステムをどう構築するかを判断する助けになる。基礎概念や形式的定義についてさらに読むには、計算モデルの資料や、数学ポータル、計算機科学学科の入門解説にある概説資料を参照するとよい。追加資料や共同編集型の参考文献は、学術的なコンペンディアや、チューリング機械について、計算量についての研究ページにあるチュートリアル集からも利用できる。
この分野の主要な技法には、還元（ある問題を解ければ別の問題も解けることを示す）、計算量クラスの分離と完全性の証明、そして直感的な計算能力を捉える抽象機械モデルの設計が含まれる。理論的洞察を求めるにしても、実用的な指針を求めるにしても、計算理論は、何がどのコストで計算できるのかを問うための厳密な枠組みを与える。