跳至內容

計數器機

維基百科，自由的百科全書

計數器機（英語：Counter machine）是一種抽象機器，作為用於形式邏輯和理論計算機科學中的計算模型，計數器機是寄存器機模型的最原始的子類。 它只由如下組成：(i)一序列的一個或多個(唯一性)命名的「無界」寄存器(只包含一個單一無界正整數的寄存器)，(ii)假如到或減去自寄存器的叫做「計數器」的物件，(iii)讓計算機(人或機器)服從的(通常順序的)算術和控制指令的列表。

對於給定的計數器機模型，指令集是非常微小的，只有從 1 到 6 或 7 指令。所有模型都包含一些算術運算和至少一個「條件表達式」(IF-THEN-ELSE)。三個基本模型，每個都使用了三個指令，從下列指令中劃分出來(簡寫助記符是任意的):

  • CLR ( r ): 清除(CLeaR)寄存器 'r' [清空計數器 'r']
  • INC ( r ): 增加(INCrement)寄存器 'r' 的內容
  • DEC ( r ): 減少(DECrement)寄存器 'r' 的內容
  • CPY ( rj, rk ): 複製(CoPY)寄存器 rj 的內容到寄存器 rk，保持 rj 的內容不動
  • JZ ( r, z ): 如果寄存器 'r' 的內容為零(Zero)，則跳轉(Jump)到標記為 'z' 的指令，否則繼續按順序執行
  • JE ( rj, rk, z ): 如果寄存器 rj 的內容等於(Equal)寄存器 rk 的內容，則跳轉(Jump)到標記為 'z' 的指令，否則繼續按順序執行，
  • 集合 (1): { INC ( r ), DEC ( r ), JZ ( r, z ) }, ( Minsky (1961, 1967), Lambek (1961) )
  • 集合 (2): { CLR ( r ), INC ( r ), JE ( rj, rk, z ) }, ( Ershov (1958), Peter (1958) 由 Shepherdson-Sturgis (1964) 解釋; Minsky (1967); Schönhage (1980) )
  • 集合 (3): { INC ( r ), CPY ( rj, rk ), JE ( rj, rk, z ) }, ( Elgot-Robinson (1964), Minsky (1967) )。

停機(HALT)指令可以包含也可以不包含在模型中。

三個計數器機的計算能力是等價的 -- 一個模型的指令可以從其他模型的指令得出。都等價於圖靈機的計算能力(但只有用哥德爾數來編碼在計算器中的數據，否則它們的能力等價於原始遞歸函數)。由於它們的一元處理方式，計數器典型的要比圖靈機慢一個因子，它是在相比較的圖靈機使用的空間的指數。

計數器機模型還有一些其他的名字: Shepherdson-Sturgis 機, Minsky 機, 程序機, 算盤機, Lambek 機, 後繼機 等等。詳情參見計數器機模型。

形式定義

計數器機構成如下:

  1. 無限數目的標定的、離散的、無界的寄存器: 寄存器 r0 ... rn 的有限(在模型模型中無限)的集合，每個都持有一個單一非負無界整數 (0, 1, 2, ...)。寄存器做自己的算術；可以有也可以沒有一個或多個特殊寄存器比如「累加器」(詳情參見隨機存取機)。
  2. 計數的籌碼或標碼 -- 只適合這個模型的一類離散的、不可細分的物件或標記。在最精簡的模型中，每個算術運算，只從它的位置/磁帶中增加或減少一個物件/標記。在某些模型中(比如 Melzak (1961), Minsky (1961)) 在一個運算中可以增加或減少多於一個物件/標記。
  3. 存儲/標識要執行的當前指令的狀態寄存器。這個寄存器是有限的並獨立於上述寄存器；所以計數器機模型是哈佛結構的例子
  4. 標定的、順序指令的列表: 指令 I0 ... Im 的有限列表。程序存儲(有限狀態機的指令)不在與寄存器同一個物理空間中。通常但不總是，像電腦程式，指令被按順序列出；除非跳轉成功，缺省順序按數值次序繼續。在列表中的每個指令都來自(非常)小的集合，但是這個集合不包括間接尋址。歷史上最常見的指令超集，各個模型從中選出精簡集合形成它的適當子集(適當就是能導致圖靈等價的機器):
{ 增加 (r)，減少 (r)，清除 (r)；複製 (rj,rk)，條件跳轉到指令 Iz 如果 r=0，條件跳轉如果 rj=rk，無條件跳轉，HALT }
某些模型要麼進一步把上述某些指令原子化為無參數指令，要麼組合它們為一個單一指令，比如對「減少」前導上零條件時跳轉「JZ ( r, z )」。指令的原子化或包含常規指令不導致計算能力的變化，因為在一個變體中的任何程序都可以直接轉換成另一個變體中的程序。

