カウンターマシン

カウンタマシンまたはカウンタ オートマトンとは、形式論理学および理論計算機科学で計算をモデル化するために使用される抽象マシンです。4 種類のレジスタ マシンの中で最も原始的です。カウンタ マシンは、それぞれが 1 つの非負整数を保持できる 1 つ以上の無制限のレジスタのセットと、マシンが従う (通常は連続した) 演算および制御命令のリストで構成されます。カウンタ マシンは、通常、相互排他原理に関連して並列アルゴリズムを設計するプロセスで使用されます。このように使用すると、カウンタ マシンは、メモリ アクセスに関連して計算システムの離散的な時間ステップをモデル化するために使用されます。それぞれの計算ステップのメモリ アクセスに関連して計算をモデル化することにより、インターロック、つまり 2 つ (またはそれ以上) のスレッドによる同じメモリ アドレスへの同時書き込み操作を回避するような方法で並列アルゴリズムを設計できます。

3つのカウンターを持つカウンターマシンは、単一変数の部分再帰関数を計算できます。2つのカウンターを持つカウンターマシンはチューリング完全です。つまり、適切にエンコードされたチューリングマシンをシミュレートできますが、計算できない単純な関数がいくつかあります。カウンターが1つだけのカウンターマシンは、正規言語の適切なスーパーセットと決定性文脈自由言語のサブセットを認識できます。^[1]

特定のカウンター マシン モデルでは、命令セットはわずか 1 個から 6 個または 7 個の命令までです。ほとんどのモデルには、いくつかの算術演算と少なくとも 1 つの条件付き演算 (条件が真の場合はジャンプ) が含まれています。それぞれ 3 つの命令を使用する 3 つの基本モデルが、次のコレクションから抽出されています (略語は任意です)。

• CLR (r): CLeaRレジスタr。( rをゼロに設定します。)
• INC (r): レジスタrの内容をインクリメントします。
• DEC (r): レジスタrの内容を減算します。
• CPY (r _j , _rk ): レジスタr _jの内容をそのまま残して、レジスタr _kにレジスタr _jの内容をコピーします。
• JZ (r, z): レジスタrにゼロが含まれている場合は命令zにジャンプし、それ以外の場合はシーケンスを続行します。
• JE (r _j , _{rk , z): レジスタ}r _jの内容がレジスタr _kの内容と等しい場合は命令zにジャンプし、そうでない場合はシーケンスを続行します。

さらに、マシンには通常、マシンを停止する HALT 命令があります (通常は結果が計算された後)。

上記の手順を使用して、さまざまな著者が特定のカウンター マシンについて説明しました。

• セット 1: { INC (r), DEC (r), JZ (r, z) }, (ミンスキー (1961, 1967), ランベック (1961))
• セット 2: { CLR (r), INC (r), JE (r _j , rk _, z) }, (Ershov (1958), Peter (1958) を Shepherdson–Sturgis (1964) によって解釈したもの、Minsky (1967)、Schönhage (1980))
• セット 3: { INC (r), CPY (r _j , r _k ), JE (r _j , r _k , z) }, (Elgot–Robinson (1964)、Minsky (1967))

3 つのカウンター マシン ベース モデルは、あるモデルの命令を別のモデルの命令から派生させることができるため、計算能力は同じです。すべて、チューリング マシンの計算能力に相当します。カウンター マシンは単項処理スタイルのため、通常、同等のチューリング マシンよりも指数関数的に遅くなります。

カウンターマシンモデルには、さまざまな名前が付けられており、それらの特徴によって区別するのに役立ちます。次の命令「JZDEC ( r )」は、レジスタ r が空かどうかをテストする複合命令です。空の場合は命令 I _zにジャンプし、空でない場合は r の内容を減算します。

