ランダムアクセスマシン

コンピュータサイエンスにおいて、ランダムアクセスマシン（RAMまたはRAマシン）は、レジスタマシンの一般クラスに属する抽象マシンを記述する計算モデルです。RAマシンはカウンターマシンと非常に似ていますが、レジスタの「間接アドレッシング」機能が追加されています。「レジスタ」は、任意のサイズの自然数を格納できるという追加機能を除けば、一般的なコンピュータのメインメモリと直感的に同等です。カウンターマシンと同様に、RAマシンはマシンの有限状態部分に実行命令を保持します（いわゆるハーバードアーキテクチャ）。

RAマシンは、データだけでなくプログラムもレジスタに格納する汎用チューリングマシンに相当するもので、ランダムアクセス・ストアード・プログラム・マシン、またはRASPマシンと呼ばれます。これはいわゆるフォン・ノイマン・アーキテクチャの一例であり、コンピュータの一般的な概念に最も近いものです。

チューリングマシンやカウンターマシンモデルと共に、RAマシンモデルとRASPマシンモデルは計算複雑性分析に用いられます。Van Emde Boas (1990) は、これら3つとポインタマシンを合わせて「シーケンシャルマシン」モデルと呼び、「並列ランダムアクセスマシン」モデルと区別しています。

非公式な説明

RA マシンは次の要素から構成されます。

「レジスタ」と呼ばれる無限の数のメモリ位置。各レジスタには自然数またはゼロのアドレスがあり、各レジスタには任意のサイズの自然数を1つだけ、またはゼロを1つだけ格納できます。
実行命令を含む命令テーブル（または単に「テーブル」）; 正確な命令セットは作成者によって異なります。一般的な命令には、インクリメント、デクリメント、ゼロクリア、コピー、条件付きジャンプ、停止などがあります。その他の命令は、命令セットの命令の組み合わせで作成できるため不要です。
「命令レジスタ」（IR）と呼ばれる特別なレジスタが1つあります。このレジスタは、命令テーブルで実行されている命令を指します。

似たような概念だがユーモラスな説明については、難解なプログラミング言語Brainfuckを参照してください。^{[ 1 ]}

モデルの紹介

ランダムアクセスマシン（RAM）の概念は、最も単純なモデル、いわゆるカウンタマシンモデルから始まります。しかし、2つの追加要素によって、カウンタマシンモデルからは離れています。1つ目は、間接アドレッシングの利便性によってマシンを拡張することです。2つ目は、1つまたは複数の補助（専用）レジスタ（最も一般的なものは「アキュムレータ」と呼ばれます）を追加することで、より従来的なアキュムレータベースのコンピュータに近いモデルへと進化させることです。

正式な定義

ランダムアクセスマシン（RAM）は、間接アドレッシングが追加された、マルチレジスタカウンタマシンと同一の抽象計算マシンモデルです。有限ステートマシンのテーブルから命令の裁量に応じて、マシンは「ターゲット」レジスタのアドレスを（i）命令自体から直接、または（ii）命令で指定された「ポインタ」レジスタの内容（番号、ラベルなど）から間接的に取得します。

定義によれば、レジスタとは、アドレス（自然数に相当する一意で識別可能な指定/位置指定）と内容（単一の自然数）の両方を持つ場所です。正確を期すため、レジスタ、その内容、そしてレジスタに対する操作を指定するために、Boolos-Burgess-Jeffrey (2002) の準形式記号を使用します。

[r]は「アドレスrのレジスタの内容」を意味します。ここでのラベル「r」は、自然数、文字（例：「A」）、または名前を格納できる「変数」です。
→「コピー/保管」または「置き換え」を意味しますが、ソースは破壊されません

例: [3] +1 → 3; は、「アドレス「3」のソースレジスタの内容に1を加えたものが、アドレス「3」の宛先レジスタに格納される」という意味です（ここではソースと宛先は同じ場所です）。[3]=37、つまりレジスタ3の内容が数値「37」の場合、37+1 = 38がレジスタ3に格納されます。

例: [3] → 5; は、「アドレス "3" のソースレジスタの内容を、アドレス "5" の宛先レジスタに格納する」という意味です。[3] = 38、つまりレジスタ3の内容が数値38の場合、この数値がレジスタ5に格納されます。この操作によってレジスタ3の内容は変更されないため、[3] は引き続き38となり、[5] と同じになります。

定義：直接命令とは、命令自体の中で、その内容が命令の対象となるソースレジスタまたはデスティネーションレジスタのアドレスを指定する命令です。定義：間接命令とは、「ポインタレジスタ」を指定する命令で、その内容は「ターゲット」レジスタのアドレスです。ターゲットレジスタは、ソースレジスタまたはデスティネーションレジスタのいずれかになります（各種COPY命令がその例です）。レジスタは、間接的に自身をアドレス指定できます。

標準/規則がないため、この記事では、命令内のパラメータとして「直接/間接」(略して「d/i」) を指定します。

例: COPY ( d , A, i , N ) は、d 命令自体からソースレジスタのアドレス (レジスタ "A") を直接取得しますが、 i ポインタレジスタ N から宛先アドレスを間接的に取得することを意味します。 [N]=3 とすると、レジスタ 3 が宛先となり、命令は次のように動作します: [A] → 3。

定義:ソースレジスタの内容は命令によって使用されます。ソースレジスタのアドレスは、(i) 命令によって直接指定するか、(ii) 命令によって指定されたポインタレジスタによって間接的に指定することができます。

定義:ポインタレジスタの内容は、「ターゲット」レジスタの アドレスです。

定義:ポインタレジスタの内容はターゲットレジスタを指します。「ターゲット」はソースレジスタまたは宛先レジスタのいずれかになります。

定義：デスティネーションレジスタは、命令が結果を格納するレジスタです。ソースレジスタのアドレスは、(i) 命令によって直接指定するか、(ii) 命令によって指定されたポインタレジスタによって間接的に指定できます。ソースレジスタとデスティネーションレジスタは、同じレジスタでも可能です。

復習：カウンターマシンモデル

メルザック（1961）は、カウンタマシンを分かりやすく視覚化しています。その「レジスタ」は地面に掘られた穴で、その穴には小石が詰められています。命令に従って、「コンピュータ」（人または機械）はこれらの穴に小石を1つずつ入れたり、1つずつ減らしたりします（インクリメント）。必要に応じて、無限の供給源から小石が追加され、余った小石はそこに戻ります。穴が小石を収容するには小さすぎる場合、「コンピュータ」は穴を大きく掘ります。

