レジスタマシン
RAM で、レジスタ内に命令を格納できる。万能チューリングマシンに対比され、ノイマン型アーキテクチャの一例でもある。ただし、モデルとして理想化されているため、事実上無限個のレジスタを持つ。また、命令セットもRISCに比較してもさらに少ない。
正しく定義されたレジスタマシンモデルは、チューリング等価である。計算速度はモデルによって異なる。
実用的な意味では、このような概念を仮想機械と呼び、ハードウェア・アーキテクチャへの依存性を削減する目的で用いられる。また、このようなマシンは教育用としても利用される。
そこで、テープを無限長(任意の整数を格納できる)の断片に分けるという考え方が出てくる。それぞれにヘッドがあり、デクリメントでは左に移動し、インクリメントでは右に移動する。ある意味で、ヘッドの位置がマークのスタックの先端を指す。ミンスキー (1961) および Hopcroft and Ullman (1979, p. 171ff) では、テープは左端から続くマーク部分以外は常に空白状態とされた(ヘッドがそこまで移動したことがない場合でも)。つまり、記録されたマークの個数が整数値に対応する。このモデルでは、デクリメントする前にゼロかどうかを確認しないと、テープの端をつき抜けてしまう。
ミンスキー (1961) と Shpepherdson-Sturgis (1963) は、テープが1つであっても、このモデルがチューリング等価であることを示した。この場合、テープ上のデータはゲーデル数(あるいは何らかの一意に符号化/複号化可能な数)とされる。この数は計算の進行に伴って変化する。ゲーデル数の符号化を伴う1つのテープのバージョンでは、カウンタマシンは (1) ゲーデル数に定数(2とか3)をかける操作ができ、(2) 定数(2や3)で割って、余りがゼロなら分岐する操作ができる必要があるとされた。ミンスキー (1967) では、これらの奇妙な命令の代わりに { INC (r), JZDEC (r, z) } で十分とされ、さらにテープ(すなわちレジスタ)が2つあれば { CLR (r), J (r) } で等価となることが示された。ただし、単純なゲーデル数化は依然として必要である。RASP モデルについての同様の研究は Elgot-Robinson (1964) でなされている。
カウンタマシン: {インクリメント (r)、デクリメント (r)、ゼロクリア (r)} 最小構成 RAM、RASP: {インクリメント (r)、デクリメント (r)、ゼロクリア (r)、即値ロード k、加算 (r1,r2)、減算 (r1,r2)、インクリメント アキュムレータ、デクリメント アキュムレータ、クリア アキュムレータ、レジスタ r の内容をアキュムレータに加算、レジスタ r の内容をアキュムレータから減算、} 最大構成 RAM、RASP: 上記に加えて {乗算、除算、各種ビット論理演算(左シフト、ビットテストなど)} 制御命令: カウンタマシン: オプションで {コピー (r1,r2)} RAM、RASP: {コピー (r1,r2)} または {r からアキュムレータへのロード、アキュムレータから r へのストア、即値のアキュムレータへのロード} のどちらかが必須 全モデル: レジスタ内容のテストを伴う条件付き分岐命令が少なくとも1つ必要。例えば {ゼロのとき分岐、ゼロでないとき分岐、等しいとき分岐、等しくないとき分岐} 全モデルでオプション: { 無条件分岐(GOTO) } レジスタ指定方法: カウンタマシン: 間接指定(レジスタの内容が別のレジスタの番号を指定)はなく、オペランドで直接指定する。 RAM、RASP: 間接指定可能で、オペランドでの直接指定もある。 入出力: 全モデルでオプション
状態レジスタ: 上述のレジスタ群とは別に、命令レジスタ(IR)に現在の命令と命令テーブル上のその命令のアドレスを格納する。このレジスタと命令テーブルは有限状態機械内にある。
カウンタマシンに間接アドレシングを付加し、一般に命令セットが強化されている。命令列は有限状態機械で構成される。