• シェパードソン・スタージス・マシンは、著者らがモデルを分かりやすい解説書（1963年）で正式に発表したため、このマシンに採用された。命令セット（1）に便利な命令（JNZは「ゼロでない場合はジャンプ」で、JZの代わりに使用される）を追加して拡張したものを使用する。

  { INC ( r )、 DEC ( r )、 CLR ( r )、 CPY ( r _j、 rk ₎、 JNZ ( r 、 z )、 J ( z ) }

• ミンスキーマシン。マービン・ミンスキー(1961) がモデルを形式化したためです。通常は命令セット (1) を使用しますが、命令実行はデフォルトで順次実行されないため、追加のパラメータ「z」は INC の次の命令を指定するために使用され、JZDEC では代替として使用されます。

  { INC ( r, z )、JZDEC ( r, z _true、 z _false ) }

• プログラムマシン、プログラムコンピュータ、ミンスキー (1967) がこのモデルに付けた名前は、条件付きジャンプが成功しない限り、コンピュータのように命令が順番に進むためである。(通常は) 命令セット (1) を使用するが、シェファーソン-スタージス モデルと同様に拡張されることもある。JZDEC は、次のように分割されることが多い:

  { INC ( r )、 DEC ( r )、 JZ ( r、 z は_真)}

• アバカスマシンは、Lambek (1961) が Melzak (1961) モデルを簡略化して付けた名前で、Boolos–Burgess–Jeffrey (2002) もこれをアバカスマシンと呼んでいます。命令セット (1) を使用しますが、Minsky (1961) モデルと同様に次の命令を指定するために追加のパラメータ z を使用します。

  { INC ( r, z )、JZDEC (r, z _true、 z _false ) }

• ランベック マシンは、Boolos-Burgess-Jeffrey (2002) がアバカス マシンに付けた別名です。次の命令を指定するための追加パラメータを持つ命令セット (1-reduced) を使用します。

  { INC ( r, z )、JZDEC ( r, z _true、 z _false ) }

• 後継マシン。ペアノ公理の「後継演算」を使用し、ペアノ公理によく似ているため。後継 RAMモデルのベースとして使用されます。たとえば Schönhage の命令セット (2) を RAM0 および RAM1 モデルのベースとして使用し、これがポインター マシンSMM モデルにつながります。このモデルについては、van Emde Boas (1990) でも簡単に説明されています。

  { CLR ( r )、 INC ( r )、 JE ( r _j、 r _k、 z ) }

• Elgot–Robinson モデルは、RASP モデル (1964) の定義に使用されました。このモデルでは、開始時に 1 つの空のレジスタが必要です (例: [r0] =0)。(彼らは、インデックス レジスタとして使用される追加のレジスタを使用して、同じモデルを間接アドレス指定で拡張しました。)

  { INC (r), CPY (r _s、r _d )、JE (r _j、rk _、 z ) }

• その他のカウンターマシン: Minsky (1967) は、この記事のリードパラグラフで説明した利用可能な命令のスーパーセットから 3 つの基本モデル (プログラム/Minsky/Lambek-abacus、後継、Elgot–Robinson) を構築する方法を示しています。Melzak (1961) モデルは、上記のものとはまったく異なり、「増分」と「減分」ではなく「加算」と「減算」が含まれています。Minsky (1961、1967) の証明では、1 つのレジスタでチューリング等価性を実現できるとされ、計算を表すレジスタ内のゲーデル数をエンコードおよびデコードするために 2 つの命令 {MULtiply k、および DIV k} が必要です。Minsky は、2 つ以上のレジスタが利用できる場合は、より単純な INC、DEC などで十分であることを示しています (ただし、ゲーデル数はチューリング等価性を証明するために依然として必要であり、Elgot–Robinson 1964 でも実証されています)。

カウンターマシンは以下から構成されます。

1. ラベル付き無制限整数値レジスタ:それぞれが任意の単一の非負整数 (0、1、2、...、つまり無制限) を保持できるレジスタr ₀  ...  r _nの有限 (または一部のモデルでは無限) セット。レジスタは独自の演算を実行します。1 つ以上の特殊レジスタ (例: 「アキュムレータ」) が存在する場合と存在しない場合があります (詳細については、ランダム アクセス マシンを参照してください)。
2. 実行すべき現在の命令を格納/識別する状態レジスタ。このレジスタは有限であり、上記のレジスタとは別個であるため、カウンターマシンモデルはハーバードアーキテクチャの例である。
3. ラベル付けされた連続命令のリスト: 命令の有限リストI ₀  ...  I _m。プログラム ストア (有限状態マシンの命令) は、レジスタと同じ物理的な「空間」にはありません。通常、コンピュータ プログラムと同様に、命令は連続順にリストされますが、常にそうであるとは限りません。ジャンプが成功しない限り、デフォルトのシーケンスは番号順に続きます。リスト内の各命令は (非常に) 小さなセットからのものですが、このセットには間接参照は含まれません。歴史的に、ほとんどのモデルは次のセットから命令を取得しました。

{ インクリメント (r)、デクリメント (r)、クリア (r); コピー (r _j、r _k )、r の内容が 0 の場合は条件付きジャンプ、r _j =r _kの場合は条件付きジャンプ、無条件ジャンプ、HALT }

一部のモデルでは、上記の一部をパラメータなしの命令にさらに細分化するか、条件付きゼロジャンプ「JZ ( r, z )」が先行する「デクリメント」などの単一の命令に結合しています。命令の細分化や便利な命令の組み込みによって概念的なパワーが変わることはありません。1 つのバリアントのプログラムは、他のバリアントに簡単に変換できるからです。

代替命令セットについては、補足資料「レジスタマシンモデル」で説明します。

この例では、 clear、unconditional jump、copyという 3 つの便利な命令を作成する方法を示します。

• CLR ( j ): レジスタr _jの内容をゼロにクリアします。
• J ( z ): 無条件に命令I _zにジャンプします。
• CPY ( s, d ): ソースレジスタr _sの内容を宛先レジスタr _dにコピーします。( 1命令セットコンピュータ#トランスポートトリガーアーキテクチャを参照)

その後、r _{s に}は元のカウントが含まれます (ソース レジスタを空にする、つまりゼロにクリアする MOVE とは異なります)。

基本セット（1）は次のように定義される。

最初、レジスタ #2 には「2」が含まれています。レジスタ #0、#1、#3 は空です (「0」が含まれています)。レジスタ #0 は無条件ジャンプに使用されるため、計算中は変更されません。レジスタ #1 はスクラッチ パッドです。プログラムは命令 1 から始まります。

プログラムは、レジスタ#2の内容が元のカウントで停止し、レジスタ#3の内容がレジスタ#2の元の内容と同じになります。つまり、

[2] = [3].

プログラム COPY ( #2, #3) には 2 つの部分があります。最初の部分では、プログラムはソース レジスタ #2 の内容をスクラッチ パッド #1 と宛先レジスタ #3 の両方に移動します。したがって、#1 と #3 は互いのコピーであり、#2 の元のカウントのコピーでもありますが、#2 は 0 に減算する過程でクリアされます。無条件ジャンプ J (z) は、常に数値 0 を含むレジスタ #0 のテストによって実行されます。

[#2] →#3; [#2] →#1; 0→#2

2 番目の部分では、プログラムはスクラッチパッド #1 の内容を #2 に戻し (返して、復元し)、その過程でスクラッチ パッド #1 をクリアします。

[#1] →#2; 0 →#1

黄色で強調表示されたプログラムは、右上に左から右に書かれて表示されます。

プログラムの「実行」を以下に示します。時間はページを下に向かって流れます。命令は黄色、レジスタは青で表示されます。プログラムは 90 度反転されており、命令番号 (アドレス) が上部に、命令ニーモニックがアドレスの下に、命令パラメータがニーモニックの下に (セルごとに 1 つ) 表示されます。

上記の例は、最初の基本命令 {INC、DEC、JZ} が、無条件ジャンプ J、CLR、CPY という 3 つの追加命令を作成する方法を示しています。ある意味では、CPY は CLR と J に加えて基本セットを使用します。レジスタ #3 に最初に内容が含まれていた場合、 #2 と #3 の内容の合計が#3 に格納されます。したがって、完全に正確であるためには、CPY プログラムでは、移動の前に CLR (1) と CLR (3) を実行する必要があります。

しかし、ADD は簡単に実行できたはずです。実際、 ADD、MULtiply、EXPonent などの基本的な再帰関数がどのようにして実現されるかをまとめると次のようになります (Boolos–Burgess–Jeffrey (2002) p. 45-51 を参照)。

• 開始命令セット: { DEC、INC、JZ、H }
• r0 に 0 が含まれていることを前提として、JZ ( r0, z ) に関して無条件の「ジャンプ J (z)」を定義します。

{ J、DEC、INC、JZ、H }

• 上記の点から「CLeaR ( r )」を定義します。

{CLR、J、DEC、INC、JZ、H}

• 上記の点から、 r _jの内容を保持しながら「CoPY ( r _j , _{rk )」を定義します。}

{ CPY、CLR、J、DEC、INC、JZ、H }

上記はShepherdson-Sturgis (1963)の命令セットです。

• 上記を使用して、「ADD ( r _j、 r _k、 r _{i )」を定義します（おそらく r j}と r _kの内容を保持します）。

{ ADD、CPY、CLR、J、DEC、INC、JZ、H }

• 上記の点から、「MULtiply ( r _j , _rk , r _{i )」(MUL) を定義します (おそらく r j}、_rkの内容は保持されます)。

{ MUL、ADD、CPY、CLR、J、DEC、INC、JZ、H }

• 上記の観点から「指数関数 ( r _j , r _k , r _{i )」(EXP) を定義します (おそらく r j}、 r _kの内容を保存します)。

{ EXP、MUL、ADD、CPY、CLR、J、DEC、INC、JZ、H }

一般的に、同じ方法を使用して、任意の部分的または全体的な原始再帰関数を構築できます。実際、Minsky (1967)、Shepherdson–Sturgis (1963)、および Boolos–Burgess–Jeffrey (2002) は、基本セット (1) から 5 つの原始再帰関数「演算子」(以下の 1-5) を作成する方法を示しています。

しかし、完全なチューリング同値性はどうでしょうか? 完全な同値性を得るためには、全再帰関数と部分再帰関数を作成できる6 番目の演算子(μ 演算子)を追加する必要があります。

1. ゼロ関数（または定数関数）
2. 後継機能
3. 恒等関数
4. 合成機能
5. 原始的な再帰（帰納法）
6. μ演算子（無制限検索演算子）

著者らは、これが利用可能な基本セット（1、2、または3）のいずれかで簡単に実行できることを示している（例はμ演算子を参照）。これは、カウンタマシン設計の命令セットとプログラムサイズが有限であるにもかかわらず、任意のμ再帰関数をカウンタマシンとして実装できることを意味する^{[2] 。ただし、}ランダムアクセスマシンなどのより複雑なレジスタマシンで比較的簡単に定義できる関数の場合でも、必要な構成は直感に反する場合があります。これは、μ演算子は無制限の回数反復できますが、任意のカウンタマシンは、命令リストのサイズが有限であるため、無制限の数の異なるレジスタをアドレス指定できないためです。

たとえば、上記の原始再帰演算子の階層は、指数演算を超えて、クヌースの上矢印記法の高階矢印演算にさらに拡張できます。 が固定されている場合、関数は原始再帰的であり、簡単な方法でカウンタ マシンとして実装できます。 しかし、関数は原始再帰的ではありません。 のより小さい値に関数を再帰的に適用できるように呼び出しスタックを実装することにより、上記の後続、加算、乗算、および指数演算命令に似た構造を使用して上矢印演算子を実装したくなるかもしれません。 このアイデアは、多くのプログラミング言語で実際に関数を実装する方法に似ています。 ただし、カウンタ マシンは計算で無制限の数のレジスタを使用することはできません。これは、任意に大きくなる可能性がある呼び出しスタックを実装するために必要です。上矢印演算は mu 再帰的であるため、カウンター マシンとして実装できますが、関数は、ゲーデル番号付けなどを使用して、有限個のレジスタ内に無制限の量の情報をエンコードすることによって実装されます。 ${\displaystyle k}$${\displaystyle Q(x,y)=x\uparrow ^{k}y}$${\displaystyle R(n,x,y)=x\uparrow ^{n}y}$${\displaystyle R}$${\displaystyle n}$

この問題については、 「ランダム アクセス マシン」の記事で詳しく説明されています。問題は、2 つの主要なクラスと 3 番目の「不便な」クラスに分類されます。

（１）レジスタの無制限の容量とステートマシン命令の制限された容量：マシンはどのようにして有限ステートマシンの容量よりも大きな定数を作成するのでしょうか？

（２）レジスタ数の制限なしとステートマシン命令数の制限：有限ステートマシンの範囲/能力を超えるアドレス番号を持つレジスタにマシンはどのようにアクセスするのでしょうか？

（３）完全に縮小されたモデルは扱いにくい：

Shepherdson と Sturgis (1963) は、6 つの命令セットについて何ら弁解していません。彼らは、「経済性ではなくプログラミングの容易さ」に基づいて選択を行いました (p. 219 脚注 1)。

Shepherdson と Sturgis の指示 ([r] は「レジスタ r の内容」を示します):

• • インクリメント ( r ) ; [r] +1 → r
  • デクリメント ( r ) ; [r] -1 → r
  • クリア ( r ) ; 0 → r
  • コピー ( r _sから r _d ) ; [r _s ] → r _d
  • _{命令I z}への無条件ジャンプ
  • [r] =0の場合、命令I _{zにジャンプ}

ミンスキー (1967) は、2 つの命令セット { INC (z), JZDEC (r, I _z ) } を { CLR (r), INC (r), JZDEC (r, I _z ), J (I _z ) } に拡張し、その後、「ユニバーサル プログラム マシン」を 2 つのレジスタのみで構築できることを実証しました (p. 255ff)。

すべてのチューリング マシンには、その 2CM の入力と出力が適切にエンコードされていれば、それをシミュレートする 2CM が存在します。これはミンスキーの本 ( Computation、1967、p. 255-258) で証明されており、代替の証明が以下に 3 つの手順で示されます。まず、チューリング マシンは、2 つのスタックを備えた有限状態マシン (FSM) によってシミュレートできます。次に、2 つのスタックは 4 つのカウンターによってシミュレートできます。最後に、4 つのカウンターは 2 つのカウンターによってシミュレートできます。2 つのカウンターのマシンは、命令セット { INC ( r, z )、JZDEC ( r, z _true、 z _false ) } を使用します。

チューリングマシンは、FSM と、最初はゼロで満たされ、マシンが 1 と 0 を書き込むことができる無限テープから構成されます。マシンの読み取り/書き込みヘッドは、いつでもテープ上の 1 つのセルを指します。このテープは、概念的にはその時点で半分に切断できます。テープの各半分はスタックとして扱うことができ、上部は読み取り/書き込みヘッドに最も近いセル、下部はヘッドから少し離れた位置にあり、下部を超えるテープ上のすべてのゼロはゼロになります。したがって、チューリングマシンは、FSM と 2 つのスタックでシミュレートできます。ヘッドを左または右に動かすことは、1 つのスタックからビットをポップして別のスタックにプッシュすることと同じです。書き込みは、プッシュする前にビットを変更することと同じです。

スタック上のビットが 2 進数を表す (スタックの最上位ビットが最下位ビット) と考えられる場合、0 と 1 を含むスタックは 2 つのカウンターでシミュレートできます。スタックに 0 をプッシュすることは、数を 2 倍にすることと同じです。1 をプッシュすることは、数を 2 倍にして 1 を加算することと同じです。ポップすることは、2 で割ることと同じです。剰余はポップされたビットです。2 つのカウンターでこのスタックをシミュレートできます。カウンターの 1 つは、スタック上のビットを 2 進数で表す数を保持し、もう 1 つのカウンターはスクラッチパッドとして使用されます。最初のカウンターの数を 2 倍にするには、FSM で 2 番目のカウンターを 0 に初期化し、次に最初のカウンターを 1 回デクリメントして 2 番目のカウンターを 2 回インクリメントすることを繰り返します。これは、最初のカウンターが 0 に達するまで続きます。その時点で、2 番目のカウンターには 2 倍になった数が格納されます。半分にするには、1 つのカウンターを 2 回デクリメントしてもう 1 つのカウンターを 1 回インクリメントし、最初のカウンターが 0 に達するまでこれを繰り返します。剰余は、偶数ステップ後または奇数ステップ後のどちらでゼロに達したかによって決定できます。ステップ数のパリティは、FSM の状態にエンコードされます。

前と同様に、カウンターの 1 つはスクラッチパッドとして使用されます。もう 1 つは、素因数分解すると2 ^a 3 ^b 5 ^c 7 ^dになる整数を保持します。指数a、b、c、およびdは、(ゲーデル数法によって) 1 つの実カウンターにパックされている 4 つの仮想カウンターと考えることができます。実カウンターを 0 に設定してから 1 回増分すると、すべての仮想カウンターを 0 に設定することと同じです。実カウンターを 2 倍にすると、a を増分することと同じになり、半分にすると、a を減分することと同じです。同様の手順で、3 を掛けたり 3 で割ったりできますが、これはb を増分または減分することと同じです。同様に、cとd を増分または減分できます。 cなどの仮想カウンターが0 に等しいかどうかを確認するには、実カウンターを 5 で割り、余りを調べてから 5 を掛けて余りを足し戻します。実数カウンタは変更されません。cがゼロの場合のみ、剰余はゼロ以外になります。

その結果、2 つのカウンターを持つ FSM は 4 つのカウンターをシミュレートでき、その 4 つのカウンターは 2 つのスタックをシミュレートし、そのスタックはチューリング マシンをシミュレートします。したがって、FSM と 2 つのカウンターは少なくともチューリング マシンと同等の性能を持ちます。チューリング マシンは 2 つのカウンターを持つ FSM を簡単にシミュレートできるため、2 つのマシンの性能は同等です。

この結果は、N ²、 sqrt( N )、 log ₂ ( N )など、2 つのカウンタを持つマシン (一方のカウンタがNで、もう一方のカウンタが 0で初期化されている場合) では計算できない他の N の関数のリストとともに、Schroeppel (1972) の論文に掲載されています。この結果は驚くべきものではありません。なぜなら、2 つのカウンタを持つマシン モデルは、引数Nが適切にエンコードされ (ゲーデル化によって)、初期テープに単項でエンコードされたNが含まれるチューリング マシンをシミュレートする場合にのみ、普遍的であることが (ミンスキーによって) 証明されたからです。さらに、2 つのカウンタを持つマシンの出力も同様にエンコードされます。この現象は、シミュレーションによってのみ普遍性が証明される非常に小さな計算基盤 (多くのチューリング タールピット、最も小さい既知の普遍チューリング マシンなど) に典型的です。

証明の前に、いくつかの興味深い定理が示されています。

• 「定理: 3 つのカウンタを持つマシンはチューリング マシンをシミュレートできる」(p. 2、Minsky 1967:170-174 も参照)
• 「定理: 3CM [3 カウンタ マシン] は、1 つの変数の部分再帰関数を計算できます。これは、引数 [つまりN ] をカウンタに入力して開始し、(停止した場合は) 答え [つまり F( N )] をカウンタに残します。」(p. 3)
• 「定理: 入力と出力に不明瞭なコーディングが受け入れられる場合、カウンター マシンは 2CM [2 カウンター マシン] でシミュレートできます」[p. 3; 「不明瞭なコーディング」とは、2 ^W 3 ^X 5 ^Y 7 ^Zで、シミュレートされるカウンターは W、X、Y、Z です]
• 「定理: 入力と出力に不明瞭なコーディングが受け入れられる限り、あらゆるカウンター マシンは 2CM によってシミュレートできます。」(p. 3)
  • 「帰結: 2CM の停止問題は解決不可能です。
  • 「帰結: 2CM は、入力が 2 ^Nとしてコード化され、出力 (マシンが停止した場合) が 2 ^answerとしてコード化されている限り、1 つの引数の部分再帰関数を計算できます。」(p. 3)
• ^{「定理: 2 N を}計算する 2 つのカウンターを持つマシンは存在しない[1 つのカウンターがNに初期化されている場合]。」(p. 11)

「3CM は任意の部分再帰関数を計算できる」という 2 番目の定理に関して、著者は読者に「難しい問題: 3 つのカウンタのみを使用して 2 つの数を乗算する」(p. 2) という課題を提示しています。主な証明は、2 つのカウンタを持つマシンでは非線形成長率を持つ算術シーケンスを計算できない (p. 15)、つまり「関数 2 ^{X は}どの算術数列よりも急速に増加する」(p. 11) という概念に基づいています。

Friden EC-130計算機には、加算ロジックそのものはありませんでした。そのロジックは高度にシリアルで、カウントによって演算を行っていました。内部的には、10 進数の数字は基数 1 でした。たとえば、6 は、その数字に割り当てられたタイム スロット内で 6 つの連続したパルスによって表されました。各タイム スロットは、最下位桁から順に 1 つの数字を運びます。キャリーによってフリップフロップが設定され、次のタイム スロットでその数字に 1 つのカウントが追加されます。

加算はアップカウンタによって行われ、減算はダウンカウンタによって行われ、借用を処理するための同様の仕組みが採用されました。

タイム スロット スキームでは、それぞれに符号ビットがある 13 桁の 6 つのレジスタが定義されています。乗算と除算は、基本的に加算と減算を繰り返すことによって行われます。平方根バージョンの EC-132 は、連続する奇数の減算を効果的に実行し、各減算には 2 回の連続した減算が必要です。最初の減算の後、2 回目の減算の前に被減数が 1 ずつ増加します。

• ポインターマシン
• ポストチューリングマシン
• ランダムアクセスマシン
• レジスターマシン
• 王Bマシン
• ベクトル加算システム

• George Boolos、John P. Burgess、Richard Jeffrey (2002)、『Computability and Logic: Fourth Edition』、Cambridge University Press、ケンブリッジ、イギリス。Boolos-Jeffrey の原著は Burgess によって大幅に改訂され、入門書よりも高度な内容になっています。「そろばんマシン」モデルは、第 5 章「そろばんの計算可能性」で詳細に説明されています。これは、チューリング マシン (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 ページ。
• フィッシャー、パトリック C. ;マイヤー、AR ;ローゼンバーグ、アーノルド L. (1968)、「カウンターマシンとカウンター言語」、数学システム理論、2 (3): 265–283、doi :10.1007/bf01694011、MR  0235932、S2CID  13006433チューリングマシンの階層構造に類似した、カウンターマシンの時間階層構造と空間階層構造の定理を開発します。
• J. Hartmanis (1971)、「ランダムアクセスストアードプログラムマシンの計算複雑性」、数学システム理論 5、3 (1971) pp. 232–245。
• ホップクロフト、ジョン、ジェフリー・ウルマン (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. Vyssots 博士、およびオックスフォード大学の H. Wang 博士との会話の恩恵」を認めている。
• マービン・ミンスキー( 1961)。「ポストの「タグ」問題の再帰的解決不可能性およびチューリングマシン理論におけるその他の話題」。Annals of Mathematics。74 ( 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。数学-物理学Semesterberichte (ゲッティンゲン) 4 (1954)、42–53。
• A. Schönhage (1980)、「Storage Modification Machines」、Society for Industrial and Applied Mathematics、SIAM J. Comput. Vol. 9、No. 3、1980 年 8 月。ここで Schönhage は、彼の SMM が「後継 RAM」(ランダム アクセス マシン) などと同等であることを示しています。
• Rich Schroeppel、1972 年 5 月、「2 つのカウンターを持つマシンは 2 ^{Nを計算できない」、マサチューセッツ工科大学、AI 研究所、人工知能メモ #257。著者は Minsky 1967 を参照し、「} Frances Yao は1971 年 4 月に同様の方法を使用して計算不可能性を独自に証明した」と述べています。
• 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 年。 

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 日の協会会議で発表。
• ^[1]

• ワイスタイン、エリック・W.「レジスターマシン」。マスワールド。
• イグブラン - ミンスキーレジスターマシン