X-machine とは

X-machine(XM)は、1974年にSamuel Eilenbergによって導入された理論計算モデルです。「X-machine」のXは、機械が動作する基本的なデータタイプを表します。たとえば、データベース(タイプデータベースのオブジェクト)で動作するマシンは、データベースマシンとなります。 Xマシンモデルは有限状態マシンと構造的には同じですが、マシンの遷移をラベル付けするために使用されるシンボルはタイプX→Xの関係を示します。トランジションをクロスすることは、それをラベル付けするリレーションを適用すること(データタイプXに一連の変更を計算すること)と同じであり、マシン内のパスをトラバースすることは、すべての関連リレーションを順番に適用することに対応します。