ランダムアクセスプログラム記憶マシン
理論計算機科学において、ランダムアクセス ストアード プログラム(RASP) マシン モデルは、アルゴリズム開発およびアルゴリズム複雑性理論の目的で使用される抽象マシンです。
RASPはランダムアクセスマシン（RAM）モデルの一種で、RAMとは異なり、プログラムと入力を「レジスタ」に格納します。レジスタの容量は無制限（無限大）ですが、レジスタの数が有限かどうかはモデルによって異なります。つまり、RASPとRAMの関係は、ユニバーサルチューリングマシンとチューリングマシンの関係に似ています。RASPはフォン・ノイマン・アーキテクチャの一例であり、RAMはハーバード・アーキテクチャの一例です。
RASPは、あらゆる抽象モデルの中で、コンピュータの一般的な概念に最も近いものです。しかし、実際のコンピュータとは異なり、RASPモデルは通常、非常にシンプルな命令セットを備えています。CISCプロセッサやRISCプロセッサの命令セットよりも大幅に簡素化されており、最も単純な算術演算、レジスタ間の「移動」、そして「テスト/ジャンプ」命令で構成されています。一部のモデルでは、アキュムレータなどの追加のレジスタを備えています。
レジスタ マシン、RAM、およびポインタ マシンとともに、RASP は 4 つの一般的なシーケンシャル マシン モデルを構成します。これらは、「並列」モデル (並列ランダム アクセス マシンなど) と区別するためにこのように呼ばれます [cf. van Emde Boas (1990)]。
非公式な定義: ランダムアクセスストアードプログラムモデル (RASP)
RASP の簡単な説明:
- RASP は、ランダム アクセス マシンRAM シャーシ上に構築されたユニバーサル チューリング マシン(UTM)です。
読者の皆様は、UTMが「普遍的な」有限状態命令表を持つチューリングマシンであり、テープ上に書き込まれたあらゆる整形式の「プログラム」をチューリング5組の文字列として解釈できることを覚えておられるでしょう。これがUTMの普遍性です。古典的なUTMモデルでは、テープ上にチューリング5組が存在することを期待しますが、チューリングマシンがそれらを見つけることを期待している限り、つまり有限状態表がそれらを解釈し、目的の動作に変換できる限り、想像し得るあらゆるプログラムセットをそこに置くことができます。テープには、プログラムと共に、入力データ/パラメータ/数値（通常はプログラムの右側）が印刷され、最終的には出力データ/数値（通常は両方の右側、または入力と混在、あるいは入力を置き換えて）が印刷されます。「ユーザー」はチューリングマシンのヘッドを最初の命令の上に置き、入力はテープ上のプログラムと有限状態マシンの命令表の両方に適した特定の場所と形式で配置する必要があります。
RASPはこの構造を模倣し、「プログラム」と「データ」をホール（レジスタ）に配置します。しかし、UTMとは異なり、RASPは条件付きテストによって命令が別の場所に送られない限り、命令を順番に「フェッチ」します。
混乱を招く点：2つの命令セット：UTMとは異なり、RASPモデルには2つの命令セットがあります。1つはステートマシン命令テーブル（「インタープリタ」）で、もう1つはホール内の「プログラム」です。この2つの命令セットは、必ずしも同じ命令セットから抽出される必要はありません。
RAMがRASPとして動作する例
次のプログラムの例では、レジスタ (ホール) #18 の内容をレジスタ (ホール) #19 に移動し、その過程で #18 の内容を消去します。
5: 03 18 15 JZ 18 , 15 ; [18] がゼロの場合、15 にジャンプしてプログラムを終了します02 18 DEC 18 ; [18] をデクリメントします01 19 INC 19 ; [19] をインクリメントします03 15 05 JZ 15 , 5 ; [15] がゼロの場合、5 にジャンプしてループを繰り返します (無条件ジャンプをシミュレートするには Halt を使用します) 15: 00 H ; 停止 18: n ; コピー元の値19: ; コピー先 この RASP マシンで使用できるプログラム命令は、例を短くするために単純なセットになります。
| 命令 | ニモニック | レジスタ「r」のアクション | 有限状態機械の命令レジスタIRに対するアクション |
|---|---|---|---|
| インクリメント | INC ( r ) | [r] +1 → r | [IR] +1 → IR |
| デクリメント | 12月（r） | [r] -1 → r | [IR] +1 → IR |
| ゼロの場合はジャンプ | JZ ( r, z ) | なし | [r] = 0 の場合、z → IR、そうでない場合、[IR] +1 → IR |
| 停止 | H | なし | [IR] → IR |
例を簡単にするために、 RAM-as-RASP のステート マシンに、同じセットから取得した基本命令を装備しますが、2 つの間接コピー命令が追加されます。
- RAM ステートマシン命令:
- { INC h; DEC h; JZ h,xxx; CPY ⟪h a ⟫, ⟨h a ⟩ ; CPY ⟨h a ⟩ ,⟪h a ⟫ }
RASPマシンのステートマシンがレジスタ内のプログラムを解釈する際、ステートマシンは具体的に何を行うのでしょうか？感嘆符「!」の付いた列には、ステートマシンがプログラムを「解釈」（アクションに変換）する際のアクションが時系列で表示されます。
| パソコン | IR | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 穴番号→ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| プログラム、パラメータ → | 5 | JZ | 18 | 15 | 12月 | 18 | 株式会社 | 19 | JZ | 15 | 5 | H | n | ||||||
| エンコードされたプログラム → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| ステートマシン命令 ↓ | |||||||||||||||||||
| ! |
伝統的に、ステートマシンの動作はフェッチと実行という2つの主要な「フェーズ」に分けられます。以下では、これらの2つの主要なフェーズの中にさらに「サブフェーズ」があることを説明します。統一された慣例はなく、モデルごとに正確な記述が必要になります。
フェッチフェーズ
ステートマシンはすべてのレジスタに直接的にも間接的にもアクセスできます。そのため、#1 を「プログラムカウンタ」PC として採用します。プログラムカウンタの役割は、プログラムのリストにおける「位置を保持する」ことです。ステートマシンは、自身専用の状態レジスタを持ちます。
起動時に、ステート マシンは PC 内で番号 (プログラムの最初の「プログラム命令」(つまり #5)) が見つかることを期待します。
(間接的な COPY を使用しない場合、ポイント先のプログラム命令を #2 に取り込む作業は少し困難です。ステート マシンは、ポイント先のレジスタを間接的にデクリメントしながら、(空の) レジスタ #2 を直接インクリメントします。「解析」フェーズでは、#2 のカウントを犠牲にして、犠牲になった #5 の内容を復元します。)
上記の回り道のポイントは、ステート マシンが 2 種類の間接コピーにアクセスできると、作業がはるかに簡単になることを示すことです。
- i から間接的にコピーし、j に直接コピーする: CPY ⟪h i ⟫, ⟨h j ⟩
- i から直接コピーし、j に間接的にコピーする: CPY ⟨h i ⟩ ,⟪h j ⟫
以下の例は、ステートマシンの「フェッチ」フェーズで何が起こるかを示しています。ステートマシンの操作は、「ステートマシン命令↓」という列に記載されています。フェッチの終了時に、レジスタ#2に最初の命令JZの「オペレーションコード」（「オペコード」）の数値3が格納されていることに注意してください。
| パソコン | PIR | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 穴番号→ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| プログラム、パラメータ → | 5 | JZ | 18 | 15 | 12月 | 18 | 株式会社 | 19 | JZ | 15 | 5 | H | n | ||||||||
| エンコードされたプログラム → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| ステップ | ステートマシン命令 ↓ | ||||||||||||||||||||
| 1 | フェッチ_instr: | CPY ⟪1⟫, ⟨2⟩ | 5 i | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n |
解析フェーズ
プログラム命令の番号 (例: 3 = "JZ") がレジスタ #2 (「プログラム命令レジスタ」PIR) に格納されたので、ステート マシンは IR が空になるまで番号を減らし続けます。
デクリメント前にIRが空だった場合、プログラム命令は0 = HALTとなり、マシンは「HALT」ルーチンにジャンプします。最初のデクリメント後、IRが空であれば命令はINCとなり、マシンは「inc_routine」命令にジャンプします。2回目のデクリメント後、空のIRはDECとなり、マシンは「dec_routine」にジャンプします。3回目のデクリメント後、IRは実際に空になり、「JZ_routine」ルーチンにジャンプします。もしIRに予期しない数値がまだ残っていた場合、マシンはエラーを検出し、例えばHALTする可能性があります。
| パソコン | IR | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 穴番号→ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| プログラム、パラメータ → | 5 | JZ | 18 | 15 | 12月 | 18 | 株式会社 | 19 | JZ | 15 | 5 | H | n | ||||||||
| エンコードされたプログラム → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| ステートマシン命令 ↓ | |||||||||||||||||||||
| CPY ⟪1⟫, ⟨2⟩ | 5 i | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||||
| JZ 2、停止 | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||||
| 3 | 12月2日 | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 4 | JZ 2、inc_routine: | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 5 | 12月2日 | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 6 | JZ 2、dec_routine | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 7 | 12月2日 | 5 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 8 | JZ 2、JZ_ルーチン | 5 | 0 ! | ||||||||||||||||||
| — | 停止: | 停止 | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| — | inc_routine: | 等 | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| — | dec_routine: | 等 | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 9 | JZ_ルーチン: | 等 | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n |
実行フェーズ、JZ_routine
これでステートマシンはどのプログラム命令を実行すべきかを認識し、実際に「JZ_routine」命令シーケンスにジャンプしました。JZ命令には2つのオペランドがあります。(i) テストするレジスタの番号、(ii) テストが成功した場合（ホールが空の場合）に移動するアドレスです。
(i) オペランドフェッチ — どのレジスタが空かテストするか？ : フェッチフェーズと同様に、有限ステートマシンはPCが指すレジスタ（つまり、ホール#6）の内容をプログラム命令レジスタPIR #2に移動します。次に、レジスタ#2の内容を使用して、ゼロかどうかをテストするレジスタ（つまり、レジスタ#18）を参照します。ホール#18には数値「n」が含まれています。テストを行うために、ステートマシンはPIRの内容を使用して、レジスタ#18の内容を予備レジスタ#3に間接的にコピーします。したがって、(ia) レジスタ#18が空の場合、(ib) レジスタ#18が空でない場合の2つの状況が考えられます。
(ia): レジスタ #3 が空の場合、ステートマシンは (ii) 第 2 オペランド フェッチ (ジャンプ先アドレスをフェッチ) にジャンプします。
(ib): レジスタ#3が空でない場合、ステートマシンは(ii)第2オペランドのフェッチをスキップできます。PCを2倍にインクリメントした後、無条件に命令フェッチフェーズに戻り、プログラム命令#8 (DEC)をフェッチします。
(ii) オペランドフェッチ — ジャンプ先アドレス。レジスタ#3が空の場合、ステートマシンはPCを使用して、それが指し示すレジスタ（#8）の内容を間接的に自身にコピーします。この時点でPCはジャンプ先アドレス15を保持しています。その後、ステートマシンは無条件に命令フェッチフェーズに戻り、プログラム命令#15（HALT）をフェッチします。
| パソコン | IR | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 穴番号→ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| プログラム、パラメータ → | 5 | JZ | 18 | 15 | 12月 | 18 | 株式会社 | 19 | JZ | 15 | 5 | H | n | ||||||||
| エンコードされたプログラム → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| ステップ | ステートマシン命令 ↓ | ||||||||||||||||||||
| 9 | JZ_ルーチン | インク1 | [6] | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 10 | CPY ⟪1⟫, ⟨2⟩ | 6 i | [18] | 3 | [18] | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 11 | テストホール: | CPY ⟪2⟫, ⟨3⟩ | 6 | 18 私 | [名詞] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | [名詞] | ||||
| 12 | テストホール: | JZ 3、ジャンプ | 6 | 18 私 | [名詞] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| n | n | ||||||||||||||||||||
| 13 | ジャンプなし: | インク1 | [7] | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 14 | インク1 | [8] | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 15 | J フェッチ_instr | 8 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 1 | フェッチ_instr: | CPY ⟪1⟫, ⟨2⟩ | 8 i | [2] | n | 3 | 18 | 15 | [2] | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 2 | 解析: | 等 | |||||||||||||||||||
| 13 | ジャンプ： | インク1 | [7] | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 14 | CPY ⟪1⟫, ⟨1⟩ | [15] | 18 | n | 3 | 18 | [15] | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 15 | J フェッチ_instr | 15 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 1 | フェッチ_instr: | CPY ⟪1⟫, ⟨2⟩ | 15 i | [0] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | [0] | n | ||||
| 2 | 解析: | 等 |
実行フェーズ INC、DEC
以下は、プログラム命令 INC h、DEC h の RAM のステートマシン解釈を完了し、RAM が RASP を「偽装」する方法のデモンストレーションを完了します。
- ターゲットプログラム命令セット: { INC h; DEC h; JZ h,xxx, HALT }
間接ステート マシン命令 INCi および DECi がない場合、INC および DECプログラム命令を実行するには、ステート マシンは間接コピーを使用して、指示されたレジスタの内容を予備レジスタ #3 に取得し、それを DEC または INC し、次に間接コピーを使用して指示されたレジスタにそれを送り返す必要があります。
| パソコン | IR | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 穴番号→ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| プログラム、パラメータ → | 5 | JZ | 18 | 15 | 12月 | 18 | 株式会社 | 19 | JZ | 15 | 5 | H | n | ||||||||
| エンコードされたプログラム → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| ステートマシン命令 ↓ | |||||||||||||||||||||
| 15 | J フェッチ_instr | 8 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 16 | フェッチ_instr: | CPY ⟪1⟫, ⟨2⟩ | 8 i | [2] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 17 | 解析: | JZ 2、停止 | 8 | 2 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 18 | 12月2日 | 8 | [1] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 19 | JZ 2、inc_routine: | 8 | 1 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 20 | 12月2日 | 8 | [0] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 21 | JZ 2、dec_routine: | 8 | 0 ! | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 22 | dec_routine: | インク1 | 9 | 0 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 23 | CPY ⟪1⟫, ⟨2⟩ | 9 i | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 24 | CPY ⟪2⟫, ⟨3⟩ | 9 | 18 私 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 25 | JZ 3,*+2 | 9 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 26 | 12月3日 | 9 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 27 | CPY ⟨3⟩、⟪2⟫ | 9 | 18 私 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 28 | インク1 | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 29 | J フェッチ_instr | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 30 | フェッチ_instr: | CPY ⟪1⟫, ⟨2⟩ | 10 i | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 31 | 解析: | JZ 2、停止 | 10 | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 32 | 12月2日 | 10 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 33 | JZ 2、inc_routine: | 10 | 0 ! | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 34 | inc_routine: | インク1 | 11 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 35 | CPY ⟪1⟫, ⟨2⟩ | 11 i | 19 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 36 | CPY ⟪2⟫, ⟨3⟩ | 11 | 19 私 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 37 | インク3 | 11 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 38 | CPY ⟨3⟩、⟪2⟫ | 11 | 19 私 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 1 | ||||
| 39 | インク1 | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 40 | J フェッチ_instr | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 41 | フェッチ_instr: | 等 | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 |
代替命令: このデモンストレーションでは 4 つの命令のみで構成される基本的な RASP が実現されましたが、読者は「ADD ⟨h⟩」や「MULT ⟨h a ⟩ ,⟪h b >」などの追加命令がどのように実行されるかを想像できるかもしれません。
自己修正型RASPプログラム
RAMがRASPとして機能する場合、新たな機能が得られます。RAMとは異なり、RASPはプログラム命令を自己修正する能力を備えています（ステートマシン命令は固定されており、マシンによる修正は不可能です）。Cook-Reckhow (1971) (p. 75) はRASPモデルの説明の中でこの点について言及しており、Hartmanis (1971) (pp. 239ff) も同様です。
この概念の初期の説明は、ゴールドスタイン・フォン・ノイマン（1946）に見られます。
- 「与えられた順序に数値を代入できる命令（インストラクション）が必要です。このような命令によって、計算の結果を、その計算または別の計算を制御する命令に導入することができます」（p. 93）
こうした能力により、次のことが可能になります。
- サブルーチン- 呼び出しルーチン（またはサブルーチン）は、戻りアドレス「return_address」をサブルーチンの最後のコマンドに格納します（例：「JMP return_address」）。
- いわゆるジャンプテーブル
- 自己変更コード
CookとReckhowによるRASPプログラム命令セット（1973年）
影響力のある論文の中で、Stephen A. Cook 氏と Robert A. Reckhow 氏は、RASP の独自のバージョンを定義しています。
- 「ここで説明するランダム アクセス ストアード プログラム マシン (RASP) は、Hartmanis [1971] が説明した RASP に似ています」(p. 74)。
その目的は、複雑性分析の理論で使用するための RAM、RASP、マルチテープ チューリング マシンなど、さまざまなモデルの実行時間を比較することでした。
彼らのRASPモデルの顕著な特徴は、間接的なプログラム命令が存在しないことです（75ページの議論を参照）。これは、プログラム自身に自己修正を要求することで実現されています。つまり、必要に応じて、命令は特定の命令の「パラメータ」（彼らの言葉、つまり「オペランド」）を変更できます。彼らは、各「命令」が連続する2つのレジスタを使用するようにモデルを設計しました。1つは「オペレーションコード」（彼らの言葉）用、もう1つは「アドレスまたは整数定数」であるパラメータ用です。
RASPのレジスタは容量も数も無制限です。同様に、アキュムレータACと命令カウンタICも無制限です。命令セットは以下のとおりです。
| 手術 | ニモニック | オペコード | 説明 |
|---|---|---|---|
| 負荷定数 | LOD、k | 1 | 定数kをアキュムレータに入れる |
| 追加 | 追加、j | 2 | レジスタjの内容をアキュムレータに加算する |
| 減算する | サブ、j | 3 | レジスタjの内容をアキュムレータから減算する |
| 店 | STO、j | 4 | アキュムレータの内容をレジスタjにコピーする |
| 正の累算器の分岐 | BPA、xxx | 5 | アキュムレータの内容が0より大きい場合はxxxへジャンプし、そうでなければ次の命令へジャンプする |
| 読む | RD、j | 6 | レジスタjへの次の入力 |
| 印刷 | PRI、j | 7 | レジスタjの内容を出力する |
| 停止する | HLT | その他の - または + 整数 | 停止 |
参考文献
RAMマシンとRASPマシンは、同じ記事で一緒に紹介されることがよくあります。これらはランダムアクセスマシンから転載されたものであり、いくつかの例外を除き、レジスタマシンの参照と同じです。
- ジョージ・ブーロス、ジョン・P・バージェス、リチャード・ジェフリー（2002年）『計算可能性と論理：第4版』、ケンブリッジ大学出版局、ケンブリッジ、イギリス。ブーロス＝ジェフリーの原著はバージェスによって大幅に改訂され、入門書よりも高度な内容となっている。「アバカスマシン」モデルは第5章「アバカス計算可能性」で詳細に展開されている。これは、チューリングマシン（ブーロスのオリジナルの4要素形式のまま）と2つの再帰モデルという、3つのモデルのうちの1つであり、広範囲に扱われ比較されている。
- アーサー・バークス、ハーマン・ゴールドスタイン、ジョン・フォン・ノイマン（1946年）「電子計算機の論理設計に関する予備的考察」 、ゴードン・ベルとアレン・ニューウェル（1971年）「コンピュータ構造：解説と例」92頁以降に再録、マグロウヒル・ブック・カンパニー、ニューヨーク。ISBN 0-07-004357-4 。
- Stephen A. Cook、Robert A. Reckhow (1972)、「時間制限付きランダムアクセスマシン」、Journal of Computer Systems Science 7 (1973)、354–375。
- Martin Davis (1958)、「Computability & Unsolvability」、McGraw-Hill Book Company、Inc.、ニューヨーク。
- Calvin Elgot とAbraham Robinson (1964)、「ランダムアクセス ストアド プログラム マシン、プログラミング言語へのアプローチ」、Journal of the Association for Computing Machinery、Vol. 11、No. 4 (1964 年 10 月)、pp. 365–399。
- J. ハートマニス(1971)、「ランダムアクセスストアードプログラムマシンの計算複雑性」、数学システム理論 5、3 (1971) pp. 232–245。
- ジョン・ホップクロフト、ジェフリー・ウルマン(1979). 『オートマトン理論、言語、計算入門』第1版、Reading Mass: Addison-Wesley. ISBN 0-201-02988-X「言語」の機械解釈、NP完全性などの問題を中心とした難しい本です。
- Stephen Kleene (1952)、『メタ数学入門』、North-Holland Publishing Company、アムステルダム、オランダ。ISBN 0-7204-2103-9。
- ドナルド・クヌース（1968年）『コンピュータプログラミングの技法』第2版、1973年、アディソン・ウェスレー社、マサチューセッツ州リーディング。462～463ページを参照。クヌースは「リンク構造を扱う新しい種類の抽象機械、あるいは『オートマトン』」と定義している。
- ヨアヒム・ランベック（1961年、1961年6月15日受理）「無限アバカスのプログラミング方法」、Mathematical Bulletin、第4巻第3号、1961年9月、295～302ページ。付録IIにおいて、ランベックは「プログラム」の「正式な定義」を提案している。彼はメルザック（1961年）とクリーネ（1952年）の「メタ数学入門」を参照している。
- ZAメルザック（1961年、1961年5月15日受理）「計算可能性と計算への非公式算術的アプローチ」、カナダ数学速報、第4巻第3号、1961年9月、279-293ページ。メルザックは参考文献を挙げていないが、「ベル電話研究所のR.ハミング博士、D.マキロイ博士、V.ヴィソツキー博士、およびオックスフォード大学のH.ワン博士との会話の恩恵」を認めている。
- マーヴィン・ミンスキー(1961). 「ポストの『タグ』問題の再帰的不解法とチューリング機械理論におけるその他の話題」Annals of Mathematics . 74 (3): 437– 455. doi :10.2307/1970290. JSTOR 1970290.
- マービン・ミンスキー（1967年）『計算：有限機械と無限機械』（第1版）イングルウッド・クリフス、ニュージャージー州：プレンティス・ホール社ISBN 0-13-165449-7。特に第11章「デジタルコンピュータに類似したモデル」と第14章「計算可能性のための非常に単純な基底」を参照してください。前章では「プログラムマシン」を定義し、後章では「2つのレジスタを持つ汎用プログラムマシン」や「1つのレジスタを持つ…」などについて説明しています。
- John C. ShepherdsonとHE Sturgis (1961)は、1961年12月にJournal of the Association for Computing Machinery (JACM) 10:217-255, 1963に「再帰関数の計算可能性」という論文を受理しました。これは非常に貴重な参考論文です。付録Aでは、著者らは「4.1で使用される命令の最小性：類似システムとの比較」という項目で、他の4つの論文を引用しています。
- Kaphengst、Heinz、Eine Abstrakte Programmgesteuerte Rechenmaschine'、Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959)、366-379。
- Ershov, AP 「演算子アルゴリズムについて」、（ロシア語）Dok. Akad. Nauk 122 (1958), 967-970. 英訳、Automat. Express 1 (1959), 20-23.
- Péter、Rózsa Graphschemata und rekursive Funktionen、Dialectica 12 (1958)、373。
- ヘルメス、ハンスディ ユニバーサル プログラム、Rechenmaschinen。数学-物理学Semsterberichte (ゲッティンゲン) 4 (1954)、42-53。
- Arnold Schönhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. ここでSchōnhageは、彼のSMMが「後継のRAM」（ランダムアクセスマシン）などと同等であることを示しています。Storage Modification Machines , Theoretical Computer Science (1979), pp. 36–37
- Peter van Emde Boas著『Machine Models and Simulations』 pp. 3–66、Jan van Leeuwen編『Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity』、MIT PRESS/Elsevier、1990年、ISBN 0-444-88071-2（A巻）。QA 76.H279 1990。
- ファン・エムデ・ボアスによるSMMの扱いは32～35ページに掲載されています。この扱いはショーンハーゲ（1980）の扱いを明確化しており、ショーンハーゲの扱いをほぼ踏襲しつつも、若干拡張しています。効果的な理解のためには、両方の参考文献が必要になるかもしれません。
- Hao Wang (1957), 「チューリングの計算機理論の変種」 , JACM (Journal of the Association for Computing Machinery) 4; 63–92. 1954年6月23日から25日にかけて開催された同協会の会議で発表された。