ミンスキー (1961) とホップクロフト＝ウルマン (1979) (p. 171) は、左端テープを「レジスタ」の数だけ持つマルチテープ・チューリングマシンの視覚化を提示している。各テープの長さは右方向に無限大で、左端のマス目はマークで示され、それ以外は空白である。テープの「ヘッド」から左端までの距離は、テープのマス目数で測定され、「レジスタ」内の自然数を表す。マス目の数を減算するにはテープヘッドを左に移動し、増分するには右に移動します。テープにマークを印刷したり消去したりする必要はありません。条件付き命令は、「マーク付きジャンプ命令」で左端のマークをテストし、ヘッドが左端にあるかどうかを確認することだけです。

次の命令の「ニーモニック」（例：「CLR (r)」）は任意であり、標準は存在しません。

レジスタマシンは、有限状態マシンの外部メモリとして、「レジスタ」と呼ばれる、容量が無制限で、かつ個別にラベル付けされた「レジスタ」と呼ばれる位置の、無制限（脚注参照：可算かつ無制限）な集合を持ちます。これらのレジスタは、自然数（0と正の整数）のみを保持します。有限状態マシンのテーブルにある一連の命令に従って、いくつかの（例えば2種類の）基本演算がこれらの「レジスタ」の内容に対して実行されます。最後に、IF-THEN-ELSE形式の条件式を使用して、1つまたは2つのレジスタの内容をテストし、有限状態マシンをデフォルトの命令シーケンスから「分岐/ジャンプ」させることができます。

基本モデル1 :ミンスキー(1961)の視覚化とランベック(1961)に最も近いモデル:

{ レジスタ r の内容をインクリメントし、レジスタ r の内容をデクリメントし、レジスタ r の内容がゼロの場合は命令 I _{zにジャンプし、}そうでない場合は次の命令に進みます }:

命令	ニモニック	レジスタ「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

基本モデル 2 : 「後継」モデル (ペアノ公理の後継関数にちなんで名付けられました):

{ レジスタ r の内容をインクリメントし、レジスタ r の内容をクリアし、レジスタ r _{jの内容がレジスタ r}_kの内容と等しい場合は命令I _{zにジャンプし、}そうでない場合は次の命令に進みます }

命令	ニモニック	レジスタ「r」に対するアクション	有限ステートマシンの命令レジスタ（IR）に対するアクション
クリア	CLR ( r )	0 → r	[IR] + 1 → IR
インクリメント	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
等しい場合はジャンプ	JE (r1, r2, z)	なし	[r1] = [r2] の場合、z → IR、そうでない場合、[IR] + 1 → IR
停止	H	なし	[IR] → IR

基本モデル3 : Elgot-Robinson (1964)が有界および非有界RASPの調査に使用したモデル。CLEARの代わりにCOPYを使用した「後継」モデル。

{ レジスタ r の内容をインクリメントし、レジスタ r _{jの内容をレジスタ r}_kにコピーします。レジスタ r _{jの内容がレジスタ r}_kの内容と等しい場合は命令 I _{zにジャンプし}、等しくない場合は次の命令に進みます }

命令	ニモニック	レジスタ「r」に対するアクション	有限ステートマシンの命令レジスタ（IR）に対するアクション
コピー	コピー (r1, r2)	[r1] → r2	[IR] + 1 → IR
インクリメント	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
等しい場合はジャンプ	JE (r1, r2, z)	なし	[r1] = [r2] の場合、z → IR、そうでない場合、[IR] + 1 → IR
停止	H	なし	[IR] → IR

基本セットから「便利な命令」を作成する

上記の3つの基本セット1、2、または3は、あるセットの命令を別のセットの命令を使用して作成できるという点で同等です（興味深い演習：ミンスキー（1967）からのヒント – 数値0を格納するために、予約レジスタを宣言します。例えば、それを「0」（または「ゼロ」のZ、または「消去」のE）と呼びます）。モデルの選択は、著者がデモンストレーションや証明などでどのモデルが最も使いやすいかによって異なります。

さらに、基本命令セット1、2、または3から、任意の基本再帰関数を作成できます（Minsky ( 1967)、Boolos-Burgess-Jeffrey (2002)を参照）。（網を広げて全体および部分μ再帰関数を捉える方法については、間接アドレッシングの文脈で説明します）。しかし、基本再帰関数の構築は、命令セットが非常に原始的（小さい）ため困難です。1つの解決策は、特定の命令セットを別の命令セットの「便利な命令」で拡張することです。

これらは従来の意味でのサブルーチンではなく、ベースセットから作成され、ニーモニックが付与された命令ブロックです。正式には、これらのブロックを使用するには、(i) ベース命令に相当するものに「拡張」するか（一時レジスタまたは「補助」レジスタの使用が必要となるため、モデルではこれを考慮する必要があります）、(ii) 命令を「組み込んだ」状態でマシン/モデルを設計する必要があります。

例: ベースセット1。CLR(r)を作成するには、レジスタrをゼロまでカウントダウンする命令ブロックを使用します。上記のヒントの使用方法に注意してください。

CLR (r) =_等価
ループ: JZ (r,終了)

12月（r）
JZ (0,ループ)

出口：など

繰り返しますが、これらはすべて便宜上のものであり、モデルの本来の力を高めるものではありません。

たとえば、最も拡張されたセットには、3 つのセットの各固有命令と、無条件ジャンプ J (z) が含まれます。

{ CLR (r), DEC (r), INC (r), CPY ( r _s , r _d ), JZ (r, z), JE ( r _j , _rk , z ), J(z) }

ほとんどの著者は、条件付きジャンプのいずれかを選択します。たとえば、Shepherdson-Sturgis (1963) は、上記のセットから JE を除いたものを使用します (完全に正確にするために、JZ の代わりに JNZ (ゼロ でない場合ジャンプ) を使用します。これもまた、便利な命令の 1 つです)。

「間接的な」操作

間接アドレッシングの例

私たちの日常生活において、「間接的な操作」という概念は珍しいことではありません。

例: 宝探し。

「Tom_&_Becky's_cave_in_pirate_chest」という場所に、「宝物」への道しるべとなる地図があります。

