レジスタマシン（Register Machines）は、現代のコンピュータを抽象化した計算モデルで、少数のレジスタに格納された整数を操作することで計算を行う。提供された文脈では、この系は主に「加算」と「条件付き減算（0でなければ減算してジャンプ）」という二つの基本命令から構成される、きわめて単純な計算系として説明されている。それにもかかわらず、レジスタマシンは複雑な計算を表現でき、単純さと計算能力の両立を示す代表例とされる。
特に重要なのは、マービン・ミンスキーがわずか2つのレジスタを持つマシンでも万能、すなわちチューリング完全であることを証明した点である。これは、複数の仮想的なレジスタの状態を単一の整数の指数として符号化し、素因数分解の一意性を利用して操作するという方法に基づく。文脈中では、加算命令は特定の素数での乗算に、減算命令は除算に対応づけられている。この結果、物理的なレジスタ数が最小限であっても、計算内容に原理的な限界はないことが示された。
レジスタマシンは、算術的に最小限の命令体系から普遍的な計算が生じうることを示す例として、計算的等価性や単純な計算系における複雑性の発現を考えるうえで重要である。