抽象マシンとは何ですか？

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

抽象マシンを分類する場合、最も単純な区別の1つは、特定のポイントで実行できる操作の数に関係しています。抽象的なマシンは、常に1つの方法しか進行しない場合、決定論的と呼ばれます。可能な状態の少なくとも1つにマシンに複数の可能性が存在する場合、それは非決定論です。 「プッシュダウン」オートマトンは、入力のスタックを操作する能力を備えたものです。それらが現れる順序で。

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

別の例であるチューリングマシンは、コンピューターサイエンスで最も基本的で基本的な抽象マシンの1つです。チューリングマシンは、テープで操作を実行します - シンボルの文字列 - 無制限のサイズの。これには、シンボルを変更することと、それが動作しているシンボルを変更するための指示が含まれています。単純なチューリングマシンには、「シンボルを1に変換してから右に移動する」という命令のみがある場合があります。このマシンは、1つの文字列以外のものを出力しません。このシンプルなチューリングマシンは決定論的ですが、同じ入力を考慮していくつかの異なる操作を実行できる非決定的チューリングマシンを構築することも可能です。

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