ランダムアクセスプログラム格納マシン

理論計算機科学において、ランダムアクセス ストアード プログラム(RASP) マシン モデルは、アルゴリズム開発およびアルゴリズム複雑性理論の目的で使用される抽象マシンです。

RASP はランダム アクセス マシン(RAM) モデルであり、RAM とは異なり、プログラムが入力とともに「レジスタ」に格納されます。レジスタは無制限 (容量が無限) です。レジスタの数が有限かどうかはモデルによって異なります。したがって、RASP と RAM の関係は、ユニバーサル チューリング マシンとチューリング マシンの関係と同じです。RASP はフォン ノイマン アーキテクチャの例であり、RAM はハーバード アーキテクチャの例です。

RASP は、すべての抽象モデルの中で、コンピュータの一般的な概念に最も近いものです。しかし、実際のコンピュータとは異なり、RASP モデルは通常、非常に単純な命令セットを持ち、CISCやRISCプロセッサの命令セットよりも大幅に簡略化され、最も単純な算術演算、レジスタ間の「移動」、および「テスト/ジャンプ」命令になっています。一部のモデルには、アキュムレータなどの追加のレジスタがいくつかあります。

レジスタ マシン、RAM、およびポインタ マシンとともに、RASP は 4 つの一般的なシーケンシャル マシン モデルを構成します。これらは、「並列」モデル (例:並列ランダム アクセス マシン) と区別するためにこのように呼ばれます [cf. van Emde Boas (1990)]。

RASP の簡単な説明:

RASP は、ランダム アクセス マシンRAM シャーシ上に構築されたユニバーサル チューリング マシン(UTM)です。

読者は、UTM が「ユニバーサル」な有限状態命令表を持つチューリング マシンであり、テープ上に書き込まれた任意の整形式の「プログラム」をチューリング 5 組の文字列として解釈できるため、その普遍性があることを覚えているでしょう。従来の UTM モデルでは、テープ上にチューリング 5 組が見つかるものと想定していますが、チューリング マシンがそれらを見つけると想定している限り、つまり有限状態表がそれらを解釈して目的のアクションに変換できる限り、考えられるあらゆるプログラム セットをそこに置くことができます。プログラムとともに、テープ上には入力データ/パラメータ/数値 (通常はプログラムの右側) が印刷され、最終的には出力データ/数値 (通常は両方の右側、または入力と混在、または入力を置き換えて) が印刷されます。「ユーザー」はチューリング マシンのヘッドを最初の命令の上に配置する必要があります。また、入力はテープ上のプログラムと有限状態マシンの命令表の両方に適した指定された場所と形式で配置する必要があります。

RASP はこの構造を模倣し、「プログラム」と「データ」をホール (レジスタ) に配置します。ただし、UTM とは異なり、RASP は、条件付きテストによって命令が他の場所に送られない限り、命令を順番に「フェッチ」します。

混乱のポイント: 2 つの命令セット: UTM とは異なり、RASP モデルには 2 つの命令セット (命令の状態マシン テーブル (「インタープリター」) とホール内の「プログラム」) があります。2 つのセットは、同じセットから取得する必要はありません。

次のプログラムの例では、レジスタ (ホール) #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 マシンで使用できるプログラム命令は、例を短くするために単純なセットになります。

例を簡単にするために、 RAM-as-RASP のステート マシンに、同じセットから抽出された基本命令を装備しますが、2 つの間接コピー命令が追加されます。

RAM ステートマシン命令:

{ INC h; DEC h; JZ h,xxx; CPY ⟪h _a ⟫, ⟨h _a ⟩ ; CPY ⟨h _a ⟩ ,⟪h _a ⟫ }

RASP マシンのステート マシンがレジスタ内のプログラムを解釈するとき、ステート マシンは具体的に何を行うのでしょうか。感嘆符 (!) を含む列には、ステート マシンがプログラムを「解釈」 (アクションに変換) するときのアクションが時系列でリストされます。

伝統的に、ステートマシンのアクションは、フェッチと実行と呼ばれる 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の「操作コード」(「opcode」) の数値 3 が含まれていることに注目してください。

プログラム命令の番号 (例: 3 = "JZ") がレジスタ #2 ("プログラム命令レジスタ" PIR) にあるので、ステート マシンは IR が空になるまで番号を減らし続けます。

