ランダムアクセスマシン

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

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

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

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

• 「レジスタ」と呼ばれる無限の数のメモリ位置。各レジスタには自然数またはゼロのアドレスがあります。各レジスタには、任意のサイズの自然数を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) 命令によって指定されたポインタ レジスタによって間接的に指定できます。ソース レジスタと宛先レジスタは 1 つにすることができます。

Melzak (1961) は、カウンター マシンの簡単な図解を提供しています。その「レジスタ」は地面に掘られた穴で、これらの穴には小石が入っています。命令に従って、「コンピュータ」(人またはマシン) はこれらの穴に 1 つの小石を追加 (増加) または削除 (減少) します。必要に応じて、無限の供給源から追加の小石が供給され、余分な小石は戻されます。穴が小石を収容するには小さすぎる場合は、「コンピュータ」は穴を大きく掘ります。

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

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

レジスタマシンには、有限状態マシンの外部メモリとして、無制限の容量を持つ、個別に一意にラベル付けされた場所の無制限の (脚注|可算および無制限を参照) コレクションがあり、これを「レジスタ」と呼びます。これらのレジスタには、自然数 (ゼロおよび正の整数) のみが保持されます。有限状態マシンのテーブルにある連続命令のリストに従って、いくつかの (たとえば 2) 種類の基本操作がこれらの「レジスタ」の内容に対して実行されます。最後に、IF-THEN-ELSE形式の条件式を使用して、1 つまたは 2 つのレジスタの内容をテストし、有限状態マシンをデフォルトの命令シーケンスから「分岐/ジャンプ」できます。

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

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

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

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

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

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

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

さらに、基本セット 1、2、または 3 から、任意の基本再帰関数を作成できます(Minsky (1967)、Boolos-Burgess-Jeffrey (2002) を参照)。(網を広げて、全体および部分 mu 再帰関数を捕捉する方法については、間接アドレッシングのコンテキストで説明します)。ただし、命令セットが非常に基本的 (小さい) であるため、基本再帰関数の構築は困難です。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」

（３）私たちは「サッチャーの玄関ポーチの下」の場所に行き、コンクリートを削岩機で削り取り、「宝物」である錆びたドアノブの袋を発見する。

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

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

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

