計算理論のソースを表示

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

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

== 計算可能性理論 ==
{{main|計算可能性理論}}

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

== 計算複雑性理論 ==
{{main|計算複雑性理論}}

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

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

これを単純化するため、[[ランダウの記号|O記法]]が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は <math>O(n)</math> となる。

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

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

;[[ラムダ計算]]: 計算を1つの初期ラムダ式（入力を分離したい場合は2つのラムダ式）と有限個のラムダ項で表す。各ラムダ項は前のラムダ項にβ簡約を適用したものである。
;[[組合せ論理]]: ラムダ計算とよく似ているが、例えばラムダ計算では正規の形式ではない不動点演算子 '''Y''' は組合せ論理では正規に組み込まれているといった違いがある。
;[[μ再帰関数]]: 複数の自然数を引数として1つの自然数を返す関数であり、[[原始再帰関数]]に基づいて構築され、それにμ再帰を施したもの。<!-- ちょっと自信なし -->
;[[マルコフアルゴリズム]]: [[文字列]]に一種の[[文法]]規則を適用する[[文字列書き換え系]]。
;[[レジスタマシン]]: コンピュータを抽象化したもの。多くの場合、無限サイズの自然数を格納できるレジスタを持ち、命令数は非常に少ない。チューリングマシンと比較すると無限のメモリが欠けているが、レジスタが無限サイズの自然数を格納できるので、それで代替される。
;P′′: （[[:en:P%E2%80%B2%E2%80%B2]]）チューリングマシンと同様、無限長のテープに記号を記録するが、チューリングマシンにおける有限状態オートマトンに相当するものを、固定長でループの記述が可能な命令の列によって記述する。これを元に、命令セットを理論向けから実装向けに大幅にアレンジして設計された[[プログラミング言語]]が[[Brainfuck]]である。

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

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

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

== 参考文献 ==
* マイケル・シプサ、『計算理論の基礎』、渡辺 治 他訳、[[共立出版]]、[[2000年]]、ISBN 4-320-02948-8
** {{cite book|author = Michael Sipser | date = 2006年 | title = Introduction to the Theory of Computation 2ed | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Part Two: Computability Theory, chapters 3–6, pp.123–222.
* {{cite book|author = Eitan Gurari | date = 1989年 | title = An Introduction to the Theory of Computation | publisher = Computer Science Press | id = 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
*[http://www.cis.upenn.edu/~giorgi/cl.html Computability Logic]: 対話型計算の理論。

== 注 ==
<references/>

{{コンピュータ科学}}
{{数学}}

{{DEFAULTSORT:けいさんりろん}}
[[Category:理論計算機科学]]
[[Category:計算理論|*]]
[[Category:離散数学]]
[[Category:数学に関する記事]]
[[Category:数学基礎論|*]]