跳至內容

寄存器機

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書

在數理邏輯和理論計算機科學中，寄存器機（英語：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」