（１）「トムとベッキーの洞窟」に行き、木箱を見つけるまで掘り進みます

（２）箱の中には宝物の場所を示す地図が入っている：「under_Thatcher's_front_porch」

(3) 私たちは「under_Thatcher's_front_porch」の場所に行き、コンクリートを削岩機で削り取り、「宝物」である錆びたドアノブの入った袋を発見します。

間接参照は、「Tom_&_Becky's_cave...」の海賊の宝箱として識別される場所を指定します。この場所は、他の場所 (それ自体を含む) へのポインタとして機能します。その内容 (宝の地図) は、実際のアクションが発生しているターゲットの場所「under_Thatcher's_front_porch」の「アドレス」を提供します。

間接的な操作が必要な理由：対機械モデルの2つの大きな問題

以下では、これらのモデルが抽象モデルであり、物理的に現実のものと2つの根本的な違いがあることを覚えておく必要があります。それは、無限の数のレジスタと、それぞれ無限の容量を持つレジスタです。この問題は、カウンターマシンモデルを用いてチューリング等価なRASPを構築し、任意の部分μ再帰関数を計算しようとする際に最も顕著に現れます。

メルザック (1961) は、「穴と小石」モデルに間接参照を追加し、「計算された goto」によってモデルを自己修正できるようにし、その使用例を2つ示しています（「d のスケールにおける小数表現」と「大きさによるソート」。これらの例が、モデルがチューリング等価であることの証明に使用されているかどうかは不明です。「プログラム自体は読者の演習として残されている」(p. 292) ためです）。ミンスキー (1961, 1967) は、適切な（しかし使いにくい）ゲーデル数エンコーディングを用いることで、レジスタモデルがチューリング等価となるために間接参照は不要であることを証明しました。ただし、少なくとも1つの無制限のレジスタは必要でした。後述するように、ミンスキー (1967) は RASP の問題について示唆していますが、解決策は示していません。エルゴットとロビンソン (1964) は、間接参照機能を持たない彼らのRASPモデルP ₀ は、自身の命令を変更する機能を持たない場合、すべての「再帰的逐次関数」（任意の長さのパラメータを持つ関数）を計算できないが、自身の命令を変更する機能を持つ場合はゲーデル数を介して計算できることを証明した (p. 395-397; 特に図2とp. 395の脚注)。一方、彼らのRASPモデルP' ₀は「インデックスレジスタ」（間接参照）を備えており、すべての「部分的再帰的逐次関数」（μ再帰関数）を計算できる (p. 397-398)。

クックとレックハウ（1973）は、これを最も簡潔に述べています。

間接命令は、入力の変化に応じて固定プログラムが無制限の数のレジスタにアクセスするために必要です。」（p. 73）

レジスタの無制限な容量とステートマシン命令の有限な容量：マシンのいわゆる有限状態部分は、アルゴリズムの通常の定義によれば、「状態」（命令）の数と命令のサイズ（シンボル／符号を保持する容量）の両方において非常に有限であると考えられます。では、ステートマシンはどのようにして任意の大きさの定数をレジスタに直接移動するのでしょうか？例えば、MOVE (k, r)（定数kをレジスタrに移動）のように。巨大な定数が必要な場合は、レジスタ自体から定数を作成するか、ステートマシンが有限数の命令（例えば、INCとDECを用いた乗算と加算のサブルーチン）を用いて定数を作成する必要があります（ただし、これらのサブルーチンは準無限ではありません）。

定数kは、CLR(r)に続いてINC(r)をk回繰り返すことで生成されることがあります。例えば、定数k=3をレジスタrに格納する場合（つまり3→r）、命令の末尾には[r]=3：CLR(r), INC(r), INC(r), INC(r)が記述されます。このトリックはKleene (1952) p. 223で言及されています。問題は、生成される数が有限ステートマシンで利用可能な命令の数を超えてしまう場合に発生します。有限ステートマシンで利用可能な命令の数よりも常に大きな定数が存在するからです。

無制限のレジスタ数と制限されたステートマシン命令：これは最初の問題よりも深刻です。特に、この問題は、いわゆるRASP、つまり有限ステートマシンを用いてレジスタに格納された「命令プログラム」を解釈する「ユニバーサルマシン」（詳しくはユニバーサルチューリングマシンを参照）を構築しようとするときに発生します。つまり、今日ではフォン・ノイマン・アーキテクチャと呼ばれるコンピュータを構築しているのです。

カウンタマシンの有限ステートマシンは、レジスタをその名前/番号で明示的に（直接）呼び出す必要があることに注意してください。INC (65,356) は、レジスタ番号「65,365」を明示的に呼び出します。レジスタの数が有限ステートマシンのアドレス指定能力を超える場合、境界外のレジスタにはアクセスできなくなります。例えば、有限ステートマシンが65,536 = 2 ^{16 個の}レジスタにしかアクセスできない場合、65,537番目のレジスタにはどのようにしてアクセスできるのでしょうか？

では、有限ステートマシンの境界を超えてレジスタをアドレス指定するにはどうすればよいでしょうか。一つの方法は、プログラム命令（レジスタに格納される命令）を複数のコマンドを含むように変更することです。しかし、命令のサイズが（潜在的に）無制限でない限り、これも限界に達します。そこで、すべてのプログラム命令をエンコードした「超命令」（非常に大きな数値）を一つだけ使用してみてはいかがでしょうか。ミンスキーはこのように問題を解決しますが、彼が用いるゲーデル数列はモデルにとって大きな不都合を招き、その結果は私たちが直感的に理解している「ストアードプログラムコンピュータ」とは全く異なるものになります。

エルゴットとロビンソン（1964）は、「有限に決定された」RASPに関して同様の結論に達している。確かにRASPは無制限の数のレジスタにアクセス可能（例えば、レジスタから命令をフェッチするなど）だが、それはRASPがプログラム命令の「自己修正」を許可し、「データ」をゲーデル数で符号化している場合に限られる（図2、396ページ）。

ミンスキー（1967）は、RPT（繰り返し）命令を用いたよりコンピュータ的なモデルの文脈において、この問題の解決策を提示している（214ページ、259ページ参照）が、明確な解決策は提示していない。彼は次のように主張している。

「一般的に、RPT 操作はマシンの有限状態部分における命令にはなり得ません。これにより、コンピューターの有限部分で許可されている特定の量のストレージが使い果たされる可能性があります (これは RAM モデルの彼の名前です)。RPT 操作には、独自の無限のレジスタが必要です。」(p. 214)。

