抽象機械
From Wikipedia, the free encyclopedia
理論計算機科学ないし主に計算理論がこれに関係する主たる分野であるが、現実のコンピュータへの応用などもある。他の「機械っぽくない」計算モデルも含む一般的な議論はそちらを参照のこと。
チューリングマシンの提案がそうであったように、計算可能性理論でも使われるが、レジスタマシンの記事にあるうちのいくつかのような、現実のコンピュータに比較的近い抽象機械は、計算複雑性理論や、あるいはより現実的な実際のコンピュータにおける計算量の議論のために使いやすいといったことに特徴がある。
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 としているほうが、ここで議論しているほうである）。