在数理逻辑和理论计算机科学中，寄存器机是以类似于使用图灵机的方式使用的一类抽象机。所有模型都是图灵等价的。寄存器机得名于它有一个或多个“寄存器” -- 替代了图灵机的磁带和磁头，这个模型使用了多个唯一寻址的寄存器，每个都持有一个单一正整数。

形式定义

参见

引用

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

计数器机 -- 最原始和精简的模型。缺乏间接寻址。指令在按照哈佛结构的有限状态机内。

指针机 -- 计数器机和 RAM 模型的混合。比这两个模型更少共通更多抽象。指令在按照哈佛结构的有限状态机内。

随机存取机 (RAM) -- 带有间接寻址和通常扩充的指令集。指令在按照哈佛结构的有限状态机内。

随机存取存储程序机 (RASP) -- 带有指令在其寄存器中的 RAM，类似于通用图灵机；因此它是冯·诺伊曼结构的一个例子。但是不同于计算机的是这个模型是带有有效无限个寄存器的“理想”机器。不象计算机甚至RISC计算机，指令集在指令数目上是非常精简的。

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

形式定义

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

寄存器机构成如下:

1 无界数目的标定的、离散的、在宽度(容量)上无界的寄存器:

有限(在某些模型中无限)的寄存器集合 '0 ... ''，每个都有无限宽度并持有一个单一非负整数 (0, 1, 2, ...)。寄存器可以做它们自己的算术，或者可以有也可以没有一个或多个做算术的特殊寄存器，比如“累加器”或“地址寄存器”。

2 计数的筹码或标码 -- 离散的、不可细分的唯一一类只适合这个模型的物件或标记。

在最精简的计数器机模型中，对每个算术指令只有一个物件/标记被要么增加到要么减少自它的位置/磁带。在某些计数器机模型(比如 Melzak (1961), Minsky (1961))和多数 RAM 与 RASP 模型中，在“加法”、“减法”、“乘法”和“除法”这样的指令中多于一个物件/标记可以增加或减少。某些模型有控制运算比如“复制”(也叫做“移动”、“装载”、“存储”)一个动作就从寄存器到寄存器移动一堆物件/标记。

3 (非常)有限的指令集:

指令可被分类 -- 3.1 算术和 3.2 控制。对指令集有一种限制: 一个指令集必须允许这个模型是图灵等价的，就是说它必须能够计算任何偏递归函数:

3.1 算术

算术指令可以运算于所有寄存器上或只在特殊的寄存器上(比如累加器)。他们通常被按如下集合来选择(但例外大量存在):

*计数器机: { 增加 (r), 减少 (r), 清零 (r) }

*精简 RAM, RASP: { 增加 (r), 减少 (r), 清零 (r), 装载立即常量 k, 加 (r1,r2), 真减 (r1,r2), 增加累加器, 减少累加器, 清除累加器, 加寄存器 r 的内容到累加器, 从累加器真减寄存器 r 的内容 }

*扩充 RAM, RASP: 所有精简指令加上: { 乘法, 除法, 各种布尔逐位运算 (左移位, 位测试, 等等)}

3.2 控制:

计数器机模型: 可选的 { 复制 (r1,r2) }

RAM 和 RASP 模型: 多数都有 { 复制 (r1,r2) }, 或 { 装载累加器从 r, 存储累加器到 r, 装载立即常量到累加器 }

所有模型: 至少一个跟随寄存器测试的条件“跳转”(分支，goto)，比如 { 零时跳转, 非零时跳转(就是，正时跳转), 等时跳转, 非等时跳转 }

所有模型可选的: { 无条件程序跳转 (goto) }

3.3 寄存器寻址方法:

计数器机: 没有间接寻址，在高度原子化的模型中可能有立即操作数

RAM 和 RASP: 可用间接寻址，典型的立即操作数

3.4 输入输出:

所有模型: 可选的

4 状态寄存器:

一个特殊的指令寄存器 "IR"，有限并独立于上述寄存器，它存储当前的要执行的指令和它在指令 TABLE(表格) 中的地址；这个寄存器和它的 TABLE 位于有限状态机内。

注释 #1: IR 是对于所有模型都是禁区。在 RAM 和 RASP 的情况下，为了确定一个寄存器的地址，模型可以选择要么 (i)在直接寻址的情况下 -- 地址通过 TABLE 指定而临时位于 IR 中，或 (ii) 在间接寻址的情况下 -- 寄存器的内容由 IR 的指令指定。

注释 #2: IR 不是 RASP (或常规计算机)的程序计数器(PC)。PC 只是类似累加器的另一个寄存器，只专门持有 RASP 的当前基于寄存器的指令的编号。所以 RASP 有两个“指令/程序”寄存器 -- (i) IR (有限状态自动机的指令寄存器) 和 (ii) PC (程序计数器) 用于位于寄存器中的程序。(同样于专门的 PC 寄存器，RASP 可以有专门的寄存器如“程序-指令寄存器”(用名字如 "PIR, "IR", "PR" 等)

5 通常按顺序的标定指令的列表:

指令的有限列表 '1 ... ''。在计数器机、随机存取机(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 Editio', 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 Computabilit'; 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 instrumen', reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Example', mcGraw-Hill Book Company, New York. ISBN 0070043574 .

Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machine', Journal of Computer Systems Science 7 (1973), 354-375.

Martin Davis (1958), Computability & Unsolvabilit', McGraw-Hill Book Company, Inc. New York.

Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Language', 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 Computatio', 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.

Stephen Kleene (1952), Introduction to Metamathematic', North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.

Donald Knuth (1968), The Art of Computer Programmin', 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 Abacu', 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 Metamathematic'.

Z. A. Melzak (1961, received 15 May 1961), An informal Arthmetical Approach to Computability and Computatio', 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."

*

In particular see chapter 11: Models Similar to Digital Computer' and chapter 14: Very Simple Bases for Computabilit'. 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 Function', 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 Rechenmaschin, Zeitschrift fur mathematische Logik und Grundlagen der Mathematik'5'' (1959), 366-379.

*Ershov, A. P. On operator algorithm', (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.

*Péter, Rózsa Graphschemata und rekursive Funktione', 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 Machine', 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 Machine', in Theoretical Computer Scienc' (1979), pp. 36-37

Peter van Emde Boas, Machine Models and Simulation' 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 0-444-88071-2 (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 Turins 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.