計算理論

計算理論（けいさんりろん、Theory Of Computation）または計算論は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算（Computation）とは、数学的に表現できる、あらゆる種類の情報処理のこと。

計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る^[1]。

計算可能性理論は、ある問題がコンピュータで解くことができるかどうかを扱う。チューリングマシンの停止問題は計算可能性理論における、ある意味で最も重要な成果である。定式化しやすく、かつチューリングマシンで解けない問題の具体例であり、数学基礎論との関係もある。同時に、静的に無限ループの検出を確実に行う方法は無いことを示している、といったように実応用的な意義もある。

計算複雑性理論は、問題がコンピュータで解けるかどうかだけでなく、その問題の困難さを扱う。時間計算量と空間計算量という2つの観点がある。時間計算量とは計算にかかるステップ数、空間計算量は計算に必要とされるメモリ量に相当する。

あるアルゴリズムが必要とする時間と空間を分析するため、時間や空間を問題の入力量の関数として表現する。例えば、長い数列から特定の数を見つけ出すという問題は、数列が長くなればなるほど難しくなる。数列に ${\displaystyle n}$個の数があるとき、その数列がソートされていなければ、一個一個の数を確認していくしかない。この場合、この問題の解法の時間計算量は入力量に比例して増大するといえる。

これを単純化するため、O記法が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は ${\displaystyle O(n)}$ となる。

計算機科学の中でも最も重要な未解決の問題は、NPと呼ばれる計算複雑性クラスの問題が効率的に解けるかどうかである。詳しくは、P≠NP予想を参照して欲しい。

ここでは例として、計算可能性がチューリングマシンと同等な計算モデル（「チャーチ＝チューリングのテーゼ」の記事を参照）のいくつかを示す。

ラムダ計算

計算を1つの初期ラムダ式（入力を分離したい場合は2つのラムダ式）と有限個のラムダ項で表す。各ラムダ項は前のラムダ項にβ簡約を適用したものである。

組合せ論理

ラムダ計算とよく似ているが、例えばラムダ計算では正規の形式ではない不動点演算子 Y は組合せ論理では正規に組み込まれているといった違いがある。

μ再帰関数

複数の自然数を引数として1つの自然数を返す関数であり、原始再帰関数に基づいて構築され、それにμ再帰を施したもの。

マルコフアルゴリズム

文字列に一種の文法規則を適用する文字列書き換え系。

レジスタマシン

コンピュータを抽象化したもの。多くの場合、無限サイズの自然数を格納できるレジスタを持ち、命令数は非常に少ない。チューリングマシンと比較すると無限のメモリが欠けているが、レジスタが無限サイズの自然数を格納できるので、それで代替される。

P′′

（en:P′′）チューリングマシンと同様、無限長のテープに記号を記録するが、チューリングマシンにおける有限状態オートマトンに相当するものを、固定長でループの記述が可能な命令の列によって記述する。これを元に、命令セットを理論向けから実装向けに大幅にアレンジして設計されたプログラミング言語がBrainfuckである。

計算理論は、チューリングマシンより弱い（制限された）計算モデルを対象とすることもある。これらに関する理論を、「オートマトン(の)理論」と呼ぶことがある（この文脈では「オートマトン」とは、チューリングマシンより弱い（制限された）機械の総称である）。

正規表現は文字列パターンを指定するのによく使われる。また、それと等価な有限オートマトンは回路設計などに使われる。文脈自由文法はプログラミング言語の構文を定義するのに使われる。非決定性プッシュダウン・オートマトンは文脈自由文法と等価である。原始再帰関数は再帰関数のサブクラスを定義したものである。モデルが異なれば得意分野も異なる。

また、形式言語とその文法と、計算モデルとの間には対応する関係があり、計算可能性＝表現力について包含関係があることが知られている。チョムスキー階層及び形式言語の階層の記事を参照のこと。

• マイケル・シプサ、『計算理論の基礎』、渡辺 治 他訳、共立出版、2000年、ISBN 4-320-02948-8
  • Michael Sipser (2006年). Introduction to the Theory of Computation 2ed. PWS Publishing. ISBN 0-534-94728-X  Part Two: Computability Theory, chapters 3–6, pp.123–222.
• Eitan Gurari (1989年). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4  無料版はこちら: 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: 対話型計算の理論。

1. ^ ただし、厳密にはここの議論はそんなに単純ではない。たとえば無理数である「2の平方根の全ての桁を求める」ことは不可能だが、「それを計算し続ける停止しないチューリングマシン」を構成すること自体は不可能ではない。

表 話 編 歴 数学
主要分野	数理論理学 集合論 圏論 代数学 初等 線型 多重線型 抽象 算術/数論 解析学/微分積分学 関数解析学 行列解析 幾何学 代数 微分 有限 離散 位相 代数的位相 表現論 リー理論（英語版） 微分方程式 線型微分方程式 複素微分方程式 常微分方程式 偏微分方程式 積分微分方程式 力学系 組合せ数学 数理物理学 ゲーム理論 グラフ理論 最適化問題 数理最適化 計算理論 確率論 数理統計学（英語版） 制御理論 三角法
トピックス	数学史 和算 算道 数理哲学 美 未解決問題 算数・数学教育 算数 教科
賞	ボッチャー記念賞 コール賞 フィールズ賞 ヴェブレン賞 サレム賞 スティール賞 ウルフ賞 クラフォード賞 クレイ研究賞 ガウス賞 アーベル賞 ラマヌジャン賞 SASTRAラマヌジャン賞 チャーン賞 数学ブレイクスルー賞
応用	情報理論 折紙の数学 囲碁と数学 数値解析 精度保証付き数値計算 計算機援用証明 数値線形代数 常微分方程式の数値解法 偏微分方程式の数値解法
学会・団体	国際数学者会議 国際数学連合 国際産業数理・応用数理会議 国際産業数理・応用数理評議会（英語版） アメリカ数学会 SIAM ヨーロッパ数学会 ロンドン数学会 日本応用数理学会 日本数学会 数学教育協議会
競技	国際数学オリンピック 日本数学オリンピック 日本ジュニア数学オリンピック 広中杯 近畿大学数学コンテスト 人の最大の力を競う算数・数学の大会
研究所	京都大学数理解析研究所 明治大学先端数理科学インスティテュート 統計数理研究所 アンリ・ポアンカレ研究所 オーバーヴォルファッハ数学研究所 クレイ研究所 CIMAT数学研究センター ステクロフ数学研究所
一覧 数学定数 数 関数 図形 数学記号 数学者 エポニム カテゴリ ポータル