用於形式邏輯和理論計算機科學中的計算模型，是暫存器機模型的最原始的子類。
基本介紹
- 中文名：計數器機
- 學科：計算機
簡介,兩計數器的機器是圖靈等價的,第1步:圖靈機可以用兩個棧來模擬,第2步:棧可以用兩個計數器模擬,第3步:四個計數器可以被兩個計數器模擬,
簡介
作為用於形式邏輯和理論計算機科學中的計算模型，計數器機是暫存器機模型的最原始的子類。
它只由如下組成：(i)一序列的一個或多個(唯一性)命名的“無界”暫存器(只包含一個單一無界正整數的暫存器)，(ii)假如到或減去自暫存器的叫做“計數器”的物件，(iii)讓計算機(人或機器)服從的(通常順序的)算術和控制指令的列表。
對於給定的計數器機模型，指令集是非常微小的，只有從 1 到 6 或 7 指令。所有模型都包含一些算術運算和至少一個“條件表達式”(IF-THEN-ELSE)。三個基本模型，每個都使用了三個指令，從下列指令中劃分出來(簡寫助記符是任意的):
停機(HALT)指令可以包含也可以不包含在模型中。
三個計數器機的計算能力是等價的 -- 一個模型的指令可以從其他模型的指令得出。都等價於圖靈機的計算能力(但只有用哥德爾數來編碼在計算器中的數據，否則它們的能力等價於原始遞歸函式)。由於它們的一元處理方式，計數器典型的要比圖靈機慢一個因子，它是在相比較的圖靈機使用的空間的指數。
計數器機模型還有一些其他的名字: Shepherdson-Sturgis 機, Minsky 機, 程式機, 算盤機, Lambek 機, 後繼機 等等。詳情參見計數器機模型。
兩計數器的機器是圖靈等價的
可以通過只有兩個計數器的機器模擬任何圖靈機。下面用三個步驟概述其證明。首先，圖靈機可以用裝備了兩個棧的有限狀態機(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，所以兩個機器有等價的能力。
