レジスタマシン
必要なのは、有限状態機械の命令レジスタや命令テーブルの限界を超えて命令をフェッチする方法であった。
例として、4つの無限長レジスタを持つカウンタマシンを考える。2つの数(m, n)の乗算を行おうとすると、m や n の大きさとは関係なく、20個程度の命令が必要となる。従って、4つしかレジスタのないRASPでは、このプログラムをレジスタに格納できない。プログラムをゲーデル数化して1つのレジスタに格納できないかぎり、このRASPは万能とは言えない。
ミンスキー (1967) では、{ CLR (r), INC (r), RPT (命令 m を n に対して "a" 回実行) } という命令を備えたカウンタマシンを示唆している。問題の解決策は示されていないが、彼は次のように述べている。
「...プログラムカウンタは RPT があと何回命令を実行しなければならないかを記憶する必要があり、これが有限なコンピュータの限られた記憶装置を消費するかもしれない。RPT 命令自体は有限個のレジスタしか必要としないが、一般に他の命令とは扱い方を変える必要があるだろう」(p. 214)
しかし、Elgot and Robinson によって、この問題が解決された。彼らの P0 RASP はインデックス付き命令セットで強化されている。これは、より複雑だがより柔軟性の高い間接指定方式である。そのモデルでは、レジスタを指定する際に、ベースレジスタとインデックスとなる即値(または、ベース即値とインデックスレジスタ)が使われる。つまり、インデックス付き命令ではオペランドが1つ増えている。
レジスタマシンは、1つ以上の「レジスタ」を持つところからそのように呼ばれる。チューリングマシンでテープとヘッドが果たす役割を「複数の一意にアドレスが振られたレジスタ群」で代替する。各レジスタには1つの正の整数が格納される。
レジスタマシンは非常に基本的なものから実際のコンピュータに近いものまで、次のように4階層に分類できる。
Cook and Reckhow (1973) は、ハルトマニス (1971) を参照し、そのモデルを単純化したランダムアクセスマシン(RAM)を提案した。Melzak (1961) に戻ったかのように見えるが、Melzak のモデルよりも単純化されている。