彼は、 CLR(r)およびINC(r)と組み合わせることで任意の原始再帰関数を計算できる有界RPTを提案しています。また、上で引用したμ演算子の役割を果たす非有界RPTも提案しています。これはCLR(r)およびINC(r)と組み合わせることでμ再帰関数を計算できます。しかし、彼は「間接参照」やRAMモデルそのものについては議論していません。

ハートマニス (1971) の文献から、クック (1970 年、カリフォルニア大学バークレー校在学時の講義ノート) が間接アドレッシングの概念を確固たるものにしたことが分かります。これは、クックとレックハウ (1973) の論文でより明確になります。クックはレックハウの修士論文指導教官でした。ハートマニスのモデルはメルザック (1961) のモデルと非常に似ており、2つまたは3つのレジスタによる加算と減算、および2つのパラメータコピーを使用します。クックとレックハウのモデルでは、アキュムレータ「AC」を使用することで、パラメータ（プログラム命令で呼び出されるレジスタ）の数を1つの呼び出しに削減します。

解決策を一言で言えば、マシン/モデルを無制限の間接参照で設計することです。つまり、レジスタの数に関係なく、任意のレジスタに名前を付ける（呼び出す）ことができる無制限の「アドレス」レジスタを提供します。これが機能するには、一般的に、無制限のレジスタは、潜在的に無限ループによってクリアされ、その後インクリメント（場合によってはデクリメント）される必要があります。この意味で、この解決策は、必要に応じて、目的のレジスタが見つかるまで無制限のレジスタ列を無限に探索できる無制限のμ演算子を表します。ポインタレジスタは他のレジスタと全く同じですが、1つの例外があります。「間接アドレッシング」と呼ばれる状況下では、ステートマシンのテーブル内のアドレスオペランドではなく、その内容をターゲットレジスタ（場合によっては自分自身も含む）のアドレスとして提供します。

境界付き間接参照と原始再帰関数

1 つのレジスタに 1 つのモンスター数を配置するミンスキーのアプローチを避け、マシンモデルが「コンピューターのような」ものとなるように指定すると、再帰関数 ( μ 再帰関数とも呼ばれる) (全多様体と部分多様体の両方) を計算する場合に、この間接性の問題に直面することになります。

より単純なカウンタマシンモデルは、「場合分けによる定義」（Kleene (1952) p. 229およびBoolos-Burgess-Jeffrey p. 74で定義）と呼ばれる原始再帰「演算子」を用いることで、「限定された」形式の間接参照（ひいては原始再帰関数のサブクラスを計算する）を実行できます。このような「限定された間接参照」は、非常に手間のかかる退屈な作業です。「場合分けによる定義」では、ポインタレジスタの内容を、場合分け演算子が明示的に宣言する数値/名前と照合する試行を、成功するまで何度も繰り返すことで、マシンが判断/識別する必要があります。したがって、場合分けによる定義は、例えば下限アドレスから始まり、上限アドレスに向かって、一致を試みるたびにうんざりするほど続きます。

レジスタ N の数字は 0 ですか? そうでない場合、1 ですか? 2 ですか? 3 ですか? ... 65364 ですか? そうでない場合、最後の数字 65365 に達しており、これがその数字であるはずです。そうでなければ、問題が発生します。

「制限付き」間接参照では部分再帰関数を計算できません。そのためには、制限なし間接参照、つまりμ 演算子が必要です。

もし65367番まで計算を続けることができ、実際にそのレジスタに探していたものが入っていたとしたら、計算は無事に完了したはずです！しかし、もし65367番に必要なデータがなかったらどうでしょう。どこまで計算を続けるべきでしょうか？

チューリングと同等であるためには、カウンターマシンは、単一レジスタのミンスキー・ゲーデル数法という不都合な方法を用いるか、レジスタ列の終端を探索する能力を拡張し、必要であれば無限に探索できるようにする必要がある。（「外側」に何かを見つけられないことが、アルゴリズムが停止しないことを意味する。Kleene (1952) 316ページ以降、第12章部分再帰関数、特に323～325ページを参照。）これについては、以下の例で詳しく説明する。

無制限の間接参照と部分再帰関数

無制限の間接参照を実現するには、マシンモデルの「ハードウェア」変更が必要です。この変更を加えると、モデルはもはやカウンタマシンではなく、ランダムアクセスマシンになります。

例えばINCが指定された場合、有限ステートマシンの命令は、対象となるレジスタのアドレスがどこから取得されるかを指定する必要があります。この「どこから取得されるか」は、(i)明示的なラベルを提供するステートマシンの命令、または (ii)対象となるアドレスを内容とするポインタレジスタのいずれかです。命令がレジスタアドレスを指定する場合は常に、追加のパラメータ「i/d」（「indirect/direct」）も指定する必要があります。ある意味で、この新しい「i/d」パラメータは、命令で指定された直接アドレスを取得する方法と、ポインタレジスタから間接アドレスを取得する方法を切り替える「スイッチ」です（どのポインタレジスタを取得するかは、モデルによってはすべてのレジスタがポインタレジスタになる可能性があり、命令によって指定されます）。この「相互に排他的だが網羅的な選択」は、「場合分けによる定義」のもう一つの例であり、以下の例に示す算術的な等価性は、Kleene (1952) p. 229の定義から導き出されています。

例: CPY ( 間接_ソース、 r_ソース、直接_宛先、 r_宛先)

直接アドレス指定を d="0"、間接アドレス指定を i="1" として指定するコードを割り当てます。すると、マシンは次のように送信元アドレスを決定できます。

i*[r _s ] + (1-i)*r _s

たとえば、レジスタ3の内容が「5」（つまり[3]=5）で、レジスタ4の内容が「2」（つまり[4]=2）であるとします。

例: CPY ( 1, 3, 0, 4 ) = CPY ( 間接, レジスタ 3, 直接, レジスタ 4 )

1*[3] + 0*3 = [3] = ソースレジスタアドレス5

0*[4] + 1*4 = 4 = 宛先レジスタアドレス4

例: CPY ( 0, 3, 0, 4 )

0*[3] + 1*3 = 3 = ソースレジスタアドレス3

0*[4] + 1*4 = 4 = 宛先レジスタアドレス4

