维基百科

寄存器机

在数理逻辑和理论计算机科学中，寄存器机（英語：Register machine），又譯為暫存器機，是以类似于使用图灵机的方式使用的一类抽象機器。所有模型都是图灵等价的。

寄存器机得名于它有一个或多个“寄存器”——替代了图灵机的磁带和磁头，这个模型使用了多个唯一寻址的寄存器，每个都持有一个单一正整数。

在文献中至少可找到4个子类，下面按最原始到最类似计算机的次序列出：

  • 计数器机——最原始和精简的模型。缺乏间接寻址。指令在按照哈佛结构的有限状态机内。
  • 指针机——计数器机和RAM模型的混合。比这两个模型更少共通更多抽象。指令在按照哈佛结构的有限状态机内。
  • 随机存取机（RAM）——带有间接寻址和通常扩充的指令集。指令在按照哈佛结构的有限状态机内。
  • 随机存取存储程序机（RASP）——带有指令在其寄存器中的RAM，类似于通用图灵机；因此它是冯·诺伊曼结构的一个例子。但是不同于计算机的是这个模型是带有有效无限个寄存器的“理想”机器。不像计算机甚至RISC计算机，指令集在指令数目上是非常精简的。

任何正确定义的寄存器机都是图灵等价的。计算速度严重倚赖于模型细节。

形式定义

没有标准术语；每个作者都以自己的助记符或符号下定义。

寄存器机构成如下：

  1. 无界数目的标定的、离散的、在宽度（容量）上无界的寄存器：有限（在某些模型中无限）的寄存器集合r0 ... rn，每个都有无限宽度并持有一个单一非负整数（0, 1, 2, ...）。寄存器可以做它们自己的算术，或者可以有也可以没有一个或多个做算术的特殊寄存器，比如“累加器”或“地址寄存器”。
  2. 计数的筹码或标码——离散的、不可细分的唯一一类只适合这个模型的物件或标记。在最精简的计数器机模型中，对每个算术指令只有一个物件/标记被要么增加到要么减少自它的位置/磁带。在某些计数器机模型（比如Melzak（1961）, Minsky (1961))和多数RAM与RASP模型中，在“加法”、“减法”、“乘法”和“除法”这样的指令中多于一个物件/标记可以增加或减少。某些模型有控制运算比如“复制”（也叫做“移动”、“装载”、“存储”）一个动作就从寄存器到寄存器移动一堆物件/标记。
  3. （非常）有限的指令集：指令可被分类为算术和控制。对指令集有一种限制：一个指令集必须允许这个模型是图灵等价的，就是说它必须能够计算任何偏递归函数：
    1. 算术：算术指令可以运算于所有寄存器上或只在特殊的寄存器上（比如累加器）。他们通常被按如下集合来选择（但例外大量存在）：
      • 计数器机：{增加（r），减少（r），清零（r）}
      • 精简RAM, RASP：{增加（r），减少（r），清零（r），装载立即常量k，加（r1,r2），真减（r1,r2），增加累加器，减少累加器，清除累加器，加寄存器r的内容到累加器，从累加器真减寄存器r的内容}
      • 扩充RAM, RASP：所有精简指令加上：{乘法，除法，各种布尔逐位运算 (左移位，位测试，等等)}
    2. 控制：
      • 计数器机模型：可选的{复制（r1,r2）}
      • RAM和RASP模型：多数都有{复制（r1,r2）}，或{装载累加器从r，存储累加器到r，装载立即常量到累加器}
      • 所有模型：至少一个跟随寄存器测试的条件“跳转”（分支，goto），比如{零时跳转，非零时跳转（就是，正时跳转），等时跳转，非等时跳转}
      • 所有模型可选的：{无条件程序跳转（goto）}
    3. 寄存器寻址方法：
      • 计数器机：没有间接寻址，在高度原子化的模型中可能有立即操作数
      • RAM和RASP：可用间接寻址，典型的立即操作数
    4. 输入输出：
      • 所有模型：可选的
  4. 状态寄存器：一个特殊的指令寄存器"IR"，有限并独立于上述寄存器，它存储当前的要执行的指令和它在指令TABLE（表格）中的地址；这个寄存器和它的TABLE位于有限状态机内。
    • IR是对于所有模型都是禁区。在RAM和RASP的情况下，为了确定一个寄存器的地址，模型可以选择要么（i）在直接寻址的情况下——地址通过TABLE指定而临时位于IR中，或（ii）在间接寻址的情况下——寄存器的内容由IR的指令指定。
    • IR不是RASP（或常规计算机）的程序计数器（PC）。PC只是类似累加器的另一个寄存器，只专门持有RASP的当前基于寄存器的指令的编号。所以RASP有两个“指令/程序”寄存器——（i）IR（有限状态自动机的指令寄存器）和（ii）PC（程序计数器）用于位于寄存器中的程序。（同样于专门的PC寄存器，RASP可以有专门的寄存器如“程序-指令寄存器”(用名字如"PIR, "IR", "PR"等）
  5. 常按顺序的标定指令的列表：指令的有限列表I1 ... Im。在计数器机、随机存取机（RAM）和指针机的情况下，指令存储于有限状态机的TABLE中；因此这些模型是哈佛结构的例子。在RASP的情况下，程序存储在寄存器中；所以它是冯·诺伊曼结构的例子。
    通常像计算机程序，指令被按顺序列出；除非成功跳转否则缺省顺序是眼数值次序。有个例外是算盘（Lambek (1961), Minksy (1961)）计数器机模型——所有指令都有至少一个“下一个”指令标识符"z"，而条件分支有两个。（算盘模型组合了两个指令JZ接着DEC）：
    • 比如{ INC(r, z), JZDEC(r, ztrue, zfalse)}

参见

引用

  • 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.
  • John Hopcroft, Jeffrey Ullman（1979）. Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. 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.
  • Arnold 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. resp. Storage Modification Machines, in Theoretical Computer Science（1979）, pp. 36-37
  • 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=80422998”