Wikipedia

「抽象機械」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
m fix template param obsolete error
タグ: 2017年版ソースエディター
編集の要約なし
2行目:
| 出典の明記 = 2009年10月<!-- ノートに議論がないため2013年8月に未検証から出典の明記に書き換え -->
}}
'''抽象機械'''（'''抽象コンピュータ'''とも呼ばれる）は、[[オートマトン計算モデル]]で利用されるのうち、[[コンピチュータリングマシン]]ハードウェアやソフトウェアシステムなどの理論上モデルような「機械っぽい」ものを指す語である。
計算処理の抽象化は、計算機科学と計算機工学の両方の分野で行われ、通常は離散時間[[パラダイム]]を仮定している。
 
==情報概要==
[[理論計算機科学]]ないし主に[[計算理論]]がこれに関係する主たる分野であるが、現実のコンピュータへの応用などもある。他の「機械っぽくない」[[計算モデル]]も含む一般的な議論はそちらを参照のこと。
計算理論において抽象機械は、計算可能性に関してまたはアルゴリズムの複雑さを分析するために（[[計算複雑性理論]]を参照すること）、[[思考実験]]でよく利用される。典型的な抽象機械は、入力、出力、そして前者を後者にするために利用され許可される操作のセットの観点による定義から構成される。最も良く知られている例として[[チューリングマシン]]がある。
 
[[チューリングマシン]]の提案がそうであったように、[[計算可能性理論]]でも使われるが、[[レジスタマシン]]の記事にあるうちのいくつかのような、現実のコンピュータに比較的近い抽象機械は、[[計算複雑性理論]]や、あるいはより現実的な実際のコンピュータにおける計算量の議論のために使いやすいといったことに特徴がある。
より複雑な定義により、完全な[[命令セット]]、[[レジスタ (コンピュータ)|レジスタ]]、そして[[:en:memory hierarchy|記憶のモデル]]を伴う抽象機械が作られる。本物の機械とよく似た平易なモデルの一つは[[:en:Random-access machine|RAMモデル]]であり、それはランダムアクセスによりメモリロケーションを索引付けできるようにする。[[キャッシュメモリ]]の異なるレベル間のパフォーマンスの差異が肥大するため、外部メモリモデルやキャッシュを気付かせないモデルが重要となってきている。
 
1例として、チューリングマシンにおけるテープは、読み書きしたい目的の場所まで、ひとコマずつ移動させなければならず、少しでも複雑なことをすると途端に必要なステップ数は膨大となる。そのため、実際のコンピュータで使うようなアルゴリズムの計算量の検討には、チューリングマシンは向かない。それに対し例えば、random-access machineの頭字語で「RAM」という抽象機械は（[[:en:Random-access machine]]）、名前の通りメモリにランダムアクセスが、すなわちメモリのどこでも一定ステップで読み書きが、できる。
抽象機械はまだハードウェアとして実装されていない（あるいは実装を意図されていない）[[マイクロプロセッサ]]設計を指すこともある。ソフトウェアシミュレーションとして、あるいは実在する[[インタプリタ]]において実装された抽象機械は[[仮想機械]]と呼ばれる。
 
キャッシュメモリなど、記憶の階層（[[:en:Memory hierarchy]]）の段階が増えてきている近年では、速いメモリをできるだけ使うことが高速化の鍵になっており、計算量の議論もそれを考慮する必要がある場合もある。それを考慮した抽象機械の必要性もあるかもしれない。
抽象機械の利用を通じて、実際のシステムで行うことなしに、個々の操作を実行するために必要な資源（時間、メモリなど）の量を計算することが可能となる。
 