Cook と Reckhow (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 番目のレジスタにどうやって到達できるのでしょうか。

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

Elgot と Robinson (1964) は、「有限に決定された」RASP に関して同様の結論に達しています。確かに、RASP は無制限の数のレジスタにアクセスできます (たとえば、レジ​​スタから命令を取得するため) が、それは RASP がプログラム命令の「自己変更」を許可し、その「データ」をゲーデル数でエンコードしている場合に限られます (図 2、396 ページ)。

ミンスキー (1967) は、RPT (繰り返し) 命令を使用した、よりコンピュータに近いモデルの文脈で、問題の解決策を提示していますが (214 ページ、259 ページを参照)、明確な解決策は提示していません。彼は次のように主張しています。

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

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

Hartmanis (1971) の文献から、Cook (1970 年にカリフォルニア大学バークレー校で行った講義ノート) が間接アドレッシングの概念を固めたことがわかります。これは Cook と Reckhow (1973) の論文でより明確になります。Cook は Reckhow の修士論文指導教官です。Hartmanis のモデルは Melzak (1961) のモデルと非常に似ており、2 つまたは 3 つのレジスタの加算と減算、および 2 つのパラメータ コピーを使用します。Cook と Reckhow のモデルでは、アキュムレータ「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」(「間接/直接」)も指定する必要があります。ある意味で、この新しい「i/d」パラメータは、命令で指定された直接アドレスを取得する方法と、ポインタ レジスタから間接アドレスを取得する方法を切り替える「スイッチ」です (どのポインタ レジスタ (一部のモデルではすべてのレジスタがポインタ レジスタになる場合があります) は、命令によって指定されます)。この「相互に排他的だが網羅的な選択」は、「ケースによる定義」のもう 1 つの例であり、以下の例に示す算術的等価物は、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 ( 間接、reg 3、直接、reg 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 です。実際、Elgot-Robinson (1964) はモデル P ₀と P' ₀に COPY 命令を提供し、Cook-Reckhow (1973) はアキュムレータ ベースのモデルに間接命令を 2 つだけ提供しています。つまり、アキュムレータへの間接的な COPY と、アキュムレータからの間接的な COPY です。

命令の多さ: 単一レジスタに作用する命令は間接的な「デュアル」(条件付きおよび無条件ジャンプを含む、Elgot-Robinson モデルを参照) で拡張できるため、間接命令を含めると単一パラメータ/レジスタ命令の数が 2 倍になります (例: 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, _rs1 , d, _rs2 , d, r _d )を実行する
• ADD ( i, r _sp1 , d, r _s2 , d, r _d )
• ADD ( d, _rs1 , i, r _sp2 , d, r _d )を実行する
• ADD ( i, r _sp1、 i, r _sp2、 d, r _d )
• ADD ( d, _rs1、 d, _rs2、 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 つのレジスタを「アキュムレータ」として指定し (以下を参照)、許可されるさまざまな命令に厳しい制限を課すと、直接操作と間接操作の過多を大幅に削減できます。ただし、削減された命令セットが十分であることを確認する必要があり、削減によって「重要な」操作あたりの命令数が増えることを犠牲にする必要があることに注意する必要があります。

歴史的慣習では、一連の算術演算中に文字通り数値を累積する「算術器官」であるアキュムレータにレジスタが割り当てられます。

「我々の演算器官の最初の部分は、数値を受け取って既存の数値に加えることができ、またその内容を消去し、その内容を保存することのできる並列記憶器官でなければならない。我々はこのような器官をアキュムレータと呼ぶことにする。これは、過去および現在のさまざまなタイプの計算機、例えば卓上乗算器、標準的な IBM カウンター、より現代的なリレー マシン、ENIAC において、原理的に非常に慣例的である」(太字は原文: Goldstine and von Neumann、1946 年、Bell and Newell、1971 年の 98 ページ)。

ただし、アキュムレータを使用すると、算術「操作」あたりの命令数が増えます。特に、「レジスタ r2 が指すレジスタの内容を間接的に増分する」などの「読み取り-変更-書き込み」命令の場合に多くなります。「A」は「アキュムレータ」レジスタ A を示します。

アキュムレータに特定の名前、例えば「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 ) 、など）

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

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

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

柔軟性を最大限に高めるために、アキュムレータ 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 はチューリングと同等であることが示されました。

ここでは、もう少し形式的なデモンストレーションを行います。まず、3 つの予約レジスタ「E」、「P」、「N」と、右側のレジスタ 1、2、...、n の無制限のセットを使用してモデルを設計します。レジスタ 1、2、...、n は「テープのマス目」と見なされます。レジスタ「N」は、「ヘッド」が現在監視している「スキャンされたマス目」を指します。「ヘッド」は条件付きジャンプにあると考えることができます。間接アドレッシングを使用していることに注意してください (Elgot-Robinson p. 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 のテープに沿ったヘッドの (見かけの) 位置は、網掛けで示されています。

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

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

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

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

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

CASE「演算子」は、Kleene (1952) (p. 229) および Boolos-Burgess-Jeffrey (2002) (p. 74) で説明されており、後者の著者はその有用性を強調しています。次の定義は Kleene によるものですが、よく知られている「IF-THEN-ELSE」構造を反映するように変更されています。

CASE 演算子は、どの「ケース」が満たされるかに応じて、"case_0" から始めて "case_last" まで順に自然数を φ に "返します"。満たされるケースがない場合は、"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: INC (y), [q] = [y]=1 の場合、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 ( い )
• JE ( q, y, _φn )
• J (ケース_n+1 )

• _φn: CPY (rn, φ)
• J (終了)

• case__n+1:など

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

• ケース_最後:

• INC ( い )
• JE ( q, y, _φlast )
• J (うわっ)

• _φlast :CPY(rlast,φ)
• J (終了)

• うわっ:アウトオブバウンズの試みをどう処理すればいいですか?
• 終了:など

CASE が無限に継続できるとしたら、それはmu 演算子になります。しかし、それはできません。有限状態マシンの「状態レジスタ」が最大カウント (例: 65365 = 11111111,11111111 ₂ ) に達したか、テーブルの命令が不足しています。結局のところ、 これは有限マシンなのです。

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

• LOAD ( C, rd ) ; C → rdCは任意の整数

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

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

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

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

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

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

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 Iz 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 Iz ; 扱いが曖昧

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

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

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

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

• リアルRAM
• トランス二分法モデル

• ランダム アクセス マシン エミュレーター
• ランダム アクセス マシン エミュレーター
• ランダム アクセス マシン エミュレーター

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

• • Goldstine, Herman H.、および von Neumann, John、「電子計算機器の問題の計画とコーディング」、Rep. 1947、Institute for Advanced Study 、プリンストン。Bell, C. Gordon および Newell, Allen (1971)、 『Computer Structures: Readings and Examples 』 、McGraw-Hill Book Company、ニューヨークの 92 ～ 119 ページに再掲載。ISBN 0-07-004357-4 }。 
• George Boolos、John P. Burgess、Richard Jeffrey (2002)、『Computability and Logic: Fourth Edition』、Cambridge University Press、ケンブリッジ、イギリス。Boolos-Jeffrey の原著は Burgess によって大幅に改訂され、入門書よりも高度な内容になっています。「Abacus machine」モデルは、第 5 章Abacus Computabilityで詳細に説明されています。これは、広範囲に扱われ比較されている 3 つのモデルのうちの 1 つです。チューリング マシン (Boolos のオリジナルの 4 組形式のまま) と再帰が他の 2 つです。
• Arthur Burks、Herman Goldstine、John von Neumann (1946)、「電子計算機の論理設計に関する予備的考察」、Gordon BellおよびAllen Newell (1971)、「Computer Structures: Readings and Examples」、mcGraw-Hill Book Company、ニューヨーク、ISBN 0-07-004357-4の 92 ページ以降に再掲載 。 
• Stephen A. CookとRobert A. Reckhow(1973)、「時間制限付きランダムアクセスマシン」、Journal of Computer Systems Science 7(4):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、vol. 4、no. 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. Vyssots 博士、およびオックスフォード大学の H. Wang 博士との会話の恩恵」を認めている。
• マービン・ミンスキー( 1961)。「ポストの「タグ」問題の再帰的解決不可能性およびチューリングマシン理論におけるその他の話題」。Annals of Mathematics。74 ( 3)。Annals of Mathematics、Vol. 74、No. 3: 437–455。doi : 10.2307 /1970290。JSTOR  1970290。
• マービン・ミンスキー (1967)。『計算：有限機械と無限機械』（第 1 版）。ニュージャージー州エングルウッドクリフス：Prentice-Hall, Inc.特に、第 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編、Handbook of Theoretical Computer Science。Volume A: Algorithms and Complexity、The MIT PRESS/Elsevier、1990 年。ISBN 0-444-88071-2 (volume A) 。QA 76.H279 1990。van Emde Boas による SMM の扱いは pp. 32–35 に記載されています。この扱いは Schōnhage 1980 を明確にするものであり、Schonhage の扱いにほぼ従っていますが、わずかに拡張されています。効果的な理解には両方の参考文献が必要になる場合があります。 
• Hao Wang (1957)、「チューリングの計算機理論の変種」、JACM (Journal of the Association for Computing Machinery) 4; 63-92。1954 年 6 月 23 ～ 25 日の協会会議で発表。