「抽象機械」の版間の差分
削除された内容 追加された内容
計算模型へのリダイレクト |
en:Abstract machine (23:19, 16 June 2013 UTC) を翻訳 |
||
1行目:
{{Cleanup|date=2011年10月}}
{{未検証|date=2009年10月}}
'''抽象機械'''（'''抽象コンピュータ'''とも呼ばれる）は、[[オートマトン]]で利用される、[[コンピュータ]]ハードウェアやソフトウェアシステムの理論上モデルである。
計算処理の抽象化は、計算機科学と計算機工学の両方の分野で行われ、通常は離散時間[[パラダイム]]を仮定している。
==情報==
計算理論において抽象機械は、計算可能性に関してまたはアルゴリズムの複雑さを分析するために（[[計算複雑性理論]]を参照すること）、[[思考実験]]でよく利用される。典型的な中小機械は、入力、出力、そして前者を後者にするために利用され許可される操作のセットの観点による定義から構成される。最も良く知られている例として[[チューリングマシン]]がある。
より複雑な定義により、完全な[[命令セット]]、[[レジスタ (コンピュータ)|レジスタ]]、そして[[:en:memory hierarchy|記憶のモデル]]を伴う抽象機械が作られる。本物の機械とよく似た平易なモデルの一つは[[en:Random-access machine|RAMモデル]]であり、それはランダムアクセスによりメモリロケーションを索引付けできるようにする。[[キャッシュメモリ]]の異なるレベル間のパフォーマンスの差異が肥大するため、外部メモリモデルやキャッシュを気付かせないモデルが重要となってきている。
抽象機械はまだハードウェアとして実装されていない（あるいは実装を意図されていない）[[マイクロプロセッサ]]設計を指すこともある。ソフトウェアシミュレーションとして、あるいは実在する[[インタプリタ]]において実装された抽象機械は[[仮想機械]]と呼ばれる。
抽象機械の利用を通じて、実際のシステムで行うことなしに、個々の操作を実行するために必要な資源（時間、メモリなど）の量を計算することが可能となる。
==チューリング等価なシーケンシャル抽象機械モデルに関する条項==
一つのアプローチは、[[チューリング完全|チューリング等価な]]抽象機械を分類するための、幾分形式的な分類上のアプローチを得るためである。この分類には[[有限オートマトン]]は含まれない:
'''科: チューリング等価な (Turing-equivalent, TE) 抽象機械''':
'''亜科:'''
:亜科 (1) シーケンシャルTE抽象機械
:亜科 (2) 並列TE抽象機械 <!-- BUT, see OPS! sec. on the Talk page -->
'''亜科 (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 }
<!--Within each of the model-species there are varieties.
Within a species, ne possible classification can be by the number of parameters used. The way to figure this out formally is to actually build the models (e.g. in an Excel spreadsheet) and see how many operands (i.e. Excel cells) are required to specify an instruction. In the following the "jump-to" address as an additional operand. So for instance the Schonhage model has no operands excepting the jump-to address in an extra goto instruction:
*0- & 1- operand: Schonage model
*1- & 2- operand: Minsky (1967) model
*2- & 3- operand: Minsky (1961), Lambek (1961)
*3- & 4- operand: Malzek (1961)
There are models with "convenience instructions" (e.g. unconditional-J xxx, CLR h; CPY a,b ) including in particular:
* 2-operand: Shepherdson-Sturgis (1963), Minsky (1967) -->
==他の抽象機械==
*[[ABC (プログラミング言語)]]
*[[:en:Abstract machine Notation]]
*[[:en:Algebraic Logic Functional programming language]]
*[[:en:Caml]]
*[[文脈自由文法]]
*[[有限オートマトン]]
*[[:en:Specification and Description Language]]
* [[Prolog]]用の歴史的で簡易な抽象機械:
**[[:en:Vienna Abstract Machine]] ([[:en:VAM Prolog]])
**[[:en:Warren Abstract Machine]] ([[:en:WAM Prolog]])
**[[:en:Berkeley Abstract Machine]] ([[:en:BAM Prolog]]).
*[[MMIX]]
*[[:en:MikroSim]]
*[[SECDマシン]]
*[[:en:Ten15]]
*[[:en:TenDRA Distribution Format]]
*[[:en:Zinc abstract machine]]
==関連項目==
*[[抽象化 (計算機科学)]]
*[[抽象解釈]]
*[[:en:Discrete time]]
*[[:en:State space]]
*[[:en:Computability#Formal models of computation]]
==脚注==
*{{MathWorld|title=Abstract Machine|urlname=AbstractMachine|author=Macura, Wiktor K.}}
*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.
* Stephan Diehl, Pieter Hartel and Peter Sestoft, [http://www.inf.ed.ac.uk/teaching/courses/lsi/diehl_abstract_machines.pdf ''Abstract Machines for Programming Language Implementation''], Future Generation Computer Systems, Vol. 16(7), Elsevier, 2000.
{{FOLDOC}}
{{DEFAULTSORT:ちゆしようきかい}}
[[Category:計算モデル]]
| |||