例: CPY ( 0, 3, 1, 4 )

0*[3] + 1*3 = 3 = ソースレジスタアドレス3

1*[4] + 0*4 = [4] = 宛先レジスタアドレス2

間接的なCOPY命令

追加された命令の中でおそらく最も有用なのはCOPY命令でしょう。実際、Elgot-Robinson (1964) はモデルP ₀とP' ₀にCOPY命令を組み込みました。一方、Cook-Reckhow (1973) はアキュムレータベースのモデルに、アキュムレータへの間接COPY命令とアキュムレータからの間接COPY命令という2つの間接命令のみを組み込みました。

命令の過剰：単一レジスタを操作する命令は、間接的な「デュアル」（条件付きジャンプと無条件ジャンプを含む、Elgot-Robinsonモデル参照）で拡張できるため、間接命令を含めると、単一パラメータ/レジスタ命令（例：INC (d, r)、INC (i, r)）の数が倍増します。さらに悪いことに、2パラメータ/レジスタ命令には、それぞれ4種類のバリエーションが存在します。例：

CPY (d, r _s , d, r _d ) = ソースレジスタから宛先レジスタへ直接コピーする

CPY (i, r _sp , d, r _d ) = ソースポインタレジスタ r _spにあるソースアドレスを使用して間接的に宛先レジスタにコピーします。

CPY (d, r _s , i, r _dp ) = 宛先ポインタレジスタ r _dpにある宛先アドレスを使用して、ソースレジスタの内容を間接的にレジスタにコピーします。

CPY (i, r _sp , i, r _{dp ) = ソースポインタレジスタ r}_spにあるアドレスのソースレジスタの内容を、デスティネーションポインタレジスタ r _dpにあるアドレスのデスティネーションレジスタに間接的にコピーします。

同様に、2 つのソースレジスタ r _s1 r _s2と 1 つのデスティネーションレジスタ r _dを使用する 3 つのレジスタ命令では、次の加算のように 8 種類の結果が生成されます。

[r _s1 ] + [r _s2 ] → r _d

結果は次のようになります:

ADD ( d, r _s1 , d, r _s2 , d, r _d )
ADD ( i, r _sp1 , d, r _s2 , d, r _d )
ADD ( d, r _s1 , i, r _sp2 , d, r _d )
ADD ( i, r _sp1 , i, r _sp2 , d, r _d )
ADD ( d, r _s1 , d, r _s2 , i, r _dp )
ADD ( i, r _sp1 , d, r _s2 , i, r _dp )
ADD ( d, r _s1 , i, r _sp2 , i, r _dp )
ADD ( i, r _sp1、 i, r _sp2、 i, r _dp )

1つのレジスタを「アキュムレータ」（下記参照）として指定し、許可される各種命令に厳しい制限を設けることで、直接操作と間接操作の過剰な量を大幅に削減できます。ただし、削減後の命令セットが十分であることを確認する必要があり、削減によって「重要な」操作あたりの命令数が増えることを考慮する必要があります。

「アキュムレータA」の概念

歴史的慣例により、レジスタは、一連の算術演算中に文字通り数値を累算する「算術器官」であるアキュムレータ専用になります。

「我々の演算器官の最初の部分は、並列記憶装置でなければならない。これは、数値を受け取り、それを既存の数値に加え、その内容を消去し、その内容を記憶することができる。我々はこのような記憶装置をアキュムレータと呼ぶ。これは、過去および現在の様々な種類の計算機、例えば卓上乗算器、標準的なIBMカウンター、より現代的なリレー式計算機、ENIACなどにおいて、原理的に極めて慣例的なものである」（原文太字：Goldstine and von Neumann, 1946; Bell and Newell 1971の98ページ）。

しかし、アキュムレータは算術演算「操作」ごとに命令数を増やすという犠牲を払います。特に、「レジスタr2が指すレジスタの内容を間接的にインクリメントする」といった「リード・モディファイ・ライト」命令において顕著です。「A」は「アキュムレータ」レジスタAを表します。

ラベル	命令	あ	r2	378,426円	説明
		. . .	378,426	17
INCi ( r2 ):	CPY ( i, r2, d, A )	17	378,426	17	r2の内容はr378,426を指し、内容は「17」です。これをAにコピーします。
	INC (A)	18	378,426	17	Aのセメント含有量
	CPY ( d, A, i, r2 )	18	378,426	18	r2の内容はr378,426を指しています。Aの内容をr378,426にコピーします。

アキュムレータに特定の名前（例えば「A」）を付けると、命令の中でアキュムレータを暗示することができます。例えば、

INC (A) = インカ

ただし、アキュムレータを呼び出さずに CPY 命令を記述すると、命令があいまいになるか、空のパラメータが必要になります。

CPY ( d, r2, d, A ) = CPY ( d, r2, , )

CPY ( d, A, d, r2 ) = CPY ( , , d, r2 )

歴史的には、これら2つのCPY命令にはそれぞれ異なる名前が付けられてきましたが、統一された慣例はありません。伝統的には（例えば、Knuth (1973) の仮想MIXコンピュータなど）、LOADとSTOREという2つの名前が使用されています。ここでは「i/d」パラメータを追加しています。

LDA ( d/i, r _s ) = _def CPY ( d/i, r _s , d, A )

STA ( d/i, r _d ) = _def CPY ( d, A, d/i, r _d )

典型的なアキュムレータベースのモデルでは、2変数演算および定数演算（例：ADD (A, r)、SUB (A, r)）はすべて、(i) アキュムレータの内容と、(ii) 指定されたレジスタの内容を使用します。1変数演算（例：INC (A)、DEC (A)、CLR (A)）は、アキュムレータのみを使用します。どちらの命令タイプも、結果（例：和、差、積、商、剰余）をアキュムレータに格納します。

例: INCA = [A] +1 → A

例: ADDA (r _s ) = [A] + [r _s ] → A

例: MULA (r _s ) = [A] * [r _s ] → A

少なくとも 1 つのソースレジスタと宛先レジスタは常にアキュムレータ A であるため、必要に応じてニーモニックを省略できます。したがって、次のようになります。

