レジスタマシン
1971年、ユリス・ハルトマニスは、RASPモデルでの間接指定を単純化した。間接指定とは、ポインタレジスタを使って命令が実際に利用するレジスタを(番号またはアドレスで)指定することである。ポインタレジスタに制限がなければ、RAM や RASP はチューリング等価となる。間接指定されるレジスタは命令形式上の指定される位置によって、演算の入力にも出力先にもなる。
つまり、有限状態機械は対象レジスタのアドレスを明示的に示す必要がない。あるポインタレジスタが指しているレジスタの内容を使って、xyz という演算をする。命令においてはポインタレジスタは明確に名前で指定しなければならないが、その内容が何であるかを知る必要はない。
エミール・ポストの1936年の論文の基づいた Wang (ハオ・ワン)の研究により、Wang はBマシンの定義に到達した。これは、2種類のシンボルと4種類の命令を持つポスト-チューリング機械であった。命令は以下の通り。
{ LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z }
Wang (1954, 1957) と C.Y. Lee (1961) は、これらにポストの命令 { ERASE } とポストの無条件分岐 { JUMP_to_ instruction_z } を追加した(あるいは簡略化すれば JUMP_IF_blank_to_instruction_z という命令を追加した)。Lee はこれをWマシンモデルと称した。
{ LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] }
Wang は、彼のモデルがチューリングマシンと現実のコンピュータの架け橋となることを望んでいた。
Wang の研究成果は大きな影響を及ぼし、彼の論文はミンスキー (1961, 1967)、Melzak (1961)、Shepherdson and Sturgis (1963) で引用された。特に Shepherdson and Sturgis (1963) では次のような記述がある。
Lmbek (1961) は Melzak のモデルを2つの単項命令( X+ 命令と、可能ならば X- し、そうでなければ分岐)に単純化した。これはミンスキー (1961) と全く同じである。