计数器机

**計數器機**（英語：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. **無限數目的標定的、離散的、無界的暫存器**: 暫存器 _r_0 ... _r_n 的有限 (在模型模型中無限) 的集合，每個都持有一個單一非負無界整數 (0, 1, 2, ...)。暫存器做自己的算術；可以有也可以沒有一個或多個特殊暫存器比如「累加器」(詳情參見隨機存取機)。
2. **計數的籌碼或標碼** -- 只適合這個模型的一類離散的、不可細分的物件或標記。在最精簡的模型中，每個算術運算，只從它的位置 / 磁帶中增加或減少一個物件 / 標記。在某些模型中 (比如 Melzak (1961), Minsky (1961)) 在一個運算中可以增加或減少多於一個物件 / 標記。
3. 存儲 / 標識要執行的當前指令的**狀態暫存器**。這個暫存器是有限的並獨立於上述暫存器；所以計數器機模型是哈佛結構的例子
4. **標定的、順序指令的列表**: 指令 _I_0 ... _I_m 的有限列表。程序存儲 (有限狀態機的指令) 不在與暫存器同一個物理空間中。通常但不總是，像電腦程式，指令被按順序列出；除非跳轉成功，預設順序按數值次序繼續。在列表中的每個指令都來自 (非常) 小的集合，但是這個集合不包括間接尋址。歷史上最常見的指令超集，各個模型從中選出精簡集合形成它的適當子集 (適當就是能導致圖靈等價的機器):

　
: : {增加 (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，所以兩個機器有等價的能力。

## 參見

* 停機問題
* 指針機
* 波斯特 - 圖靈機
* 隨機存取機
* 暫存器機
* 圖靈機
* Wang B-machine

## 引用

* 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.  引文格式 1 維護：冗餘文本 (link) 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._

* 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.

## 外部連結

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