{LDA (i/d, r _s )、STA (i/d, rd ₎、CLRA、INCA、DECA、ADDA (rs ₎、SUBA (rs ₎、MULA ( _rs )、DIVA (rs ₎など)

間接アドレスレジスタ「N」の概念

モデルに無制限のアキュムレータがある場合、他のすべてのレジスタを制限できますか？間接アドレスを導出する少なくとも 1 つの無制限のレジスタを用意しない限り、制限できません。

ミニマリストのアプローチは、それ自体を使用することです (Schönhage はこれを実行します)。

別のアプローチ（Schönhage氏もこれを採用しています）は、特定のレジスタを「間接アドレスレジスタ」と宣言し、間接参照をこのレジスタに限定することです（Schonhage氏のRAM0モデルでは、間接命令と直接命令の両方にAレジスタとNレジスタの両方を使用します）。ここでも、新しいレジスタには慣例的な名前はありません。おそらく「iNdex」の「N」、あるいは「iNdirect」、あるいは「address Number」といった名前でしょう。

柔軟性を最大限に高めるために、アキュムレータ A の場合と同様に、N を増分、減分、クリア、テスト、直接コピーなどの対象となる単なる別のレジスタと見なします。ここでも、たとえば方向と間接指定を提供する単一パラメータに命令を縮小できます。

LDAN (i/d) = CPY (i/d, N, d, A); iNdirectionレジスタ経由のアキュムレータのロード

STAN (i/d) = CPY (d, A, i/d, N)。iNdirectionレジスタを介してアキュムレータをストアする。

なぜこれがこんなに興味深いアプローチなのでしょうか？少なくとも2つの理由があります。

（１）パラメータを持たない命令セット：

Schönhageはこれを利用してRAM0命令セットを作成しました。以下のセクションをご覧ください。

（２）RAMをポストチューリングマシンに縮小する：

ミニマリストのふりをして、アキュムレータAと間接レジスタN（例：r = {r0, r1, r2, ... }）を除くすべてのレジスタを、（非常に）有限な容量を持つ無限のピジョンホールの列に縮小します。これらのピジョンホールは、（非常に）有限な数値（例：{0, 1}という値を持つ1ビット）を保持することしかできません。同様に、アキュムレータも1ビットに縮小します。演算処理はレジスタ{A, N}に限定し、間接演算を使用してレジスタの内容をアキュムレータに取り込み、アキュムレータからレジスタに0または1を書き込みます。

{ LDA (i, N)、 STA (i, N)、 CLR (A/N)、 INC (A/N)、 DEC(N)、 JZ (A/N、 I _z )、 JZ (I _z )、 H }

さらに進んで、「ERASE」と「PRINT」という 2 つの「定数」レジスタを使用して A を完全に削除します: [ERASE]=0、[PRINT]=1。

{ CPY (d, ERASE, i, N)、 CPY (d, PRINT, i, N)、 CLR (N)、 INC (N)、 DEC (N)、 JZ (i, N, I _z )、 JZ (I _z )、 H }

COPY 命令の名前を変更し、INC (N) = RIGHT、DEC (N) = LEFT を呼び出すと、ポストチューリングマシンと同じ命令に加えて、追加の CLRN が得られます。

{ 消去、印刷、消去、右、左、JZ (i、N、I _z )、JZ (I _z )、H }

間接参照付きRAMのチューリング同値性

上のセクションでは、無制限の間接参照機能を持つRAMがポストチューリングマシンを生成することを非公式に示しました。ポストチューリングマシンはチューリングマシンと同等であるため、間接参照機能を持つRAMはチューリングマシンと同等であることが示されました。

ここでは、もう少し形式的なデモンストレーションを行います。まず、3つの予約レジスタ「E」、「P」、「N」と、その右側に1、2、…、nという無限のレジスタセットを持つモデルを設計します。レジスタ1、2、…、nは「テープのマス目」とみなします。レジスタ「N」は、「ヘッド」が現在監視している「スキャンされたマス目」を指します。「ヘッド」は条件ジャンプ内にあると考えることができます。間接アドレッシングを使用していることに注意してください（Elgot-Robinson、398ページ参照）。「N」を減分または増分すると、（見かけ上の）ヘッドはマス目に沿って「左」または「右」に移動します。間接CPYを使用して、「E」=0または「P」=1の内容を、Nが指す「スキャンされたマス目」に移動します。

テープが左端にあるという事実は、小さな問題を引き起こします。LEFT が発生するたびに、命令は「N」の内容がゼロであるかどうかをテストする必要があります。ゼロである場合は、そのカウントを「0」のままにする必要があります (これは設計者としての選択です。たとえば、マシン/モデルに「イベントをトリガー」させるように選択できます)。

命令セット1（拡張）: { INC (N), DEC (N), CLR (N), CPY (d, r _s ,i, N), JZ ( i, r, z ), HALT }

以下の表は、ポストチューリング命令をRAM上の同等の命令に基づいて定義し、その動作例を示しています。レジスタr0～r5のテープ上のヘッドの（見かけ上の）位置は網掛けで示されています。

ニモニック	ラベル：		E	P	北	r0	r1	r2	r3	r4	r5	等	レジスターでのアクション	有限状態マシン命令レジスタ IR のアクション

	始める：		0	1	3				1	0

R	右：	INC (N)	0	1	4				1	0			[N] +1 → N	[IR] +1 → IR

P	印刷:	CPY ( d, P, i, N )	0	1	4				1	1			[P]=1 → [N]=r4	[IR] +1 → IR

E	消去:	CPY ( d, E, i, N )	0	1	4				1	0			[E]=0 → [N]=r4	[IR] +1 → IR

L	左：	JZ ( i, N, 終わり )	0	1	4				1	0			なし	IF N =r4] =0 THEN "end" → IR else [IR]+1 → IR
		12月（北）	0	1	3				1	0			[N] -1 → N

J0 (停止)	空白の場合ジャンプ:	JZ ( i, N, 終わり )	0	1	3				1	0			なし	IF N =r3] =0 THEN "end" → IR else [IR]+1 → IR

J1 (停止)	ジャンプマーク:	JZ ( i, N, 停止 )	0	1	3				1	0			N =r3] → A	IF N =r3] =0 THEN "end" → IR else [IR]+1 → IR
	終わり	. . . など	0	1	3				1	0

	停止:	H	0	1	3				1	0			なし	[IR] +1 → IR

例: 制限付き間接参照はチューリング等価ではないマシンを生成する

このデモンストレーション全体を通して、有限状態マシンの TABLE 内の命令は制限付き、つまり有限であることに留意する必要があります。

