寄存器机

在數理邏輯和理論計算機科學中，**暫存器機**（英語：Register machine），又譯為**暫存器機**，是以類似於使用圖靈機的方式使用的一類抽象機器。所有模型都是圖靈等價的。

暫存器機得名於它有一個或多個「暫存器」—— 替代了圖靈機的磁帶和磁頭，這個模型使用了**多個唯一尋址的暫存器**，每個都持有一個單一正整數。

在文獻中至少可找到 4 個子類，下面按最原始到最類似計算機的次序列出：

* 計數器機 —— 最原始和精簡的模型。缺乏間接尋址。指令在按照哈佛結構的有限狀態機內。
* 指針機 —— 計數器機和 RAM 模型的混合。比這兩個模型更少共通更多抽象。指令在按照哈佛結構的有限狀態機內。
* 隨機存取機（RAM）—— 帶有間接尋址和通常擴充的指令集。指令在按照哈佛結構的有限狀態機內。
* 隨機存取存儲程序機（RASP）—— 帶有指令在其暫存器中的 RAM，類似於通用圖靈機；因此它是馮・諾伊曼結構的一個例子。但是不同於計算機的是這個模型是帶有有效無限個暫存器的「理想」機器。不像計算機甚至 RISC 計算機，指令集在指令數目上是非常精簡的。

任何正確定義的暫存器機都是圖靈等價的。計算速度嚴重倚賴於模型細節。

## 形式定義

　
: _沒有標準術語；每個作者都以自己的助記符或符號下定義。_

暫存器機構成如下：

1. **無界數目的標定的、離散的、在寬度（容量）上無界的暫存器**：有限（在某些模型中無限）的暫存器集合 _r_0 ... _r_n，每個都有無限寬度並持有一個單一非負整數（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. **常按順序的標定指令的列表：**指令的有限列表 _I_1 ... _I_m。在計數器機、隨機存取機（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.  引文格式 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. 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.

## 外部連結

* 埃里克・韋斯坦因. Register machine. MathWorld.
* Igblan - Minsky Register Machines（頁面存檔備份，存於網際網路檔案館）