レジスタマシンとは、有限個のレジスタに格納された整数を操作することで計算を行う計算モデルである。現代のコンピュータを抽象化したモデルとして知られ、命令セットは「レジスタの値を1増やす」「値が0でなければ1減らして指定した命令へ分岐する」といった、ごく少数の算術命令だけで足りる。テープと読み書きヘッドを前提とするチューリングマシンに比べて構成が実際の計算機に近く、計算可能性理論の教科書的なモデルとして用いられる。
この極端な単純さにもかかわらず、レジスタマシンは万能な計算能力をもつ。マービン・ミンスキーは、レジスタが2本しかないマシンでもチューリングマシンと等価な計算ができることを示した。鍵となるのは、複数の仮想レジスタの状態を素数の指数として単一の整数に符号化する手法である。素因数分解の一意性によって各仮想レジスタの値が復元でき、加算は特定の素数による乗算、減算はその素数による除算に対応する。物理的なレジスタの本数が最小限であっても、原理的に計算能力に限界はない。
レジスタマシンは、セルオートマトンやタグシステム、置換系などと並んで、最小限の規則から複雑な振る舞いと普遍的な計算が生じることを示す例として参照される。異なる単純な系が互いに同じ計算能力に到達するという観察は、計算的等価性原理を支える具体例のひとつでもある。