江苏图灵空间装饰有限公司

可以通过只有两个计数器的机器模拟任何图灵机。下面用三个步骤概述其证明。首先，图灵机可以用装备了两个栈的有限状态机(FSM)来模拟。接着，两个栈可以用四个计数器模拟。最后，四个计数器可以用两个计数器模拟。

图灵机由一个 FSM 和一个最初填充零的无限磁带组成，机器可以在其上写一和零。在任何时候，这个机器的读/写磁头指向在磁带上的一个单元。这个磁头概念上在这一点上把磁带分为两每一半磁带都可以被当作栈，栈顶是最靠近读/写磁头的单元，而栈底与磁头有些距离，而在磁带上的所有零都超出了栈底。因此图灵机可以用 FSM 加上两个栈来模拟。左或右移动磁头等价于从一个栈弹出一位并压入到另一个栈中。写等价于在压入一位之前改变它。

包含零和一的栈可以用两个计数器模拟，当在栈上的位被认为表示二进制数的时候，而栈顶是最低位。压入零到栈顶等价于双倍这个数。压入一到栈顶等价于双倍并加 1。弹出等价于除以 2，这里的余数是弹出的位。两个计数器可以模拟一个栈，一个计数器持有其二进制表示表示在栈上的位的数，而另一个计数器用做暂存器。要双倍在第一个寄存器内的数，FSM 可以初始化第二个计数器为零，接着重复减少第一计数器一次而增加第二个计数器两次。继续直到第一个寄存器到达零。在这一点上，第二个寄存器将持有双倍的这个数。减半通过减少一个计数器两次而增加另一个一次，重复知道第一个计数器到达零来实现。余数可以通过它在偶数或奇数次尝试后结束来确定。

同上，一个计数器用做暂存器。另一个真实计数器持有一个整数，它的素因数分解是 2a3b5c7d。指数 a, b, c 和 d 可被看作要被模拟的四个虚拟计数器。如果真实计数器被置零接着增加一次，则等价于把所有寄存器都置零。如果真实计数器被双倍，则等价于增加 a，而如果它被减半，则等价于减少 a。通过类似的过程，它可以乘以或除以 3，这等价于增加或减少 b。类似的，c 和 d 可以增加或减少。要检查一个虚拟计数器比如 c 是否等于零，只要把实际计数器除以 5，看余数是什么，接着乘以 5 并加回余数。这保持真实计数器不变。余数将是非零当且仅当 c 是零。

作为结果，带有两个计数器的 FSM 可以模拟四个计数器，依次模拟两个栈，再次模拟图灵机。所以，FSM 加上两个计数器至少有图灵机一样的能力。图灵机可以轻易的模拟带有两个计数器的 FSM，所以两个机器有等价的能力。