「アルゴリズムは、特定の種類の問題を解決するための一連の操作を与える単なる有限のルールセットであることに加えて、5 つの重要な特徴 [有限性、明確性、入力、出力、有効性] を備えています」(強調追加、Knuth、p. 4-7)。

困難が生じるのは、レジスタには明示的な「名前」（番号）があり、マシンはレジスタに「アクセス」するためにそれぞれの名前を呼び出さなければならないためです。

CASE演算子を用いて間接CPY ( i, q, d, φ )を構築します。対象レジスタのアドレスはレジスタ「q」の内容によって指定されます。CASE演算子によってこの数値が決定されると、CPYはレジスタの内容をその数値で直接レジスタ「φ」に格納します。「y」という追加のレジスタが必要になります。これはアップカウンタとして機能します。

したがって、以下は、カウンターマシン／モデルの「ハードウェア」設計変更なしに、間接CPY（i、q、d、φ）を実際にシミュレートできることを実証する、建設的なデモンストレーションです。ただし、この間接CPYは有限ステートマシンのサイズ／範囲によって「制限」されるため、この間接CPYを使用するRASPは、μ再帰関数の完全なスイートではなく、プリミティブ再帰関数しか計算できないことに注意してください。

CASE演算子はKleene (1952) (p. 229) とBoolos-Burgess-Jeffrey (2002) (p. 74) で説明されており、後者はその有用性を強調しています。以下の定義はKleeneによるものですが、一般的な「IF-THEN-ELSE」構文を反映するように修正されています。

CASE 演算子は、"case_0" から "case_last" まで、どの "case" が満たされるかに応じて自然数を φ に "返します"。満たされるケースがない場合は、"default" (別名 "woops") と呼ばれる数値が φ に返されます (ここで、x は、レジスタ q と文字列 r0、... rlast など、いくつかのパラメータの選択を示します)。

場合別の定義φ ( x , y):

case_0: Q ₀ ( x , y )が真ならばφ ₀ ( x , y ) であり、そうでなければ
case_1: Q ₁ ( x , y )が真ならばφ ₁ ( x , y ) であり、そうでなければ
cases_2 から case_next_to_last: など . . . . . . . . ELSE
case_last: Q _last ( x , y )が真であればφ _last ( x , y ) であり、そうでなければ
デフォルト: φ _default ( x , y )を実行する

Kleene は、テストを実行する「述語」 Q _{n が}すべて相互に排他的であることを要求します。つまり、「述語」は出力として { true、false } のみを生成する関数です。Boolos-Burgess-Jeffrey は、ケースが「網羅的」であるという要件を追加します。

まず、レジスタqに、ターゲットレジスタのアドレスを表す数値が格納されています。しかし、この数値は何でしょうか？「述語」は、JE (q, y, z) に続いて INC (y) と、順にこの数値をテストして、その値を見つけ出します。数値が明示的に特定されると、CASE演算子はこのレジスタの内容を φ に直接/明示的にコピーします。

場合別の定義CPY (i, q, d, φ) = _def φ (q, r0, ..., rlast, y) =

case_0: CLR (y), [q] - [y]=0 の場合、CPY ( r0, φ )、J (終了) ELSE
case_1: IF INC (y), [q] = [y]=1 THEN CPY ( r1, φ ), J (終了) ELSE
case_2 から case n: IF . . . THEN . . . ELSE
case_n: IF INC (y), [q] = [y]=n THEN CPY (rn, φ), J (終了) ELSE
case_n+1 から case_last: IF . . . THEN . . . ELSE
case_last: IF INC (y), [q] = [y]="last" THEN CPY ( rlast, φ ), J (終了) ELSE
デフォルト: うわっ

Case_0 (y の再帰の基本ステップ) は次のようになります。

ケース_0 :

CLR ( y ) ; レジスタ y を 0 に設定する
JE ( q, y, _φ0 )
J (ケース1 )

_φ0: CPY ( r0, φ )
J (出口)

case_1:など

Case_n (誘導ステップ) は次のようになります。「n」、「n+1」、...、「last」の各インスタンスは明示的な自然数でなければならないことに注意してください。

ケースn :

INC ( y )
JE ( q, y, _φn )
J (ケース_n+1 )

_φn: CPY ( rn, φ )
J (出口)

case__n+1:など

Case_last は誘導を停止し、 CASE 演算子を制限します (これにより、「間接コピー」演算子も制限されます)。

ケース_最後:

INC ( y )
JE ( q, y, _φlast )
J（うっかり）

_φlast : CPY ( rlast, φ )
J (出口)

おっと：境界外への試みをどう処理すればいいでしょうか？
出口:など

もしCASEが無限に実行できるなら、それはμ演算子でしょう。しかし、それはできません。有限状態マシンの「状態レジスタ」が最大カウント（例えば65365 = 11111111,11111111 ₂）に達したか、テーブルの命令が尽きてしまったかのどちらかです。結局のところ、 CASEは有限マシンなのです。

モデルの例

CookとReckhow（1973）のレジスタ間（「読み取り・変更・書き込み」）モデル

よく見られる Cook および Rechkow モデルは、3 値レジスタの Malzek モデル (Knuth ニーモニックで記述されています。元の命令には TRA、Read、Print 以外のニーモニックはありませんでした) に少し似ています。

LOAD ( C, r_d ) ; C → r_dCは任意の整数

例:LOAD ( 0, 5 )レジスタ 5 をクリアします。

ADD ( r_s1, r_s2, r_d ) ; [r_s1] + [r_s2] → r_dレジスタは同じでも異なっていても構いません。

例:ADD ( A, A, A )レジスタ A の内容を 2 倍にします。

SUB ( r_s1, r_s2, r_d ) ; [r_s1] - [r_s2] → r_dレジスタは同じでも異なっていても構いません。

例:SUB ( 3, 3, 3 )レジスタ 3 をクリアします。

COPY ( i, r_p, d, r_d ) ; [[r_p] ] → r_d_{ポインタレジスタr p}が指すソースレジスタの内容を間接的に宛先レジスタにコピーします。
COPY ( d, r_s, i, r_p ) ; [r_s] → [r_p]_{ソースレジスタr s}の内容をポインタレジスタr _pが指す宛先レジスタにコピーします。
JNZ ( r, I_z ) ;[r]が正の場合、条件付きジャンプを実行します。つまり、IF [r] > 0 であれば命令zにジャンプし、そうでなければシーケンスを続行します（CookとReckhowはこれを「Xj > 0の場合、制御をm行に転送する」と呼んでいます）。
READ ( r_d ) ;「入力」を宛先レジスタr _{dにコピーする}
PRINT ( r_s ) ;_{ソースレジスタ r s}の内容を「出力」にコピーします。

