抽象機械

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

抽象機械抽象コンピュータとも呼ばれる)は、オートマトンで利用される、コンピュータハードウェアやソフトウェアシステムの理論上モデルである。 計算処理の抽象化は、計算機科学と計算機工学の両方の分野で行われ、通常は離散時間パラダイムを仮定している。

情報[編集]

計算理論において抽象機械は、計算可能性に関してまたはアルゴリズムの複雑さを分析するために(計算複雑性理論を参照すること)、思考実験でよく利用される。典型的な中小機械は、入力、出力、そして前者を後者にするために利用され許可される操作のセットの観点による定義から構成される。最も良く知られている例としてチューリングマシンがある。

より複雑な定義により、完全な命令セットレジスタ、そして記憶のモデルを伴う抽象機械が作られる。本物の機械とよく似た平易なモデルの一つはRAMモデルであり、それはランダムアクセスによりメモリロケーションを索引付けできるようにする。キャッシュメモリの異なるレベル間のパフォーマンスの差異が肥大するため、外部メモリモデルやキャッシュを気付かせないモデルが重要となってきている。

抽象機械はまだハードウェアとして実装されていない(あるいは実装を意図されていない)マイクロプロセッサ設計を指すこともある。ソフトウェアシミュレーションとして、あるいは実在するインタプリタにおいて実装された抽象機械は仮想機械と呼ばれる。

抽象機械の利用を通じて、実際のシステムで行うことなしに、個々の操作を実行するために必要な資源(時間、メモリなど)の量を計算することが可能となる。

チューリング等価なシーケンシャル抽象機械モデルに関する条項[編集]

一つのアプローチは、チューリング等価な抽象機械を分類するための、幾分形式的な分類上のアプローチを得るためである。この分類には有限オートマトンは含まれない:

科: チューリング等価な (Turing-equivalent, TE) 抽象機械: 亜科:

亜科 (1) シーケンシャルTE抽象機械
亜科 (2) 並列TE抽象機械

亜科 (1)-- シーケンシャルTE抽象モデル : 現在使用されているシーケンシャルTE抽象機械の2つの階層(属)がある(例としてvan Emde Boasを参照すること):

属 (1.1) テープベースのチューリングマシンモデル
属 (1.2) レジスタベースのレジスタマシン

属 (1.1) -- テープベースのチューリングマシンモデル これは以下の「種」を含む:

{ シングルテープ、マルチテープチューリングマシン、決定性チューリングマシン、非決定性チューリングマシン、Wang B-マシン、ポストチューリングマシン、神託機械、万能チューリングマシン }

属 (1.2)-- レジスタマシンモデル : これには以下の(少なくとも)4つの「種」が含まれる(他のものはvan Emde Boasにより言及される):

{ (1.2.1) カウンタ機械、(1.2.2) ランダムアクセスマシン RAM、(1.2.3) ランダムアクセスプログラム記憶式機械 RASP, (1.2.4) ポインタマシン }
種 (1.2.1) -- カウンタ機械:
{ アバカスマシン、Lambekマシン、Melzakモデル、ミンスキーマシン、Shepherdson-Sturgisマシン、プログラムマシンなど }
種 (1.2.2) -- ランダムアクセス (RAM) モデル:
{ ハーバード・アーキテクチャにおける状態機械の間接アドレス指定を追加した命令を除いたCounter-machine modelモデル; ハーバード・アーキテクチャにおける状態機械の命令を除いた間接指定アドレッシングを追加した「アキュムレータ」を伴う任意のモデル }
種 (1.2.3) -- ランダムアクセスプログラム記憶式機械 (RASP) モデルは以下を含む:
{ 万能チューリングマシンに似たレジスタ内に記憶されたプログラムを伴うRAM、すなわちノイマン型アーキテクチャ }
種 (1.2.4)-- ポインタマシン モデルは以下を含む:
= { Schonhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton }

他の抽象機械[編集]

関連項目[編集]

脚注[編集]

  • Macura, Wiktor K., "Abstract Machine" - MathWorld.(英語)
  • Peter van Emde Boas, Machine Models and Simulations pp. 3?66, appearing in:
Jan van Leeuwen, ed. "Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990.

この記述は GNU Free Documentation License のもとに公開されているコンピュータ用語辞典『 Free On-line Dictionary of Computing (FOLDOC) 』に基づいています。