两个计数器已经等于图灵能力

Parent: minsky-machine

Minsky（1961）

只用两个寄存器的计数器机就能模拟任意图灵机——也就是说，在两个无界计数器上执行 INC + test/DEC，就已经是图灵完备的了（其停机问题也不可判定）。

为什么（编码方式）

一条图灵机纸带在读写头处一分为二：左半段与右半段——两个栈（one stack vs two）。把每个栈里的符号序列编码成一个数（例如 base-k 的各位数字，或素数幂）。于是：

• 移动读写头 = 从一个数里弹出一位数字、压入另一个数 = 一个计数器除以常数、另一个计数器乘以常数——而按常数做乘/除，不过是重复的 [[minsky-examples|INC/DEC loops]]；
• 读写当前被扫描的符号 = 查看最低位数字 = 一次有界的 mod/div运算，同样是循环。

于是 2 stacks = 2 numbers = 2 counters = one tape = Turing。（三个计数器可以直接模拟一台图灵机——每个栈一个，再加一个暂存位；压缩到两个则需要额外的哥德尔式数编码，速度更慢，但可行。）

教训

给一个有限控制加上任何无界的、可做零判定的存储，就得到了完整的计算能力——这与 one stack → two 的突变，或单个 [[recursive-functions|μ-operator]] 带来的突变，是同一种跳跃。图灵能力是廉价的；真正昂贵的是可判定性。正是这种廉价，让计数器机成了构造不可判定性问题的首选工具（例如 generalized-collatz 归约，就是把一台计数器机编码进去）。