计数器机

两计数器的机器是图灵等价的

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

第 1 步: 图灵机可以用两个栈来模拟

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

第 2 步: 栈可以用两个计数器模拟

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

第 3 步: 四个计数器可以被两个计数器模拟

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