計算模型
出典: フリー百科事典『ウィキペディア(Wikipedia)』
計算模型(model of computation)とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理模型。計算モデルとも。また、抽象機械(abstract machine)と言った場合、特にオートマトン理論での計算システムの理論的モデルを意味する。計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。
計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する(計算科学参照)。
計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い(計算複雑性理論参照)。典型的な抽象機械は、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。代表例はチューリングマシンである。
より複雑な抽象機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的コンピュータの計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。
ハードウェアとして実装されていない(実装する予定のない)マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。
抽象機械を使用することで、実際にシステムを組み立てることなく特定の操作の実行に要するリソース(時間、メモリ使用量など)を計算で求めることが可能である。
カテゴリ: 計算モデル | 計算理論 | コンピュータ関連のスタブ項目