計算模型

ウィキペディア

計算モデル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/31 06:19 UTC 版)

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

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

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

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

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

関連項目

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

脚注

[脚注の使い方]

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

表 話 編 歴 コンピュータ科学
ハードウェア	プリント基板 周辺機器 Integrated Circuit (IC) Very Large Scale Integration (超大規模集積回路、VLSI) Systems on Chip (SoC) エネルギー消費 (グリーン・コンピューティング) EDA ハードウェアアクセラレーション
コンピュータシステムの構造	コンピュータ・アーキテクチャ 組み込みシステム リアルタイムシステム ディペンダビリティ
ネットワーク	ネットワーク・アーキテクチャ（英語版） 通信プロトコル ネットワーク・コンポーネント（英語版） ネットワーク・スケジューラ（英語版） ネットワーク性能評価（英語版） ネットワーク・サービス（英語版）
ソフトウェアの構造	インタプリタ ミドルウェア 仮想マシン オペレーティングシステム ソフトウェア品質
ソフトウェア記法（英語版） とツール	プログラミングパラダイム プログラミング言語 コンパイラ ドメイン固有言語 モデリング言語 ソフトウェアフレームワーク 統合開発環境 ソフトウェア構成管理 ソフトウェアライブラリ ソフトウェアリポジトリ
ソフトウェア開発	ソフトウェア開発プロセス 要求分析 ソフトウェア設計 ソフトウェア構築（英語版） ソフトウェアデプロイメント ソフトウェアメンテナンス プログラミングチーム（英語版） オープンソースモデル
計算理論	計算モデル 形式言語 オートマトン理論 計算可能性理論 計算複雑性理論 コンピュータ科学における論理学（英語版） 意味論
アルゴリズム	アルゴリズム（英語版） アルゴリズム解析 アルゴリズム効率（英語版） 乱択アルゴリズム 計算幾何学
コンピューティングの数学	離散数学 確率 統計学 数学ソフトウェア 情報理論 解析学 数値解析
情報システム	データベース管理システム 情報ストレージシステム 企業情報システム 社会情報システム（英語版） 地理情報システム 意思決定支援システム プロセス制御システム マルチメディア情報システム（英語版） データマイニング 電子図書館 コンピューティング・プラットフォーム デジタルマーケティング World Wide Web 情報検索
セキュリティ	暗号理論 形式手法 セキュリティ・サービス（英語版） 侵入検知システム ハードウェア・セキュリティ（英語版） ネットワーク・セキュリティ 情報セキュリティ アプリケーション・セキュリティ（英語版）
ヒューマンコンピュータ インタラクション	インタラクションデザイン ソーシャル・コンピューティング（英語版） ユビキタスコンピューティング 可視化 アクセシビリティ
並行性	並行コンピューティング 並列コンピューティング 分散コンピューティング マルチスレッディング マルチプロセッシング
人工知能	自然言語処理 知識表現と推論 コンピュータビジョン 自動計画とスケジューリング 検索手法 制御手法 人工知能の哲学（英語版） 分散人工知能（英語版）
機械学習	教師あり学習 教師なし学習 強化学習 マルチタスク学習（英語版） 交差検証
グラフィックス	アニメーション レンダリング 画像編集 GPU 複合現実 バーチャル・リアリティ 画像圧縮 ソリッドモデリング
応用コンピューティング	電子商取引 企業アプリケーション 計算数学（英語版） 計算物理学 計算化学 計算生物学 計算社会科学 計算工学（英語版） 健康情報学 デジタルアート 電子出版 サイバー戦争 電子投票 コンピュータゲーム ワードプロセッサー オペレーションズ・リサーチ 教育工学 文書管理システム
概要（英語版） カテゴリ ブック コモンズ

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