計算モデル

出典: フリー百科事典『ウィキペディア(Wikipedia)』
計算模型から転送)
移動: 案内検索

計算モデルmodel of computation)とは、人工的な計算機を含め、計算推論証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。

また、抽象機械abstract machine)と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。

計算過程の抽象化は計算機科学計算機工学で一般に使われる手法である。

計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。

計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。

典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。

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

ハードウェアとして実装されていない(実装する予定のない)マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。

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