計算モデル

計算モデル（けいさんモデル、（英: model of computation）は、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルである。計算模型ともいう。これに含まれるうちで、チューリングマシンなどのような、現実の機械に似せた架空のものを抽象機械といい、そうでないものとしてはラムダ計算などがある。ラムダ計算は数学の関数式の組み合わせであり、ソースコードのような計算モデルである。

理論計算機科学の多くの分野で、「計算機械」を理論的に、すなわちモデル化して扱うために多大に活用されている。また特に抽象機械は、実際のプロセッサやコンパイラやインタプリタの研究や開発など、理論に限らず実際的な分野でも活用される。計算理論においては、計算可能性や計算複雑性について形式的・定量的に示すためなどに使われており、古典的な成果にチャーチ＝チューリングのテーゼがある。

より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデル（ランダムアクセスマシン）がある。これはメモリに対してインデックス付けによりランダムアクセス可能な計算モデルである（チューリングマシンではテープの1区画ずつの移動しかできない）。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなるにつれて、メモリの階層を前提とした計算モデルが重要となった。

ハードウェアとして実装されていない（実装する予定のない）プロセッサの設計も一種の抽象機械である^[1]。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。研究目的などで、より抽象的な抽象機械の実装を作って研究などに使うこともある。

抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。

• チューリングマシン
• レジスタマシン
• スタックマシン
• ラムダ計算
• セルオートマトン
• SECDマシン
• CEK機械
• 帰納函数
• 論理回路
• 形式文法
• プッシュダウン・オートマトン
• 有限状態機械
• 状態遷移図
• 神経細胞網
• 量子計算機

1. ^ と言えなくもないが、実機のプロセッサに近い設計では、理論的に扱うための利点はほぼ無い。

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集