寄存器机

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

寄存器机构成如下：

1. 无界数目的标定的、离散的、在宽度（容量）上无界的寄存器：有限（在某些模型中无限）的寄存器集合r₀ ... r_n，每个都有无限宽度并持有一个单一非负整数（0, 1, 2, ...）。寄存器可以做它们自己的算术，或者可以有也可以没有一个或多个做算术的特殊寄存器，比如“累加器”或“地址寄存器”。
2. 计数的筹码或标码——离散的、不可细分的唯一一类只适合这个模型的物件或标记。在最精简的计数器机模型中，对每个算术指令只有一个物件/标记被要么增加到要么减少自它的位置/磁带。在某些计数器机模型（比如Melzak（1961）, Minsky (1961))和多数RAM与RASP模型中，在“加法”、“减法”、“乘法”和“除法”这样的指令中多于一个物件/标记可以增加或减少。某些模型有控制运算比如“复制”（也叫做“移动”、“装载”、“存储”）一个动作就从寄存器到寄存器移动一堆物件/标记。
3. （非常）有限的指令集：指令可被分类为算术和控制。对指令集有一种限制：一个指令集必须允许这个模型是图灵等价的，就是说它必须能够计算任何偏递归函数：
   1. 算术：算术指令可以运算于所有寄存器上或只在特殊的寄存器上（比如累加器）。他们通常被按如下集合来选择（但例外大量存在）：
      • 计数器机：{增加（r），减少（r），清零（r）}
      • 精简RAM, RASP：{增加（r），减少（r），清零（r），装载立即常量k，加（r₁,r₂），真减（r₁,r₂），增加累加器，减少累加器，清除累加器，加寄存器r的内容到累加器，从累加器真减寄存器r的内容}
      • 扩充RAM, RASP：所有精简指令加上：{乘法，除法，各种布尔逐位运算 (左移位，位测试，等等)}
   2. 控制：
      • 计数器机模型：可选的{复制（r₁,r₂）}
      • RAM和RASP模型：多数都有{复制（r₁,r₂）}，或{装载累加器从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. 常按顺序的标定指令的列表：指令的有限列表I₁ ... I_m。在计数器机、随机存取机（RAM）和指针机的情况下，指令存储于有限状态机的TABLE中；因此这些模型是哈佛结构的例子。在RASP的情况下，程序存储在寄存器中；所以它是冯·诺伊曼结构的例子。
   通常像计算机程序，指令被按顺序列出；除非成功跳转否则缺省顺序是眼数值次序。有个例外是算盘（Lambek (1961), Minksy (1961)）计数器机模型——所有指令都有至少一个“下一个”指令标识符"z"，而条件分支有两个。（算盘模型组合了两个指令JZ接着DEC）：
   • 比如{ INC(r, z), JZDEC(r, z_true, z_false)}

• 图灵机
• 停机问题
• 波斯特定理
• 克莱尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯纳–罗宾逊定理
• 跳跃逆转定理

• 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. 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. Stephen Kleene（1952）, Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. 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.  请检查|date=中的日期值 (帮助)
• Marvin Minsky. Computation: Finite and Infinite Machines 1st ed. Englewood Cliffs, N. J.: Prentice-Hall, Inc. 1967.  引文格式1维护：冗余文本 (link) 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. 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.