维基百科

计数器机

計數器機（英語：Counter machine）是一種抽象機器，作为用于形式逻辑和理论计算机科学中的计算模型，计数器机是寄存器机模型的最原始的子类。 它只由如下组成：(i)一序列的一个或多个(唯一性)命名的“无界”寄存器(只包含一个单一无界正整数的寄存器)，(ii)假如到或减去自寄存器的叫做“计数器”的物件，(iii)让计算机(人或机器)服从的(通常顺序的)算术和控制指令的列表。

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

  • 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' 的指令，否则继续按顺序执行，
  • 集合 (1): { INC ( r ), DEC ( r ), JZ ( r, z ) }, ( Minsky (1961, 1967), Lambek (1961) )
  • 集合 (2): { CLR ( r ), INC ( r ), JE ( rj, rk, z ) }, ( Ershov (1958), Peter (1958) 由 Shepherdson-Sturgis (1964) 解释; Minsky (1967); Schönhage (1980) )
  • 集合 (3): { INC ( r ), CPY ( rj, rk ), JE ( rj, rk, z ) }, ( Elgot-Robinson (1964), Minsky (1967) )。

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

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

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

形式定义

编辑

计数器机构成如下:

  1. 无限数目的标定的、离散的、无界的寄存器: 寄存器 r0 ... rn 的有限(在模型模型中无限)的集合，每个都持有一个单一非负无界整数 (0, 1, 2, ...)。寄存器做自己的算术；可以有也可以没有一个或多个特殊寄存器比如“累加器”(详情参见随机存取机)。
  2. 计数的筹码或标码 -- 只适合这个模型的一类离散的、不可细分的物件或标记。在最精简的模型中，每个算术运算，只从它的位置/磁带中增加或减少一个物件/标记。在某些模型中(比如 Melzak (1961), Minsky (1961)) 在一个运算中可以增加或减少多于一个物件/标记。
  3. 存储/标识要执行的当前指令的状态寄存器。这个寄存器是有限的并独立于上述寄存器；所以计数器机模型是哈佛结构的例子
  4. 标定的、顺序指令的列表: 指令 I0 ... Im 的有限列表。程序存储(有限状态机的指令)不在与寄存器同一个物理空间中。通常但不总是，像计算机程序，指令被按顺序列出；除非跳转成功，缺省顺序按数值次序继续。在列表中的每个指令都来自(非常)小的集合，但是这个集合不包括间接寻址。历史上最常见的指令超集，各个模型从中选出精简集合形成它的适当子集(适当就是能导致图灵等价的机器):
{ 增加 (r)，减少 (r)，清除 (r)；复制 (rj,rk)，条件跳转到指令 Iz 如果 r=0，条件跳转如果 rj=rk，无条件跳转，HALT }
某些模型要么进一步把上述某些指令原子化为无参数指令，要么组合它们为一个单一指令，比如对“减少”前导上零条件时跳转“JZ ( r, z )”。指令的原子化或包含常规指令不导致计算能力的变化，因为在一个变体中的任何程序都可以直接转换成另一个变体中的程序。

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

编辑

可以通过只有两个计数器的机器模拟任何图灵机。下面用三个步骤概述其证明。首先，图灵机可以用装备了两个栈的有限状态机(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，所以两个机器有等价的能力。

参见

编辑

引用

编辑
  • George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared -- the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
  • Arthur Burks, Herman Goldstine, John von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, mcGraw-Hill Book Company, New York. ISBN 978-0-07-004357-2 .
  • Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354-375.
  • Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
  • Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365-399.
  • J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232-245.
  • Hopcroft, John; Jeffrey Ullman. Introduction to Automata Theory, Languages and Computation 1st ed. Reading Mass: Addison-Wesley. 1979. ISBN 978-0-201-02988-8.  A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
  • Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 978-0-7204-2103-3.
  • Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
  • Joachim Lambek (1961, received 15 June 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
  • Z. A. Melzak (1961, received 15 May 1961), An informal Arthmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
  • Marvin Minsky. Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines. Annals of Math. 1961, received August 15, 1960, 74: 437–455. 
  • Marvin Minsky. Computation: Finite and Infinite Machines 1st ed. Englewood Cliffs, N. J.: Prentice-Hall, Inc. 1967.  In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
  • John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
  • Ershov, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
  • Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
  • Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42-53.
  • A. Schōnhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc.
  • Peter van Emde Boas, Machine Models and Simulations pp.3-66, appearing in:
Jan Van Leeuwen, ed. "Handbbook of Theoretical Computer Science. Volumne A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 978-0-444-88071-0 (volume A). QA 76.H279 1990.
van Emde Boas' treatment of SMMs appears on pp. 32-35. This treatment clarifies Schōnhage 1980 -- it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
  • Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23-25, 1954.

外部链接

编辑
检索自“https://zh.wikipedia.org/w/index.php?title=计数器机&oldid=80044634”