抽象機械

抽象機械（ちゅうしょうきかい）とは、計算モデルのうち、チューリングマシンなどのような「機械っぽい」ものを指す語である。

概要

理論計算機科学ないし主に計算理論がこれに関係する主たる分野であるが、現実のコンピュータへの応用などもある。他の﹁機械っぽくない﹂計算モデルも含む一般的な議論はそちらを参照のこと。

チューリングマシンの提案がそうであったように、計算可能性理論でも使われるが、レジスタマシンの記事にあるうちのいくつかのような、現実のコンピュータに比較的近い抽象機械は、計算複雑性理論や、あるいはより現実的な実際のコンピュータにおける計算量の議論のために使いやすいといったことに特徴がある。

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 としているほうが、ここで議論しているほうである︶。

階層的分類

いくらかの抽象機械は、階層的に分類できる。ここではチューリング完全のもののみを対象とする。以下は網羅したものではないし、このような分類のしかたが唯一のものというわけでもない。

●直列計算の機械

●並列計算の機械

以下は直列計算の機械のみである。

●テープベース - チューリングマシンの変形など
●シングルテープ、マルチテープチューリングマシン、決定的チューリングマシン、非決定的チューリングマシン、Wang B-マシン、ポストチューリングマシン、神託機械、万能チューリングマシン

●レジスタベース - レジスタマシン
●counter machine、RAM︵Random-Access Machine︶、RASP︵Random-Access Stored-Program machine︶、pointer machine

レジスタベースのそれぞれについての詳細は以下のようになる。

• counter machine
  • （en:Counter machine も参照）アバカスマシン、Lambekマシン、Melzakモデル、ミンスキーマシン、Shepherdson-Sturgisマシン、プログラムマシン
• RAM（Random-Access Machine）
  • （en:Random-access machine を参照）
• RASP（Random-Access Stored-Program machine）
  • （en:Random-access stored-program machine も参照）ノイマンマシン
• pointer machine
  • （en:Pointer machine も参照）Schonhage Storage Modification Machine SMM, Kolmogorov-Uspensky KU-machine, Knuth linking automaton

その他の分類

• en:Categorical abstract machine
• 有限オートマトン
• Prolog用の抽象機械
  • en:Warren Abstract Machine
• SECDマシン
• en:Ten15
  • en:TenDRA Distribution Format

脚注

• Macura, Wiktor K. "Abstract Machine". mathworld.wolfram.com (英語).
• 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, Abstract Machines for Programming Language Implementation, Future Generation Computer Systems, Vol. 16(7), Elsevier, 2000.

この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。