计数器机

用于形式逻辑和理论计算机科学中的计算模型，是寄存器机模型的最原始的子类。

简介作为用于形式逻辑和理论计算机科学中的计算模型，计数器机是寄存器机模型的最原始的子类。

它只由如下组成：(i)一序列的一个或多个(唯一性)命名的“无界”寄存器(只包含一个单一无界正整数的寄存器)，(ii)假如到或减去自寄存器的叫做“计数器”的物件，(iii)让计算机(人或机器)服从的(通常顺序的)算术和控制指令的列表。

对于给定的计数器机模型，指令集是非常微小的，只有从 1 到 6 或 7 指令。所有模型都包含一些算术运算和至少一个“条件表达式”(IF-THEN-ELSE)。三个基本模型，每个都使用了三个指令，从下列指令中划分出来(简写助记符是任意的):

停机(HALT)指令可以包含也可以不包含在模型中。

三个计数器机的计算能力是等价的 -- 一个模型的指令可以从其他模型的指令得出。都等价于图灵机的计算能力(但只有用哥德尔数来编码在计算器中的数据，否则它们的能力等价于原始递归函数)。由于它们的一元处理方式，计数器典型的要比图灵机慢一个因子，它是在相比较的图灵机使用的空间的指数。

计数器机模型还有一些其他的名字: Shepherdson-Sturgis 机, Minsky 机, 程序机, 算盘机, Lambek 机, 后继机 等等。详情参见计数器机模型。1

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

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

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

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

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

本词条内容贡献者为:

李航 - 副教授 - 西南大学