レジスタマシン
標準的用語は存在しない。書籍によって個々に用語やシンボルを定義している。多くの場合、「レジスタ転送」的な記号を使うが、構文定義はその都度行う必要がある。
レジスタマシンは以下のような要素から成る。
有限個数でかつ無限長のレジスタ: 有限個(またはモデルによっては無限個)のレジスタ群 r0, ..., rn があり、個々のレジスタは無限長で1つの非負整数(0, 1, 2, ...)を格納する。レジスタ同士の算術ができるか、一部のレジスタがアキュムレータとして算術に使われたり、アドレスレジスタとして使われたりする。
タリーカウンタ/マーク: モデルにおける離散的識別可能オブジェクト/マーク。最も単純なカウンタマシンでは、1回の算術演算で1つのオブジェクト/マークが追加または削除される(つまり、インクリメントまたはデクリメント)。Melzak (1961) や Minsky (1961) のカウンタマシンや RAM または RASP では、1回の加算や減算で1つ以上のオブジェクト/マークの追加・削除が行われる。モデルによっては、コピー制御命令によってオブジェクト/マークの「かたまり」をレジスタからレジスタに1回の操作で移動させることができる。
(非常に)制限された命令セット: 命令は算術演算命令と制御命令の2種類に分類される。「命令セット」はそのモデルがチューリング等価となるよう選択される(つまり、任意の計算可能関数を計算可能である)。 算術演算命令: 全レジスタを対象に実行できる場合とアキュムレータだけを対象に実行できる場合がある。次のようなセットから選択される(例外もある)。