RAMマシンは、レジスタマシンのクラスに属する抽象的なチューリングコンピューターです。 これは、普遍的なチューリングマシンと同等であり、アルゴリズムの正確性を証明するのにより視覚的で便利です。 このトピックでは、それがどのように配置されているかを説明し、PAMマシンエミュレーターの動作する実装へのリンクをいくつかの興味深い例とともに添付します。
RAMマシン（RAM：Random Access Machine）の抽象モデルには、無限のレジスタセットが含まれ、各レジスタには任意の長さの整数を格納できます。 レジスタインデックスには、任意の整数（負を含む）を指定できます。 RAMマシン用のプログラム-メモリレジスタを変更する命令の有限セット。 非常に単純なアセンブラーとして見ることができます。 一連のコマンドを検討することで、マシンの研究を開始します。
停止
マシンに到達すると実行を停止するよう指示する最も単純な命令。
読む
マシンはI / Oをサポートする必要があり、READ操作はキーボードから数値を入力するように設計されています（または、別のストリームは、抽象モデルを扱っていることを忘れないでください。ここでは、大規模な問題を解決できるようにアルゴリズムにデータ入力を提供します）。 番号はレジスタ
[0]
に入力され、このレジスタは引き続き「特別」と見なされます。
書きます
[0]
保存されている番号を（画面に）表示します。 これ以上の引数はありません。
LOAD x / [x] / [[x]]
トリッキーな命令-任意の値を
[0]
書き込みます。 値は定数に設定できます：
LOAD 5
など。 または、別のセルからコピー：
LOAD [3]
-ここでは、3番目のレジスタからの値がゼロにコピーされます。 または、ダブルアドレッシングを使用して：
LOAD [[3]]
-3番目のレジスタが「参照する」レジスタからの番号は「ゼロ」になります。 したがって、マシンが間接アドレス指定をサポートしていることがわかります。
STORE [x] / [[x]]
[0]
値を指定したセルに書き込みます。 直接アドレス指定：
STORE [1]
または間接アドレス指定：
STORE [[1]]
いずれかが利用可能です。
NEG
[0]
数値の符号を反転します。 したがって、
-3
は
3
に置き換えられ、符号にはゼロがありません。
LSHIFT x / [x] / [[x]]
[0]
数値を指定された引数だけビット単位で左シフトします。 利用可能な定数、直接アドレス、間接アドレス。 たとえば、
LSHFIT [[3]]
は、
[0]
値に
[3]
参照されるレジスタ値の累乗の2を乗算します。
RSHIFT x / [x] / [[x]]
LSHIFTと同様に、ビット単位の右シフト、引数、および意味を実行します。 クラシックモデルでは、LSHIFT / RSHIFTの引数として符号付き数値を使用できません。
ADD x / [x] / [[x]]
関数の引数で指定された値を
[0]
追加します。 使用可能な定数、直接アドレス指定、間接。
最後に、サイクルと条件を整理するのに役立ちます。
JUMP タグ
指定されたコード行またはラベルへの無条件ジャンプ。
JG タグ
ゼロレジスタの値が厳密に正の場合、指定されたラベルに移動します。
以上です！
しかし、他の算術演算はどうでしょうか？ はい、古典的なモデルは冗長な命令を意味するものではないため、追加によって実装する必要があります。 小さなパズルとして、私は以下を実装することを提案します：
- mにnを掛ける（ O（max（m、n））より速い）;
- 平方m（ O（m）より速い）;
- 度m（ O（m * log（m））より速い）;
- 任意の次数のルート（ニュートンの方法を思い出してください）。
より困難なタスクは、各メソッドの実装の複雑さと正確さの証明と考えることができます（ただし、ここではチューリングマシンよりもはるかに簡単です）。
マシンの最も単純な特性の1つは、 デッドロック状態（安定した役に立たない状態）を簡単に検出できることです。同じラベルに切り替えたときに、レジスタ値が同じままであれば、「ハング」します。
キーボードから入力されたN個の数値を合計する単純なプログラムの例（私は願っています、自明です）（エミュレーターの実行可能ファイルを含むアーカイブ内の他の例）：
いくつかのバリエーション（正直なところ、最初は学校の子供たちを「楽しませる」ために） いくつかのプリミティブ（点と線）を追加して、面白いものを作成できるグラフィック要素を描画しました。 例：
このリンクから実装をダウンロードできます。ソースはこちらからダウンロードできます。 ソースコードの品質、およびそれらが記述されている言語（そう、これはDelphiです）はそれほど欠陥がないはずです。何年も前にそれらを書いたので、私はすべてがうまくいくことに驚いています。 実装は長い算術演算をサポートし、無限の数のレジスタをエミュレートしますが、物理マシンのメモリは無制限ではないことがわかります:)
頑張ってください！