闵斯基机（寄存器机/计数器机）

上级：logic

可计算性的最小汇编语言——建立在几个整数寄存器之上的一个有限程序。因为它几乎不需要任何机制，就能达到与图灵机相同的能力，所以在不可判定性证明中，它是最容易归约到的模型。

计数器机

有限多个寄存器 r₁,…,rₖ，每个都存放一个自然数，加上一个带编号的有限程序，程序由两种指令构成：

• INC(rⱼ); goto L——将 rⱼ 加 1；
• if rⱼ>0 then DEC(rⱼ); goto L₁ else goto L₂——唯一的判断（零测试与减一融合在一起）。 在指定的指令处停机。

仅此而已——没有纸带，只有加一，以及"测试并减一"。

这是真实 CPU 里的"寄存器"吗？

思路相同，本质不同。闵斯基寄存器是一个无界的自然数计数器，只支持加一/减一/测试是否为零；CPU 寄存器则是固定位宽的（例如 64 位），配有完整的ALU，且数量固定、屈指可数。寄存器机（闵斯基；Shepherdson–Sturgis）在设计之初就刻意模仿真实计算机的样子（寄存器加一个程序计数器），因此它是从图灵机理论通向汇编语言实践的桥梁——真实的汇编语言正是一台更丰富的寄存器机。关键的鸿沟在于无界与有限之别：一台内存有限的真实机器只是一个（巨大的）有限状态机；它的图灵完备性是对无界内存的理想化，而闵斯基的计数器正是这种理想化最纯粹的形式。（算法分析中常用的、更贴近现实的理想化是RAM 模型；双计数器机则是它的最小近亲。）

子节点

• minsky-examples——手工推演的小程序（加法、复制、乘法），外加一个 Haskell 模拟器。
• two-counters-turing——为什么两个计数器就已经足以给出完整的图灵能力（纸带编码方式）。