レジスタマシンは、1つ以上の「レジスタ」を持つところからそのように呼ばれる。チューリングマシンでテープとヘッドが果たす役割を「複数の一意にアドレスが振られたレジスタ群」で代替する。各レジスタには1つの正の整数が格納される。 レジスタマシンは非常に基本的なものから実際のコンピュータに近いものまで、次のように4階層に分類できる。 カウンタマシン 最も基本的なモデル。間接アドレシングができない。命令列は有限状態機械で構成される。 ポインタマシン カウンタマシンとランダムアクセスマシンの中間。それらより一般的ではないが、より抽象的である。命令列は有限状態機械で構成される。 ランダムアクセスマシン(RAM) カウンタマシンに間接アドレシングを付加し、一般に命令セットが強化されている。命令列は有限状態機械で構成される。 ランダムアクセス・プログラム内蔵機械モデル(RASP) RAM で、レジスタ内に命