レジスタマシン
「...我々は、Wang が示唆した計算の実用面と論理面の和解をさらに推し進めようとした」(p. 218)
Matin Davis は、このモデルを(2シンボルの)ポスト-チューリング機械に発展させた。
Wang/ポスト-チューリングのモデルには問題があった。すなわち、Wang のモデルはチューリング機械のような1つのテープの使用を前提としていた。Melzak (1961) と Shepherdson and Strugis (1963) ではこれについて次のように述べている。
「...チューリング機械にはある曖昧さが存在する...チューリング機械は手順が多く複雑である。このため設計が困難で、記憶領域や時間の最適化を検討するのも難しく、2つのアルゴリズムの効率を比較するのも困難である」(Melzak (1961) p. 281)
「...困難ではないが...次の2つの理由から、証明過程が複雑で、それを追うのが退屈な作業となる。(1) チューリング機械にはヘッドが1つしかないため、計算を一桁ずつの操作を積み重ねて構成しなければならない。(2) テープも1つしかないため、テープ上のある部分を保持しようとすると非常に複雑な操作が必要になる」(Shepherdson and Sturgis (1963) p. 218)
実際、チューリング機械の動作例を見れば、それが複雑であることがわかる。
カウンタマシンとランダムアクセスマシンの中間。それらより一般的ではないが、より抽象的である。命令列は有限状態機械で構成される。