減分前に IR が空だった場合、プログラム命令は 0 = HALT となり、マシンは「HALT」ルーチンにジャンプします。最初の減分後、ホールが空であれば命令は INC となり、マシンは命令「inc_routine」にジャンプします。2 回目の減分後、空の IR は DEC を表し、マシンは「dec_routine」にジャンプします。3 回目の減分後、IR は実際に空になり、これにより「JZ_routine」ルーチンにジャンプします。予期しない数字が IR にまだ残っている場合、マシンはエラーを検出し、HALT する可能性があります (例)。

これで、ステート マシンはどのプログラム命令を実行するかを認識します。実際、ステート マシンは「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)をフェッチします。

以下は、プログラム命令 INC h、DEC h の RAM のステート マシン解釈を完了し、RAM が RASP を「偽装」する方法のデモンストレーションを完了します。

ターゲットプログラム命令セット: { INC h; DEC h; JZ h,xxx, HALT }

間接ステートマシン命令 INCi および DECi がない場合、INC および DECプログラム命令を実行するには、ステートマシンは間接コピーを使用して、指示されたレジスタの内容を予備レジスタ #3 に取得し、それを DEC または INC してから、間接コピーを使用して指示されたレジスタに送り返す必要があります。

代替命令: このデモンストレーションでは 4 つの命令のみで構成される基本的な RASP が実現されましたが、読者は「ADD ⟨h⟩」や「MULT ⟨h _a ⟩ ,⟪h _b >」などの追加命令がどのように実行されるかを想像できるかもしれません。

RAM が RASP として動作する場合、新しい機能が得られます。RAM とは異なり、RASP はプログラム命令を自己修正する機能を備えています (ステート マシン命令は固定されており、マシンによって変更できません)。Cook-Reckhow (1971) (p. 75) は、RASP モデルの説明でこれについてコメントしています。Hartmanis (1971) (pp. 239ff) も同様です。

この概念の初期の説明は、ゴールドスタイン・フォン・ノイマン（1946）に見られます。

「数値を特定の順序に置き換えることができる命令（命令）が必要です...このような命令によって、計算の結果を、その計算または別の計算を管理する命令に導入することができます」（p. 93）

このような機能により、次のことが可能になります。

• サブルーチン- 呼び出しルーチン (またはサブルーチン)は、戻りアドレス「return_address」をサブルーチンの最後のコマンド (つまり「JMP return_address」) に格納します。
• いわゆるジャンプテーブル
• 自己修正コード

影響力のある論文の中で、Stephen A. Cook 氏と Robert A. Reckhow 氏は、RASP の独自のバージョンを定義しています。

「ここで説明するランダム アクセス ストアド プログラム マシン (RASP) は、Hartmanis [1971] が説明した RASP に似ています」(p. 74)。

その目的は、複雑性分析の理論で使用するための RAM、RASP、マルチテープ チューリング マシンなど、さまざまなモデルの実行時間を比較することでした。

彼らの RASP モデルの顕著な特徴は、間接的なプログラム命令が用意されていないことです (彼らの議論 p. 75 を参照)。これは、プログラム自体を変更することを要求することで実現されます。必要な場合は、命令が特定の命令の「パラメータ」(彼らの言葉、つまり「オペランド」) を変更できます。彼らは、各「命令」が 2 つの連続したレジスタを使用するようにモデルを設計しました。1 つは「操作コード」(彼らの言葉) 用、もう 1 つは「アドレスまたは整数定数」のパラメータ用です。

RASP のレジスタの容量と数は無制限です。同様に、アキュムレータ AC と命令カウンタ IC も無制限です。命令セットは次のとおりです。

多くの場合、RAM マシンと RASP マシンの両方が同じ記事で一緒に紹介されています。これらはRandom-access machineからコピーされたものであり、いくつかの例外を除いて、これらの参照はRegister machineのものと同じです。