兩計數器的機器是圖靈等價的

可以通過只有兩個計數器的機器模擬任何圖靈機。下面用三個步驟概述其證明。首先，圖靈機可以用裝備了兩個棧的有限狀態機(FSM)來模擬。接着，兩個棧可以用四個計數器模擬。最後，四個計數器可以用兩個計數器模擬。

第 1 步: 圖靈機可以用兩個棧來模擬

圖靈機由一個 FSM 和一個最初填充零的無限磁帶組成，機器可以在其上寫一和零。在任何時候，這個機器的讀/寫磁頭指向在磁帶上的一個單元。這個磁頭概念上在這一點上把磁帶分為兩半。每一半磁帶都可以被當作棧，棧頂是最靠近讀/寫磁頭的單元，而棧底與磁頭有些距離，而在磁帶上的所有零都超出了棧底。因此圖靈機可以用 FSM 加上兩個棧來模擬。左或右移動磁頭等價於從一個棧彈出一位並壓入到另一個棧中。寫等價於在壓入一位之前改變它。

第 2 步: 棧可以用兩個計數器模擬

包含零和一的棧可以用兩個計數器模擬，當在棧上的位被認為表示二進制數的時候，而棧頂是最低位。壓入零到棧頂等價於雙倍這個數。壓入一到棧頂等價於雙倍並加 1。彈出等價於除以 2，這裏的餘數是彈出的位。兩個計數器可以模擬一個棧，一個計數器持有其二進制表示表示在棧上的位的數，而另一個計數器用做暫存器。要雙倍在第一個寄存器內的數，FSM 可以初始化第二個計數器為零，接着重複減少第一計數器一次而增加第二個計數器兩次。繼續直到第一個寄存器到達零。在這一點上，第二個寄存器將持有雙倍的這個數。減半通過減少一個計數器兩次而增加另一個一次，重複知道第一個計數器到達零來實現。餘數可以通過它在偶數或奇數次嘗試後結束來確定。

第 3 步: 四個計數器可以被兩個計數器模擬

同上，一個計數器用做暫存器。另一個真實計數器持有一個整數，它的素因數分解是 2a3b5c7d。指數 a, b, c 和 d 可被看作要被模擬的四個虛擬計數器。如果真實計數器被置零接着增加一次，則等價於把所有寄存器都置零。如果真實計數器被雙倍，則等價於增加 a，而如果它被減半，則等價於減少 a。通過類似的過程，它可以乘以或除以 3，這等價於增加或減少 b。類似的，c 和 d 可以增加或減少。要檢查一個虛擬計數器比如 c 是否等於零，只要把實際計數器除以 5，看餘數是什麼，接着乘以 5 並加回餘數。這保持真實計數器不變。餘數將是非零若且唯若 c 是零。

作為結果，帶有兩個計數器的 FSM 可以模擬四個計數器，依次模擬兩個棧，再次模擬圖靈機。所以，FSM 加上兩個計數器至少有圖靈機一樣的能力。圖靈機可以輕易的模擬帶有兩個計數器的 FSM，所以兩個機器有等價的能力。

參見

引用

  • 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.
  • Hopcroft, John; Jeffrey Ullman. Introduction to Automata Theory, Languages and Computation 1st ed. Reading Mass: Addison-Wesley. 1979. 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.
  • A. 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.
  • 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=80044634"