Loading article…
コンピュータ科学において、ランダムアクセスマシン（RAMまたはRAマシン）は、レジスタマシンの一般クラスに属する抽象マシンを記述する計算モデルです。RAマシンはカウンタマシンと非常によく似ていますが、レジスタへの「間接アドレッシング」機能が追加されています。レジスタは、一般的なコンピュータのメインメモリと直感的に同等ですが、レジスタには任意のサイズの自然数を格納できるという追加機能があります。カウンタマシンと同様に、RAマシンはマシンの有限状態部分（いわゆるハーバードアーキテクチャ）に実行命令を保持しています。
RAマシンにおける万能チューリングマシンに相当するもの、すなわちプログラムとデータの両方をレジスタに格納するマシンは、ランダムアクセス・プログラム内蔵マシン（RASPマシン）と呼ばれます。これは、いわゆるフォン・ノイマン・アーキテクチャの一例であり、一般的にコンピュータと認識される概念に最も近いものです。
チューリングマシンモデルやカウンタマシンモデルとともに、RAマシンモデルとRASPマシンモデルは計算複雑性解析に用いられる。ヴァン・エムデ・ボアス（1990）は、これら3つのモデルをポインタマシンとともに「逐次マシン」モデルと呼び、「並列ランダムアクセスマシン」モデルと区別している。
RA装置は、以下の要素で構成されています。
同様の概念だがユーモラスな説明については、難解なプログラミング言語Brainfuck を参照してください。[ 1 ]
ランダムアクセスマシン（RAM）の概念は、最も単純なモデルである、いわゆるカウンタマシンモデルから始まります。しかし、2つの追加要素によって、カウンタマシンから大きく変化します。1つ目は、間接アドレッシングの利便性をマシンにもたらすことであり、2つ目は、1つ以上の補助（専用）レジスタ（最も一般的なものは「アキュムレータ」と呼ばれる）を追加することで、より一般的なアキュムレータベースのコンピュータへとモデルを近づけることです。
ランダムアクセスマシン（RAM）は、間接アドレッシング機能を追加したマルチレジスタカウンタマシンと同一の抽象的な計算機モデルです。有限状態マシンのTABLEからの命令に応じて、マシンは「ターゲット」レジスタのアドレスを、（i）命令自体から直接、または（ii）命令で指定された「ポインタ」レジスタの内容（番号、ラベルなど）から間接的に取得します。
定義によれば、レジスタとは、アドレス（自然数に相当する、一意で識別可能な指定/ロケータ）と内容（単一の自然数）の両方を持つ場所である。正確を期すため、レジスタ、その内容、およびレジスタに対する操作を指定するために、Boolos-Burgess-Jeffrey (2002) の準形式的な記号体系を使用する。
定義：直接命令とは、命令自体の中で、命令の対象となるソースレジスタまたはデスティネーションレジスタのアドレスを指定する命令です。定義：間接命令とは、「ポインタレジスタ」を指定する命令で、その内容は「ターゲット」レジスタのアドレスです。ターゲットレジスタは、ソースレジスタまたはデスティネーションレジスタのどちらにもなり得ます（各種COPY命令がその例です）。レジスタは、自身を間接的に参照することもできます。
定義：ソースレジスタの内容は命令によって使用されます。ソースレジスタのアドレスは、（i）命令によって直接指定することも、（ii）命令によって指定されたポインタレジスタによって間接的に指定することもできます。
定義：ポインタレジスタの内容は、 「ターゲット」レジスタのアドレスです。
定義：ポインタレジスタの内容はターゲットレジスタを指し示します。「ターゲット」はソースレジスタまたはデスティネーションレジスタのいずれかです。
定義：宛先レジスタとは、命令が結果を格納する場所です。ソースレジスタのアドレスは、(i)命令によって直接指定することも、(ii)命令で指定されたポインタレジスタによって間接的に指定することもできます。ソースレジスタと宛先レジスタは同一にすることも可能です。
レジスタマシンは、有限状態機械とは別のメモリとして、容量が無制限の、一意にラベル付けされた離散的な場所の集合（「レジスタ」と呼ばれる）を備えています。これらのレジスタには、自然数（ゼロと正の整数）のみが格納されます。有限状態機械のTABLEにある一連の命令に従って、いくつかの（例えば2種類の）基本演算がこれらの「レジスタ」の内容に対して実行されます。最後に、IF-THEN-ELSE形式の条件式を使用して、1つまたは2つのレジスタの内容をテストし、有限状態機械をデフォルトの命令シーケンスから「分岐/ジャンプ」させることができます。
基本モデル1：ミンスキー（1961）の視覚化とランベック（1961）に最も近いモデル：
基本モデル2：後継モデル（ペアノ公理の後継関数にちなんで命名）：
基本モデル 3 : Elgot-Robinson (1964) が有界および無界 RASP の調査で使用したモデル– CLEAR の代わりに COPY を使用した「後継」モデル:
上記の 3 つの基本セット 1、2、または 3 は、あるセットの命令を別のセットの命令を使用して作成できるという意味で同等です (興味深い演習: Minsky (1967) からのヒント–予約レジスタを宣言します。たとえば、それを「0」(または「ゼロ」の Z、または「消去」の E) と呼び、数値 0 を格納します)。モデルの選択は、著者がデモンストレーションや証明などで最も使いやすいと感じるものによって決まります。
さらに、基本セット 1、2、または 3 から、任意の原始再帰関数を作成できます( Minsky ( 1967)、Boolos-Burgess-Jeffrey (2002) を参照)。 (全再帰関数と部分再帰関数を網羅するために、どのように範囲を広げるかは、間接アドレッシングの文脈で議論されます)。 ただし、命令セットが非常に原始的 (小さい) であるため、原始再帰関数を構築するのは困難です。 1 つの解決策は、別のセットからの「便利な命令」で特定のセットを拡張することです。
繰り返しますが、これらはすべて利便性を高めるためのものであり、モデル本来の性能を向上させるものではありません。
例えば、最も拡張されたセットには、3 つのセットからの固有の命令と、無条件ジャンプ J (z) が含まれます。
ほとんどの著者は条件付きジャンプのどちらか一方を選択します。たとえば、Shepherdson-Sturgis (1963) は上記のセットから JE を除いたものを使用します (完全に正確には、JZ の代わりに JNZ – Jump if Not Zero を使用します。これは、もう 1 つの便利な命令です)。
私たちの日常生活において、「間接的な操作」という概念は珍しいものではありません。
間接参照では、「Tom_&_Becky's_cave...」にある海賊の宝箱として識別される場所が指定され、これは他の任意の場所（自身を含む）へのポインターとして機能します。その内容（宝の地図）は、実際のアクションが行われているターゲットの場所「under_Thatcher's_front_porch」の「アドレス」を提供します。
以下では、これらのモデルは物理的に現実のものとは根本的に異なる2つの違いを持つ抽象モデルであることを覚えておく必要がある。それは、それぞれ無制限の容量を持つ無制限の数のレジスタである。この問題は、チューリング等価なRASPを構築し、それによって任意の部分μ再帰関数を計算しようとする際に最も顕著に現れる。
では、有限状態機械の範囲を超えるレジスタにどうやってアクセスすればよいのでしょうか？ 一つのアプローチは、プログラム命令（レジスタに格納されている命令）を、複数のコマンドを含むように変更することです。しかし、命令のサイズが（潜在的に）無限でない限り、これも使い果たしてしまう可能性があります。そこで、すべてのプログラム命令をエンコードした、非常に大きな数値である「超命令」を一つだけ使用してみてはどうでしょうか。ミンスキーはこの方法で問題を解決しましたが、彼が使用したゲーデル番号付けはモデルにとって大きな不便をもたらし、その結果は私たちが直感的に理解する「プログラム内蔵型コンピュータ」とは全く似ていません。
ElgotとRobinson（1964）は、「有限に決定された」RASPに関して同様の結論に達している。実際、RASPは無制限の数のレジスタにアクセスできる（例えば、そこから命令をフェッチする）が、それはRASPがプログラム命令の「自己変更」を許可し、その「データ」をゲーデル数でエンコードしている場合に限られる（図2、396ページ）。
ミンスキー（1967）は、自身のRPT（繰り返し）命令を用いた、よりコンピュータらしいモデルの文脈において、問題の解決策を示唆している（214ページ、259ページ参照）ものの、確固たる解決策は提示していない。彼は次のように主張している。
彼は、CLR(r)とINC(r)と組み合わせることで任意の原始再帰関数を計算できる有界RPTと、μ演算子の役割を果たす上記の無界RPTを提示しています。無界RPTはCLR(r)とINC(r)と組み合わせることでμ再帰関数を計算できます。しかし、彼は「間接参照」やRAMモデルそのものについては議論していません。
Hartmanis (1971) の参考文献から、Cook (1970 年に UC Berkeley での講義ノート) が間接アドレッシングの概念を確立したことがわかる。これは Cook と Reckhow (1973) の論文でより明確になる。Cookは Reckhow の修士論文指導教官である。Hartmanis のモデルはMelzak (1961) のモデルと非常によく似ており、 2 レジスタと 3 レジスタの加算と減算、および 2 つのパラメータコピーを使用する。Cook と Reckhow のモデルは、アキュムレータ「AC」を使用することで、パラメータ (プログラム命令で呼び出されるレジスタ) の数を 1 つの呼び出しに減らしている。
解決策を簡潔にまとめると、マシン/モデルを無制限の間接参照で設計します。つまり、いくつのレジスタがあっても、潜在的に任意のレジスタに名前を付ける（呼び出しる）ことができる無制限の「アドレス」レジスタを用意します。一般的に、この方法が機能するためには、無制限レジスタは、潜在的に無限ループによってクリアされ、その後インクリメント（場合によってはデクリメント）される機能が必要です。この意味で、この解決策は、必要に応じて、探しているものが見つかるまで無制限のレジスタ列を無限に探索できる無制限のμ演算子を表しています。ポインタレジスタは、1つの例外を除いて他のレジスタとまったく同じです。「間接アドレッシング」と呼ばれる状況では、ステートマシンのテーブルのアドレスオペランドではなく、その内容がターゲットレジスタ（場合によっては自身も含む）のアドレスになります。
ミンスキーのアプローチのように1つのレジスタに1つの巨大な数値を格納するのではなく、マシンモデルを「コンピュータのようなもの」と指定すると、再帰関数（μ再帰関数とも呼ばれる）を計算するには、間接参照の問題に直面する必要があります。これは、全体型と部分型の両方に当てはまります。
Our simpler counter-machine model can do a "bounded" form of indirection –and thereby compute the sub-class of primitive recursive functions –by using a primitive recursive "operator" called "definition by cases" (defined in Kleene (1952) p. 229 and Boolos-Burgess-Jeffrey p. 74). Such a "bounded indirection" is a laborious, tedious affair. "Definition by cases" requires the machine to determine/distinguish the contents of the pointer register by attempting, time after time until success, to match this contents against a number/name that the case operator explicitly declares. Thus the definition by cases starts from e.g. the lower bound address and continues ad nauseam toward the upper bound address attempting to make a match:
"Bounded" indirection will not allow us to compute the partial recursive functions –for those we need unbounded indirection aka the μ operator.
To be Turing equivalent the counter machine needs to either use the unfortunate single-register Minsky Gödel number method, or be augmented with an ability to explore the ends of its register string, ad infinitum if necessary. (A failure to find something "out there" defines what it means for an algorithm to fail to terminate; cf Kleene (1952) pp. 316ff Chapter XII Partial Recursive Functions, in particular p. 323-325.) See more on this in the example below.
For unbounded indirection we require a "hardware" change in our machine model. Once we make this change the model is no longer a counter machine, but rather a random-access machine.
例えば INC が指定された場合、有限状態機械の命令は、対象となるレジスタのアドレスがどこから来るかを指定する必要があります。この「どこから来るか」は、(i)明示的なラベルを提供する状態機械の命令、または (ii)対象となるアドレスの内容を持つポインタレジスタのいずれかになります。命令がレジスタアドレスを指定する場合、追加のパラメータ「i/d」（間接/直接）も指定する必要があります。この新しい「i/d」パラメータは、命令で指定された直接アドレスを取得するか、ポインタレジスタから間接アドレスを取得するかを切り替える「スイッチ」のようなものです（どのポインタレジスタを使用するかは、一部のモデルではすべてのレジスタがポインタレジスタになり得ますが、命令で指定されます）。この「相互に排他的だが網羅的な選択」は、「場合による定義」のもう 1 つの例であり、以下の例に示す算術的等価物は、Kleene (1952) p. 229 の定義から導き出されています。
追加された命令の中で最も有用なのはおそらくCOPYでしょう。実際、Elgot-Robinson（1964）は彼らのモデルP0とP'0にCOPY命令を提供しており、 Cook -Reckhow（1973）はアキュムレータベースのモデルに間接的な命令を2つだけ提供しています。それは、間接的にアキュムレータにコピーする命令と、間接的にアキュムレータからコピーする命令です。
命令の多さ: 単一レジスタに作用する命令は、その間接的な「双対」(条件付きジャンプと無条件ジャンプを含む、Elgot-Robinson モデルを参照) で拡張できるため、間接命令を含めると、単一パラメータ/レジスタ命令 (例: INC (d, r)、INC (i, r)) の数が 2 倍になります。さらに悪いことに、2 つのパラメータ/レジスタ命令には、4 つの可能なバリエーションがあります。例:
同様に、2つのソースレジスタr s1、 r s2と1つのデスティネーションレジスタr dを含むすべての3レジスタ命令は、例えば加算のように8つのバリエーションを生み出します。
結果は以下の通りになります。
1つのレジスタを「アキュムレータ」（下記参照）として指定し、許可される各種命令に厳しい制限を設けることで、直接演算と間接演算の膨大な数を大幅に削減できます。ただし、削減後の命令セットが十分であることを確認する必要があり、また、削減によって「重要な」演算あたりの命令数が増加するという代償を伴うことを認識しておく必要があります。
歴史的慣習では、演算処理の過程で数値を文字通り蓄積していく「算術器」であるアキュムレータに専用のレジスタが割り当てられている。
しかし、アキュムレータは、特に「レジスタr2が指すレジスタの内容を間接的にインクリメントする」などの「読み出し・変更・書き込み」命令と呼ばれるものに関して、算術「演算」あたりの命令数を増やすという代償を伴います。「A」は「アキュムレータ」レジスタAを表します。
アキュムレータに特定の名前（例えば「A」）を付けておけば、命令の中でアキュムレータを暗黙的に指定できます。例えば、
しかし、アキュムレータを指定せずにCPY命令を記述すると、命令が曖昧になるか、パラメータが空でなければなりません。
歴史的に見ると、これら2つのCPY命令にはそれぞれ異なる名前が付けられてきましたが、慣例はありません。従来（例えば、クヌース（1973）の架空のMIXコンピュータ）では、LOADとSTOREという2つの名前が使われていました。ここでは、「i/d」パラメータを追加しています。
典型的なアキュムレータベースのモデルでは、2変数演算および定数演算（例：ADD（A、r）、SUB（A、r））はすべて、（i）アキュムレータの内容と（ii）指定されたレジスタの内容を使用します。1変数演算（例：INC（A）、DEC（A）、CLR（A））は、アキュムレータのみを必要とします。どちらの命令タイプも、結果（例：和、差、積、商、剰余）をアキュムレータに格納します。
必要に応じて、少なくとも1つのソースレジスタと宛先レジスタは常にアキュムレータAであるため、ニーモニックを省略することができます。したがって、次のようになります 。
モデルに無制限のアキュムレータがある場合、他のすべてのレジスタに上限を設けることは可能でしょうか？少なくとも1つの無制限レジスタを用意し、そこから間接アドレスを導出するまでは、それは不可能です。
ミニマリスト的なアプローチとは、それ自体を使うことである（シェーンハーゲはこの方法を採用している）。
別のアプローチ（Schönhage氏も同様の手法を採用）としては、特定のレジスタを「間接アドレスレジスタ」と宣言し、このレジスタを基準とした間接アドレス指定に限定する方法があります（Schonhage氏のRAM0モデルでは、直接命令だけでなく間接命令にもAレジスタとNレジスタの両方を使用しています）。ここでも、新しいレジスタには慣習的な名前は付けられていません。「iNdex」の「N」、あるいは「iNdirect」または「アドレス番号」などが考えられます。
最大限の柔軟性を確保するため、アキュムレータAの場合と同様に、Nもインクリメント、デクリメント、クリア、テスト、直接コピーなどの操作が可能な単なるレジスタとして扱います。ここでも、例えば方向指定と間接指定を可能にする単一のパラメータに命令を縮小することができます。
なぜこれがそんなに興味深いアプローチなのか？少なくとも2つの理由がある。
（１）パラメータのない命令セット：
Schönhageは、RAM0命令セットを作成するためにこの方法を用います。詳細は下記のセクションを参照してください。
（２）RAMをポストチューリングマシンに還元する：
ミニマリストを装い、アキュムレータ A と間接レジスタ N を除くすべてのレジスタ ( r = { r0, r1, r2, ... }) を、容量が極めて限定されたピジョンホールの無限列に縮小します。これらは、値 { 0, 1 } を持つ単一のビットなど、容量が極めて限定された数値を保持するだけです。同様に、アキュムレータも単一ビットに縮小します。演算はレジスタ { A, N } に限定し、間接演算を使用してレジスタの内容をアキュムレータに取り込み、アキュムレータからレジスタに 0 または 1 を書き込みます。
さらに進んで、「ERASE」と「PRINT」と呼ばれる2つの「定数」レジスタを使用することでAを完全に排除します: [ERASE]=0、[PRINT]=1。
COPY命令の名前を変更し、INC (N) = RIGHT、DEC (N) = LEFTを呼び出すと、ポストチューリングマシンと同じ命令に加えて、CLRN : が追加されます 。
上記のセクションでは、非公式ながら、無制限の間接参照機能を持つRAMがポストチューリングマシンを生成することを示しました。ポストチューリングマシンはチューリングマシンと同等であるため、間接参照機能を持つRAMがチューリングマシンと同等であることを示したことになります。
ここでは、もう少し正式な説明をします。まず、予約レジスタ「E」、「P」、「N」と、右側に無制限のレジスタセット 1、2、...、n を持つモデルを設計します。レジスタ 1、2、...、n は「テープのマス目」とみなされます。レジスタ「N」は、「ヘッド」が現在監視している「スキャンされたマス目」を指します。「ヘッド」は条件付きジャンプ中であると考えることができます。間接アドレッシングを使用していることに注意してください (Elgot-Robinson p. 398 を参照)。「N」をデクリメントまたはインクリメントすると、(見かけ上の) ヘッドはマス目に沿って「左」または「右」に移動します。間接 CPY を使用して、「E」=0 または「P」=1 の内容を、N が指す「スキャンされたマス目」に移動します。
テープが左端になっているという事実は、ちょっとした問題を引き起こします。LEFTが発生するたびに、命令は「N」の内容がゼロかどうかをテストする必要があります。ゼロの場合は、そのカウントを「0」のままにしておく必要があります（これは設計者である私たちの選択です。たとえば、マシン/モデルが私たちが選択した「イベントをトリガー」するようにすることもできます）。
以下の表は、ポストチューリング命令をRAM相当命令の観点から定義し、その動作例を示しています。レジスタr0～r5のテープ上のヘッドの（見かけ上の）位置は網掛けで示されています。
このデモンストレーション全体を通して、有限状態機械のテーブル内の命令は制限されている、つまり有限であることを念頭に置いておく必要があります。
CASE演算子を使って間接命令CPY(i, q, d, φ)を構築します。ターゲットレジスタのアドレスはレジスタ「q」の内容によって指定されます。CASE演算子がこの数値を判定すると、CPYはその数値を持つレジスタの内容を直接レジスタ「φ」に格納します。また、アップカウンタとして機能するレジスタ「y 」も必要になります。
CASE演算子については、Kleene（1952）（p. 229）およびBoolos-Burgess-Jeffrey（2002）（p. 74）で説明されており、後者の著者らはその有用性を強調している。以下の定義はKleeneによるものだが、おなじみの「IF-THEN-ELSE」構文を反映するように修正されている。
CASE演算子は、「case_0」から始まり「case_last」まで順に、どの「case」が満たされるかに応じて自然数をφに「返します」。どのcaseも満たされない場合は、「default」（別名「woops」）と呼ばれる数がφに返されます（ここでxは、レジスタqと文字列r0、...rlastなどのパラメータの選択を表します）。
場合別の定義φ ( x , y):
クリーネは、テストを行う「述語」Qnがすべて相互に排他的であることを要求します。「述語」とは、出力として{true、false}のみを生成する関数です。ブールス・バージェス・ジェフリーは、ケースが「網羅的」であることを要求します。
まず、レジスタqに格納されている数値が、ターゲットレジスタのアドレスを表します。しかし、この数値とは何でしょうか？「述語」は、JE(q, y, z)に続いてINC(y)を実行することで、この数値を一つずつ検証していきます。数値が明確に特定されると、CASE演算子によって、このレジスタの内容が直接的かつ明示的にφにコピーされます。
ケース0（yに対する再帰の基本ステップ）は次のようになります。
case_n（帰納ステップ）は次のようになります。ただし、「n」、「n+1」、「...」、「last」の各インスタンスは明示的な自然数でなければならないことに注意してください。
Case_last は帰納法を停止し、CASE 演算子を制限します（それによって「間接コピー」演算子も制限します）。
CASE が無限に続くことができれば、それはミュー演算子になります。しかし、それは不可能です。有限状態機械の「状態レジスタ」が最大カウントに達したか (例えば 65365 = 11111111,11111111 2 )、テーブルに命令がなくなったためです。結局のところ、それは有限機械なのです。
よく見かけるクックとレチコウのモデルは、3進レジスタのマルツェクのモデルに少し似ています（クヌースのニーモニックを使って書かれていますが、元の説明書には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] ] → rdポインタレジスタr pが指すソースレジスタの内容を間接的にデスティネーションレジスタにコピーします。 COPY ( d, rs, i, rp ) ; [rs] → [rp]ソースレジスタrsの内容を、ポインタレジスタrpが指す宛先レジスタにコピーします。 JNZ ( r, Iz ) ;[r]が正の場合に条件付きジャンプを実行します。つまり、[r] > 0の場合は命令zにジャンプし、そうでない場合はシーケンスを続行します（CookとReckhowはこれを「Xj > 0の場合に制御をm行に転送する」と呼んでいます）。 READ ( rd ) ;「入力」を宛先レジスタr dにコピーする PRINT ( rs ) ;ソースレジスタrsの内容を「出力」にコピーします。Schönhage (1980) は、自身の SMMポインターマシンモデルの等価性を証明するために選択した、非常に原始的で原子化されたモデルについて述べている。
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 などを要求するわけではありません。
間接アドレスを指定するレジスタのアドレスを提供する無制限のレジスタを用意することで、この制約を回避できます。
いくつかの例外を除き、これらの参照はレジスタマシンのものと同じです。