• George Boolos、John P. Burgess、Richard Jeffrey (2002)、『Computability and Logic: Fourth Edition』、Cambridge University Press、ケンブリッジ、イギリス。Boolos-Jeffrey の原著は Burgess によって大幅に改訂され、入門書よりも高度な内容になっています。「Abacus machine」モデルは、第 5 章Abacus Computabilityで詳細に説明されています。これは、チューリング マシン (Boolos のオリジナルの 4 組形式のまま) と 2 つの再帰モデルの 3 つのモデルのうちの 1 つです。
• Arthur Burks、Herman Goldstine、John von Neumann (1946)、「電子計算機の論理設計に関する予備的考察」 、 Gordon BellおよびAllen Newell (1971)、「Computer Structures: Readings and Examples」、McGraw-Hill Book Company、ニューヨークに再録された pp. 92ff。ISBN 0-07-004357-4  。
• Stephen A. Cookと Robert A. Reckhow (1972)、「時間制限付きランダムアクセスマシン」、Journal of Computer Systems Science 7 (1973)、354–375。
• マーティン・デイビス（1958年）、「計算可能性と解決不可能性」、McGraw-Hill Book Company、Inc.、ニューヨーク。
• Calvin Elgot とAbraham Robinson (1964)、「ランダムアクセス・ストアード・プログラム・マシン、プログラミング言語へのアプローチ」、Journal of the Association for Computing Machinery、第 11 巻、第 4 号 (1964 年 10 月)、365 ～ 399 ページ。
• J. Hartmanis (1971)、「ランダムアクセスストアードプログラムマシンの計算複雑性」、数学システム理論 5、3 (1971) pp. 232–245。
• John Hopcroft、Jeffrey Ullman (1979)。『オートマトン理論、言語、計算入門』、第 1 版、Reading Mass: Addison-Wesley。ISBN 0-201-02988 -X。機械による「言語」の解釈、NP 完全性などの問題を中心に扱った難解な本。 
• Stephen Kleene (1952)、「Introduction to Metamathematics」、North-Holland Publishing Company、アムステルダム、オランダ。ISBN 0-7204-2103-9。 
• Donald Knuth (1968)、『The Art of Computer Programming』、第 2 版 1973、Addison-Wesley、マサチューセッツ州レディング。462 ～ 463 ページを参照。ここで彼は「リンクされた構造を扱う新しい種類の抽象マシン、つまり「オートマトン」」を定義しています。
• Joachim Lambek (1961、1961 年 6 月 15 日受領)、「How to Program an Infinite Abacus」、Mathematical Bulletin、第 4 巻、第 3 号、1961 年 9 月、295 ～ 302 ページ。付録 II で、Lambek は「プログラム」の「正式な定義」を提案しています。彼は Melzak (1961) と Kleene (1952) の「Introduction to Metamathematics」を参照しています。
• ZA Melzak (1961、1961 年 5 月 15 日受領)、「計算可能性と計算に対する非公式の算術的アプローチ」、Canadian Mathematical Bulletin、第 4 巻、第 3 号、1961 年 9 月、279 ～ 293 ページ。Melzak は参考文献を挙げていないが、「ベル電話研究所のR. Hamming博士、D. McIlroy 博士、V. Vyssotsky博士、およびオックスフォード大学のH. Wang博士との会話の恩恵」を認めている。
• マービン・ミンスキー( 1961)。 「ポストの「タグ」問題の再帰的解決不可能性およびチューリングマシン理論におけるその他の話題」。Annals of Mathematics。74 ( 3): 437–455。doi :10.2307/1970290。JSTOR  1970290。
• マービン・ミンスキー(1967)。『計算：有限機械と無限機械』（第 1 版）。ニュージャージー州エングルウッドクリフス：Prentice-Hall, Inc. 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 でComputability of Recursive Functionsという論文を受賞しました。これは非常に貴重な参考論文です。付録 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. 第 9 巻、第 3 号、1980 年 8 月。ここで Schōnhage は、SMM が「後継 RAM」(ランダム アクセス マシン) などと同等であることを示しています。Storage Modification Machines、Theoretical Computer Science (1979)、36 ～ 37 ページ
• Peter van Emde Boas、「マシンモデルとシミュレーション」、 pp. 3～66、Jan van Leeuwen編『理論計算機科学ハンドブック』、第 A 巻: アルゴリズムと複雑性、MIT PRESS/Elsevier、1990 年。ISBN 0-444-88071-2 (第 A 巻)。QA 76.H279 1990 年。 

van Emde Boas による SMM の扱いは 32 ～ 35 ページにあります。この扱いは Schōnhage 1980 を明確にするものであり、Schonhage の扱いにほぼ従っていますが、わずかに拡張されています。効果的な理解には両方の参考文献が必要になる場合があります。

• Hao Wang (1957)、「チューリングの計算機理論の変種」、JACM (Journal of the Association for Computing Machinery) 4; 63–92。1954 年 6 月 23 日から 25 日の協会会議で発表。