| 翻訳と辞書 |
計算理論[けいさんりろん]
計算理論（けいさんりろん、theory of computation）は、計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。
計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量も有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。
== 計算可能性理論 ==
計算可能性理論は、ある問題がコンピュータで解くことができるかどうかを扱う。チューリングマシンの停止問題は計算可能性理論における最も重要な成果である。これは、定式化しやすく、かつチューリングマシンで解けない問題の具体例である。計算可能性理論の大部分はこの停止問題の結果に基づいて構築されている。
計算可能性理論は、数理論理学の再帰理論と密接に関連しており、再帰理論は物理的に実現可能な計算模型だけに限定しない研究とされている。多くの数学者や再帰理論研究者は再帰理論を計算可能性理論と呼ぶ。実際のところ、この2つの研究分野は、数学の研究室で行われているか、計算機科学の研究室で行われているかの違いしかない。
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「計算理論」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|