19/08/06 22:09:11.85 /q1/+QCZ.net
コンピュータサイエンスは、基本は有限ですね
URLﾘﾝｸ(www.math.keio.ac.jp)
慶応
数理科学科
(抜粋)
数理科学科における４年次の卒業研究のテーマは，「数学」「統計学」「コンピュータ・サイエンス」の３つのものに大別されます．
組み合わせ論やグラフ理論などの「有限」をあつかう数学の分野もあり，これらはコンピュータ・サイエンスとも関係の深いものです．
URLﾘﾝｸ(ja.wikipedia.org)
計算理論
(抜粋)
無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。
「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。
よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。[1]