抽象マシンとは？

オートマトンとも呼ばれる抽象マシンは、理論的なコンピューターサイエンスの要素です。 抽象マシンは、数学の機能に似ています。 指定されたルールに従って入力を受け取り、出力を生成します。 抽象マシンは、ハードウェアから完全に独立して機能すると想定されているため、よりリテラルなマシンとは異なります。 それらは、操作の実行方法や受け取ることができる入力のタイプなどの特性に基づいて、タイプに細分化されます。

抽象マシンを分類する場合、最も単純な違いの1つは、任意の時点で実行が許可されている操作の数に関するものです。 抽象マシンは、進行する方法が常に1つしかない場合、確定的と呼ばれます。 可能な状態の少なくとも1つにあるマシンに複数の可能性が存在する場合、非決定的です。 「プッシュダウン」オートマトンは、入力の順番に1つずつ単純に応答するのではなく、入力のスタックを操作する機能を備えたオートマトンです。

Wolfram MathWorldは抽象マシンの2つの有名な例を提供します。 これらの例の1つはConwayのライフゲームです。これは、1つの構成のみが他の構成から出現するため、決定論的な抽象マシンです。 このゲームでは、各ボックスまたはセルの状態が「生きている」または「死んでいる」グリッドを使用します。 グリッド全体の状態は、以前の状態に基づいて決定されます。 生きている細胞がちょうど2つまたは3つの他の生きている細胞に触れると、生き続けます。 1つ、2つ、または3つ以上（最大8つ）の近隣がある場合、それは死にます。 正確に3つの隣人がいる死んだ細胞が生き返ります。 それ以外の場合は、デッドのままです。

別の例であるチューリングマシンは、コンピューターサイエンスの最も基本的かつ基本的な抽象マシンの1つです。 チューリングマシンは、無制限のサイズのテープ（一連の記号）に対して操作を実行します。 シンボルを変更するための指示と、操作しているシンボルを変更するための指示の両方が含まれています。 単純なチューリングマシンには、「シンボルを1に変換してから右に移動する」という命令しかありません。 このマシンは、1のストリングのみを出力します。 この単純なチューリングマシンは決定論的ですが、同じ入力に対して複数の異なる操作を実行できる非決定論的チューリングマシンを構築することもできます。

これらの抽象的なマシンは、多くの目的に役立ちます。 これらは楽しい理論上のおもちゃになりますが、実際のコンピューターシステムのモデルとしても機能します。 抽象マシンは、規律としてコンピューターサイエンスの中心にあります。