计数器机 計數器機英語Counter machine是一種抽象機器作为用于形式逻辑和理论计算机科学中的计算模型计数器机是寄存器机模型的最原始的子类 它只由如下组成i一序列的一个或多个唯一性命名的无界寄存器只包含一个单一无界正整数的寄存器ii假如到或减去自寄存器的叫做计数器的物件iii让计算机人或机器服从的通常顺序的算术和控制指令的列表 对于给定的计数器机模型指令集是非常微小的只有从  到  或  指令所有模型都包含一些算术运算和至少一个条件表达式IFTHENELSE三个基本模型每个都使用了三个指令从下列指令中划分出来简写助记符是任意的 CLR  r  清除CLeaR寄存器 r 清空计数器 r INC  r  增加INCrement寄存器 r 的内容 DEC  r  减少DECrement寄存器 r 的内容 CPY  rj rk  复制CoPY寄存器 rj 的内容到寄存器 rk保持 rj 的内容不动 JZ  r z  如果寄存器 r 的内容为零Zero则跳转Jump到标记为 z 的指令否则继续按顺序执行 JE  rj rk z  如果寄存器 rj 的内容等于Equal寄存器 rk 的内容则跳转Jump到标记为 z 的指令否则继续按顺序执行 集合   INC  r  DEC  r  JZ  r z    Minsky   Lambek   集合   CLR  r  INC  r  JE  rj rk z    Ershov  Peter  由 ShepherdsonSturgis  解释 Minsky  Schönhage   集合   INC  r  CPY  rj rk  JE  rj rk z    ElgotRobinson  Minsky   停机HALT指令可以包含也可以不包含在模型中 三个计数器机的计算能力是等价的  一个模型的指令可以从其他模型的指令得出都等价于图灵机的计算能力但只有用哥德尔数来编码在计算器中的数据否则它们的能力等价于原始递归函数由于它们的一元处理方式计数器典型的要比图灵机慢一个因子它是在相比较的图灵机使用的空间的指数 计数器机模型还有一些其他的名字 ShepherdsonSturgis 机 Minsky 机 程序机 算盘机 Lambek 机 后继机 等等详情参见计数器机模型