レジスタマシン
最も基本的なモデル。間接アドレシングができない。命令列は有限状態機械で構成される。
1950年代初期に2つの方向性が現れた。第一はコンピュータをチューリングマシンとしてモデリングする方向で、第二はチューリングマシンと同等の能力がある、よりコンピュータ的モデル(つまり、逐次命令実行と条件付き命令のあるモデル)を定義する方向である。これらの研究は2つの難しい問題の解を得る努力の過程でなされた。ひとつはエミール・ポストの提示した未解決問題(タグ問題)、もうひとつはヒルベルトの23の問題の10番目のディオファントス方程式にまつわる問題である。研究者らは、「論理」性がより少なく、「算術」性が強いチューリング等価なモデルを捜し求めていた。(cf Melzak (1961) p. 281, Shepherdson-Sturgis (1963) p. 218)。
第一の方向性は、Hans Hermes (1954) や Heinz Kaphengst (1959) が創始し、第二の方向性は Hao Wang (1954, 1957) が創始し、上述のように Z. A.
RASP(ランダムアクセス・プログラム内蔵機械)は、レジスタにプログラムを構成する命令を格納するカウンタマシンとして生まれた。有限状態機械内の命令レジスタとは別に、プログラムカウンタ(PC)と現在の命令を表す数を格納する一時レジスタが必要となる。有限状態機械の命令テーブルは、(1) 実行すべき命令を適当なレジスタからフェッチし、(2)その命令を解析し、(3) その命令のオペランドで指定されたレジスタをフェッチし、(4) その命令を実行する。
ただし、これをカウンタマシンに基づいて構築してもチューリング等価とはならず、計算可能なあらゆるものを計算可能とは言えない。このモデルは本質的に有限状態機械の持つ命令セットに制限されている。カウンタマシン・ベースのRASPは、任意の原始再帰関数(例えば乗算)は計算可能だが、全てのμ再帰関数(例えばアッカーマン関数)は計算できない。
Elgot-Robinson はRASPモデルによる命令の自己書き換えの可能性を研究した。この考え方は古くからあり、Durks-Goldstine-von Neumann (1946-7) で提案されていた。Melzak (1961) ではこれを "comnputed goto" と称していたが、実際にはその代わりに間接指定を使っている。Computed goto とは、RASP のプログラムにおいて、条件分岐や無条件分岐の分岐先を計算によって求めるものである。
しかし、これは(少なくともゲーデル数に頼らない限り)解決策とはならない。