シェーンハーゲの RAM0 と RAM1 (1980)

Schönhage (1980) は、SMMポインターマシンモデルの同等性の証明のために選択された、非常に原始的で原子化されたモデルについて説明しています。

「明示的なアドレス指定を避けるために、RAM0には内容zのアキュムレータと現在の内容n （初期値は0）のアドレスレジスタが搭載されています」（p. 494）

RAM1 モデル: Schönhage 氏は、彼の構築を使用して、より一般的で使いやすい形式の「後継」のような RAM (この記事のニーモニックを使用) を形成する方法を示しています。

LDA k ; k --> A kは定数、例えば「47」のような明示的な数値である。
LDA ( d, r ) ; [r] → A ;Aを直接ロードする
LDA ( i, r ) ; [[r]] → A ;間接的にAをロードする
STA ( d, r ) ; [A] → r ;Aを直接保存する
STA ( i, r ) ; [A] → [r] ;間接的にAを保存する
JEA ( r, z ) ; IF [A] = [r] then I_z else continue
INCA ; [A] + 1 --> A

RAM0 モデル: Schönhage の RAM0 マシンには、1 文字で示される 6 つの命令があります (6 番目の「C xxx」は、「次のパラメータをスキップする」ことを意味するようです)。Schönhage は、アキュムレータを「z」、「N」を「n」などで指定しました。Schönhage のニーモニックではなく、上記で開発されたニーモニックを使用します。

(Z), CLRA: 0 → A
(A), INCA: [A] +1 → A
(N), CPYAN: [A] → N
(A), LDAA: [[A]] → A ; Aの内容はレジスタアドレスを指し示します; レジスタの内容をAに格納します
(S), STAN: [A] → [N] ; Nの内容はレジスタアドレスを指し示します。Aの内容をNが指すレジスタに格納します。
(C), JAZ ( z ): [A] = 0 then go to I_z; 彼の扱いは曖昧

間接参照は、(i) store_A_via_N STAN と連携した CPYAN (コンテンツ A を N にコピー/転送) と、(ii) 特有の間接参照命令から生じますLDAA ( [[A]] → [A] )。

脚注

有限 vs 無限

無制限のレジスタ「アドレス」レジスタを持たないあらゆる種類のカウンタマシンは、レジスタ「r」を名前で指定しなければならないという定義上の事実は、モデルが「r」を有限数とすることを要求していることを示しています。ただし、rが「無制限」であるというのは、モデルがそのジョブを実行するために必要なレジスタの数に上限を示唆しないという意味です。例えば、r < 83,617,563,821,029,283,746 や r < 2^1,000,001 などである必要はありません。

このように、私たちのモデルは、特定の計算を実行するために必要であれば、レジスタの数を「拡張」することができます。ただし、これはモデルが拡張する数が有限でなければならないことを意味します。つまり、自然数でインデックス付け可能でなければなりません。ωは選択肢ではありません。

間接アドレスを指定するレジスタのアドレスを提供するために無制限のレジスタを提供することで、この制限を回避できます。

参照

外部リンク

参考文献

^エルディ、ゲルグー (2010 年 9 月 6 日)。「レジスターマシンからブレインファックまで、パート 1」。2024 年 2 月 7 日に取得。

いくつかの例外を除き、これらの参照はレジスターマシンのものと同じです。

- ゴールドスタイン、ハーマン・H.、フォン・ノイマン、ジョン、「電子計算機のための問題の計画とコーディング」、プリンストン高等研究所、1947年刊。ベル、C.・ゴードン、ニューウェル、アレン（1971年）『コンピュータ構造：解説と例』（McGraw-Hill Book Company、ニューヨーク）92～119ページに再録。ISBN 0-07-004357-4}。
ジョージ・ブーロス、ジョン・P・バージェス、リチャード・ジェフリー（2002年）『計算可能性と論理：第4版』、ケンブリッジ大学出版局、ケンブリッジ、イギリス。ブーロス＝ジェフリーの原著はバージェスによって大幅に改訂され、入門書よりも高度な内容となっている。「アバカスマシン」モデルは第5章「アバカス計算可能性」で詳細に展開されており、これは3つのモデルのうちの1つであり、チューリングマシン（ブーロスのオリジナルの4要素形式のまま）と再帰が他の2つと広く比較されている。
アーサー・バークス、ハーマン・ゴールドスタイン、ジョン・フォン・ノイマン（1946年）「電子計算機の論理設計に関する予備的考察」、ゴードン・ベルとアレン・ニューウェル（1971年）「コンピュータ構造：解説と例」92頁以降に再録、マクグローヒル・ブック・カンパニー、ニューヨーク。ISBN 0-07-004357-4 。
Stephen A. CookとRobert A. Reckhow(1973)、「時間制限付きランダムアクセスマシン」、Journal of Computer Systems Science 7(4):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日受理）「計算可能性と計算への非公式算術的アプローチ」、Canadian Mathematical Bulletin、第4巻第3号、1961年9月、279-293ページ。メルザックは参考文献を挙げていないものの、「ベル電話研究所のR.ハミング博士、D.マキロイ博士、V.ヴィソッツ博士、そしてオックスフォード大学のH.ワン博士との会話の恩恵」に感謝の意を表している。
マービン・ミンスキー(1961). 「ポストの『タグ』問題の再帰的不解法とチューリング機械理論におけるその他の話題」Annals of Mathematics . 74 (3). Annals of Mathematics, Vol. 74, No. 3: 437– 455. doi : 10.2307/1970290 . JSTOR 1970290 .
マービン・ミンスキー（1967年）『計算：有限機械と無限機械』（第1版）ニュージャージー州エングルウッド・クリフス：プレンティス・ホール社特に第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編『理論計算機科学ハンドブック』第A巻：アルゴリズムと複雑性、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日の協会会議で発表。

[1] エルディ、ゲルグー (2010 年 9 月 6 日)。「レジスターマシンからブレインファックまで、パート 1」。2024 年 2 月 7 日に取得。

[ 1 ]