[[SECDマシン]]のような、より実用を目的とした抽象機械もある。他の例としては、[[OCaml]]のベースであるCamlは、もともとはCategorical abstract machine（[[:en:Categorical abstract machine]]）という抽象機械をベースとした実装だったことからその名前が付いた（後に別の抽象機械をベースに、大幅に改造された）。そのような抽象機械と、「[[仮想機械]]」という語が指すものとの違いは、いくぶんはっきりしない。明確に分けることは不可能だが、抽象というよりは具体に近いほうが仮想機械と言えるであろう（歴史的理由から、仮想機械（virtual machine）という語は、全く無関係ではないにしても異なった2種類のものを指すようになってしまっている。英語版 [[:en:Virtual machine]] で system virtual machine ではなく process virtual machine としているほうが、ここで議論しているほうである）。
==チューリング等価なシーケンシャル抽象機械モデルに関する条項==
一つのアプローチは、[[チューリング完全|チューリング等価な]]抽象機械を分類するための、幾分形式的な分類上のアプローチを得るためである。この分類には[[有限オートマトン]]は含まれない:
 
==階層的分類==
'''科: チューリング等価な (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) モデル''':
▲:属 (1.1)* テープベースの - [[チューリングマシン]]モデルの変形など
::{ [[ハーバード・アーキテクチャ]]における状態機械の''間接アドレス指定''を追加した命令を除いたCounter-machine modelモデル; ハーバード・アーキテクチャにおける状態機械の命令を除いた間接指定アドレッシングを追加した「アキュムレータ」を伴う任意のモデル }▼
▲: {** シングルテープ、マルチテープチューリングマシン、決定性的チューリングマシン、非決定性的チューリングマシン、Wang B-マシン、ポストチューリングマシン、[[神託機械]]、万能チューリングマシン }
:'''種 (1.2.3) -- ランダムアクセスプログラム記憶式機械''' (RASP) モデルは以下を含む:
▲:属 (1.2)* レジスタベースの - [[レジスタマシン]]
:: { 万能チューリングマシンに似たレジスタ内に記憶されたプログラムを伴うRAM、すなわち[[ノイマン型|ノイマン型アーキテクチャ]] }
** counter machine、RAM（Random-Access Machine）、RASP（Random-Access Stored-Program machine）、pointer machine
:'''種 (1.2.4)-- ポインタマシン''' モデルは以下を含む:
レジスタベースのそれぞれについての詳細は以下のようになる。
::= { Schonhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton }▼
* counter machine
▲**（[[:en:{Counter machine]] も参照）アバカスマシン、Lambekマシン、Melzakモデル、ミンスキーマシン、Shepherdson-Sturgisマシン、プログラムマシンなど }
* RAM（Random-Access Machine）
▲**（[[:en:{Random-access machine]] を参照）<!--[[ハーバード・アーキテクチャ]]における状態機械の''間接アドレス指定''を追加した命令を除いたCounter-machine modelモデル; ハーバード・アーキテクチャにおける状態機械の命令を除いた間接指定アドレッシングを追加した「アキュムレータ」を伴う任意のモデル }--><!--意味わかんないんですけどとりあえず残しておきます-->
* RASP（Random-Access Stored-Program machine）
** （[[:en:Random-access stored-program machine]] も参照）[[ノイマン型|ノイマンマシン]]
* pointer machine
▲** （[[:en:=Pointer {machine]] Schonhageも参照）Schonhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton }
<!--Within each of the model-species there are varieties.
 
48 ⟶ 45行目:
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) -->
==その他の抽象機械分類==
*[[:en:Caml]] (Categorical abstract machine language)]]▼
*[[ABC (プログラミング言語)]]{{要出典|date=2016年12月}}
*[[:en:Algebraic Logic Functional programming language]]
▲*[[:en:Caml]] (Categorical abstract machine language)
*[[文脈自由文法]]
*[[有限オートマトン]]
* [[Prolog]]用の抽象機械:▼
*[[仕様及び記述言語]]
▲* [[Prolog]]用の抽象機械:
**[[:en:Warren Abstract Machine]]
*[[MMIX]]
*[[:en:MikroSim]]
*[[SECDマシン]]
*[[:en:Ten15]]
**[[:en:TenDRA Distribution Format]]
 
==関連項目==
*[[抽象化 (計算機科学)]]
*[[:en:Discrete time]]
*[[:en:State space]]
*[[:en:Computability#Formal models of computation]]
 
==脚注==
「https://ja.wikipedia.org/wiki/抽象機械」から取得