抽象機械

抽象機械とは

抽象機械とは、計算モデルの一つであり、特にチューリングマシンのような「機械的な」形式の計算を指します。これらのモデルは理論計算機科学、つまり計算理論と深く関わっているものの、実際のコンピュータへの応用も考えられます。他にも「機械っぽくない」計算モデルも存在するため、そちらに興味がある方は別の文献を参照することをお勧めします。

計算可能性理論と抽象機械

計算可能性理論の領域において、チューリングマシンは重要な役割を果たしていますが、実際のコンピュータの動作に近い抽象機械としてはレジスタマシンや他のモデルも考慮されています。これらは計算複雑性理論や、実際のコンピュータにおける計算量の議論においても使いやすい特徴があります。

例えば、チューリングマシンではテープを使った読み書きが行われますが、目的の位置まで移動するのに手間がかかるため、複雑な処理を行う際には効率が悪くなります。このため、実用的なアルゴリズムの評価には必ずしも適していません。一方、「ランダムアクセスマシン」（RAM）のような型の抽象機械は、名前の通り、メモリに対して任意の位置に一定時間でアクセスできるため、より効率的な計算が可能です。

メモリ階層と計算量

最近のコンピュータは、キャッシュメモリなどのメモリ階層の複雑さを増してきています。このため、より高速なメモリを活用して処理速度を上げることが求められ、計算量に関する議論もこれらの要因を考慮する必要があります。このような新たなニーズを満たすために、新しい抽象機械のモデルが求められています。

実用的な抽象機械の例

SECDマシンなど、具体的な用途を意図した抽象機械も存在します。加えて、OCamlの基盤となるCamlは、もともと「Categorical Abstract Machine」に由来する実装であり、後に別の抽象機械を基にして改良が施された経緯があります。ここで言う「抽象機械」と「仮想機械」（virtual machine）の違いは曖昧で、多くの場合、抽象度の低い具体的なモデルが仮想機械として分類されることがあります。特に「仮想機械」という言葉は、歴史的な理由から異なる概念を指すようにもなってきました。

抽象機械の階層的分類

抽象機械は分類が可能で、ここで示すのはチューリング完全であるものに限定されています。直列計算と並列計算の二つの大まかな枠組みがあります。以下は直列計算に限定した分類です。

• - テープベースの機械: チューリングマシンの変種や、決定的・非決定的チューリングマシンなど。
• - レジスタベースの機械: レジスタマシン、カウンターマシン、RAM、ポイントマシンなど。

レジスタベースの機械について

• - カウンターマシン: アバカスマシンやLambekマシン、Melzakモデルなど。
• - RAM: ランダムアクセスマシン。
• - ポイントマシン: Schonhage Storage Modification MachineやKolmogorov-Uspensky KU-machine、Knuth linking automatonなど。

その他の抽象機械

その他の例として、Categorical Abstract Machine、有限オートマトン、Prolog用の抽象機械、Warren Abstract Machine、SECDマシン、Ten15、TenDRA Distribution Formatなどが挙げられます。

これらの様々な抽象機械は、計算理論やプログラミング言語の実装において重要な役割を果たし続けています。

もう一度検索