「計算理論」の版間の差分
en:Theory of computation 04:23, 5 February 2007 版の部分翻訳をマージ |
編集の要約なし |
||
(21人の利用者による、間の30版が非表示) | |||
1行目: | 1行目: | ||
'''計算理論'''( |
'''計算理論'''(けいさんりろん、Theory Of Computation)または'''計算論'''は、[[理論計算機科学]]と[[数学]]の一部で、[[計算模型]]や[[アルゴリズム]]を理論的にあつかう学問である。[[計算複雑性理論]]、[[計算可能性理論]]を含む。ここでいう'''計算'''(Computation)とは、数学的に表現できる、あらゆる種類の[[情報処理]]のこと。 |
||
計算を厳密に研究するため、計算機科学では[[計算模型]]と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものは[[チューリングマシン]]である。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは |
計算を厳密に研究するため、計算機科学では[[計算模型]]と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものは[[チューリングマシン]]である。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る<ref>ただし、厳密にはここの議論はそんなに単純ではない。たとえば無理数である「2の平方根の全ての桁を求める」ことは不可能だが、「それを計算し続ける停止しないチューリングマシン」を構成すること自体は不可能ではない。</ref>。 |
||
== 計算可能性理論 == |
== 計算可能性理論 == |
||
{{main|計算可能性理論}} |
{{main|計算可能性理論}} |
||
[[計算可能性理論]]は、ある問題がコンピュータで解くことができるかどうかを扱う。[[チューリングマシンの停止問題]]は計算可能性理論における最も重要な成果である。 |
[[計算可能性理論]]は、ある問題がコンピュータで解くことができるかどうかを扱う。[[チューリングマシンの停止問題]]は計算可能性理論における、ある意味で最も重要な成果である。定式化しやすく、かつチューリングマシンで解けない問題の具体例であり、[[数学基礎論]]との関係もある。同時に、静的に[[無限ループ#無限ループの検出|無限ループの検出]]を確実に行う方法は無いことを示している、といったように実応用的な意義もある。 |
||
計算可能性理論は、[[数理論理学]]の[[再帰理論]]と密接に関連しており、再帰理論は物理的に実現可能な計算模型だけに限定しない研究とされている。多くの数学者や再帰理論研究者は再帰理論を計算可能性理論と呼ぶ。実際のところ、この2つの研究分野は、数学の研究室で行われているか、計算機科学の研究室で行われているかの違いしかない。 |
|||
== 計算複雑性理論 == |
== 計算複雑性理論 == |
||
19行目: | 17行目: | ||
これを単純化するため、[[ランダウの記号|O記法]]が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は <math>O(n)</math> となる。 |
これを単純化するため、[[ランダウの記号|O記法]]が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は <math>O(n)</math> となる。 |
||
計算機科学の中でも最も重要な未解決の問題は、'''[[NP]]'''と呼ばれる計算複雑性クラスの問題が効率的に解けるかどうかである。詳しくは、[[P≠NP予想]]を参照 |
計算機科学の中でも最も重要な未解決の問題は、'''[[NP]]'''と呼ばれる計算複雑性クラスの問題が効率的に解けるかどうかである。詳しくは、[[P≠NP予想]]を参照して欲しい。 |
||
== 計算 |
== 計算モデル == |
||
{{main|計算モデル}} |
|||
ここでは例として、計算可能性がチューリングマシンと同等な[[計算モデル]](「[[チャーチ=チューリングのテーゼ]]」の記事を参照)のいくつかを示す。 |
|||
;[[ラムダ計算]]: 計算を1つの初期ラムダ式(入力を分離したい場合は2つのラムダ式)と有限個のラムダ項で表す。各ラムダ項は前のラムダ項にβ簡約を適用したものである。 |
;[[ラムダ計算]]: 計算を1つの初期ラムダ式(入力を分離したい場合は2つのラムダ式)と有限個のラムダ項で表す。各ラムダ項は前のラムダ項にβ簡約を適用したものである。 |
||
;[[組合せ論理]]: ラムダ計算とよく似ているが、例えばラムダ計算では正規の形式ではない不動点演算子 '''Y''' は組合せ論理では正規に組み込まれているといった違いがある。 |
;[[組合せ論理]]: ラムダ計算とよく似ているが、例えばラムダ計算では正規の形式ではない不動点演算子 '''Y''' は組合せ論理では正規に組み込まれているといった違いがある。 |
||
;[[μ再帰関数]]: 複数の自然数を引数として1つの自然数を返す関数であり、[[原始再帰関数]]に基づいて構築され、それにμ再帰を施したもの。<!-- ちょっと自信なし --> |
;[[μ再帰関数]]: 複数の自然数を引数として1つの自然数を返す関数であり、[[原始再帰関数]]に基づいて構築され、それにμ再帰を施したもの。<!-- ちょっと自信なし --> |
||
;[[マルコフ |
;[[マルコフアルゴリズム]]: [[文字列]]に一種の[[文法]]規則を適用する[[文字列書き換え系]]。 |
||
;[[レジスタマシン]]: コンピュータを抽象化したもの。多くの場合、無限サイズの自然数を格納できるレジスタを持ち、命令数は非常に少ない。チューリングマシンと比較すると無限のメモリが欠けているが、レジスタが無限サイズの自然数を格納できるので、それで代替される。 |
;[[レジスタマシン]]: コンピュータを抽象化したもの。多くの場合、無限サイズの自然数を格納できるレジスタを持ち、命令数は非常に少ない。チューリングマシンと比較すると無限のメモリが欠けているが、レジスタが無限サイズの自然数を格納できるので、それで代替される。 |
||
;[[ |
;P′′: ([[:en:P%E2%80%B2%E2%80%B2]])チューリングマシンと同様、無限長のテープに記号を記録するが、チューリングマシンにおける有限状態オートマトンに相当するものを、固定長でループの記述が可能な命令の列によって記述する。これを元に、命令セットを理論向けから実装向けに大幅にアレンジして設計された[[プログラミング言語]]が[[Brainfuck]]である。 |
||
計算理論は、チューリングマシンより弱い(制限された)計算モデルを対象とすることもある。これらに関する理論を、「オートマトン(の)理論」と呼ぶことがある(この文脈では「[[オートマトン]]」とは、チューリングマシンより弱い(制限された)機械の総称である)。 |
|||
[[正規表現]]は文字列パターンを指定するのによく使われる。また、それと等価な[[有限オートマトン]]は回路設計などに使われる。[[文脈自由文法]]はプログラミング言語の構文を定義するのに使われる。非決定性[[プッシュダウン・オートマトン]]は文脈自由文法と等価である。[[原始再帰関数]]は再帰関数のサブクラスを定義したものである。モデルが異なれば得意分野も異なる。 |
|||
また、[[形式言語]]とその文法と、計算モデルとの間には対応する関係があり、計算可能性=表現力について包含関係があることが知られている。[[チョムスキー階層]]及び[[形式言語の階層]]の記事を参照のこと。 |
|||
モデルが異なれば得意分野も異なる。計算モデルの能力を測る方法として、そのモデルが生成できる[[形式言語]]のクラスを調べるという手法がある。詳しくは[[チョムスキー階層]]を参照されたい。 |
|||
== 参考文献 == |
== 参考文献 == |
||
* マイケル・シプサ、『計算理論の基礎』、渡辺 治 他訳、[[共立出版]]、2000年、ISBN 4-320-02948-8 |
* マイケル・シプサ、『計算理論の基礎』、渡辺 治 他訳、[[共立出版]]、[[2000年]]、ISBN 4-320-02948-8 |
||
** {{cite book|author = Michael Sipser | |
** {{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 | |
* {{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. 入門書 |
*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. |
*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. 上級者向け |
*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 |
*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]: 対話型計算の理論。 |
*[http://www.cis.upenn.edu/~giorgi/cl.html Computability Logic]: 対話型計算の理論。 |
||
== 注 == |
|||
{{math-stub}} |
|||
<references/> |
|||
{{コンピュータ科学}} |
|||
⚫ | |||
{{数学}} |
|||
⚫ | |||
⚫ | |||
⚫ | |||
{{DEFAULTSORT:けいさんりろん}} |
|||
[[en:Theory_of_computation]] |
|||
⚫ | |||
[[fr:Calculabilité]] |
|||
⚫ | |||
[[pl:Teoria_obliczeń]] |
|||
⚫ | |||
[[pt:Teoria_da_Computação]] |
|||
⚫ | |||
[[su:Computation]] |
|||
[[Category:数学基礎論|*]] |
|||
[[th:การคณนา]] |
2023年9月10日 (日) 07:42時点における最新版
計算理論(けいさんりろん、Theory Of Computation)または計算論は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算(Computation)とは、数学的に表現できる、あらゆる種類の情報処理のこと。
計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る[1]。
計算可能性理論[編集]
計算可能性理論は、ある問題がコンピュータで解くことができるかどうかを扱う。チューリングマシンの停止問題は計算可能性理論における、ある意味で最も重要な成果である。定式化しやすく、かつチューリングマシンで解けない問題の具体例であり、数学基礎論との関係もある。同時に、静的に無限ループの検出を確実に行う方法は無いことを示している、といったように実応用的な意義もある。
計算複雑性理論[編集]
計算複雑性理論は、問題がコンピュータで解けるかどうかだけでなく、その問題の困難さを扱う。時間計算量と空間計算量という2つの観点がある。時間計算量とは計算にかかるステップ数、空間計算量は計算に必要とされるメモリ量に相当する。
あるアルゴリズムが必要とする時間と空間を分析するため、時間や空間を問題の入力量の関数として表現する。例えば、長い数列から特定の数を見つけ出すという問題は、数列が長くなればなるほど難しくなる。数列に 個の数があるとき、その数列がソートされていなければ、一個一個の数を確認していくしかない。この場合、この問題の解法の時間計算量は入力量に比例して増大するといえる。
これを単純化するため、O記法が使われる。こうすることで特定のマシンの実装を前提とすることなく、問題の本質的な計算量を扱うことができる。従って、上の例の時間計算量は となる。
計算機科学の中でも最も重要な未解決の問題は、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: 対話型計算の理論。
注[編集]
- ^ ただし、厳密にはここの議論はそんなに単純ではない。たとえば無理数である「2の平方根の全ての桁を求める」ことは不可能だが、「それを計算し続ける停止しないチューリングマシン」を構成すること自体は不可能ではない。