計數(shù)器機形式定義

計數(shù)器機構(gòu)成如下:

作為用于形式邏輯和理論計算機科學中的計算模型，計數(shù)器機是寄存器機模型的最原始的子類。

它只由如下組成:(i)一序列的一個或多個(唯一性)命名的"無界"寄存器(只包含一個單一無界正整數(shù)的寄存器)，(ii)假如到或減去自寄存器的叫做"計數(shù)器"的物件，(iii)讓計算機(人或機器)服從的(通常順序的)算術(shù)和控制指令的列表。

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

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

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

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

可以通過只有兩個計數(shù)器的機器模擬任何圖靈機。下面用三個步驟概述其證明。首先，圖靈機可以用裝備了兩個棧的有限狀態(tài)機(FSM)來模擬。接著，兩個?？梢杂盟膫€計數(shù)器模擬。最后，四個計數(shù)器可以用兩個計數(shù)器模擬。

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

包含零和一的?？梢杂脙蓚€計數(shù)器模擬，當在棧上的位被認為表示二進制數(shù)的時候，而棧頂是最低位。壓入零到棧頂?shù)葍r于雙倍這個數(shù)。壓入一到棧頂?shù)葍r于雙倍并加 1。彈出等價于除以 2，這里的余數(shù)是彈出的位。兩個計數(shù)器可以模擬一個棧，一個計數(shù)器持有其二進制表示表示在棧上的位的數(shù)，而另一個計數(shù)器用做暫存器。要雙倍在第一個寄存器內(nèi)的數(shù)，F(xiàn)SM 可以初始化第二個計數(shù)器為零，接著重復減少第一計數(shù)器一次而增加第二個計數(shù)器兩次。繼續(xù)直到第一個寄存器到達零。在這一點上，第二個寄存器將持有雙倍的這個數(shù)。減半通過減少一個計數(shù)器兩次而增加另一個一次，重復知道第一個計數(shù)器到達零來實現(xiàn)。余數(shù)可以通過它在偶數(shù)或奇數(shù)次嘗試后結(jié)束來確定。

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

作為結(jié)果，帶有兩個計數(shù)器的 FSM 可以模擬四個計數(shù)器，依次模擬兩個棧，再次模擬圖靈機。所以，F(xiàn)SM 加上兩個計數(shù)器至少有圖靈機一樣的能力。圖靈機可以輕易的模擬帶有兩個計數(shù)器的 FSM，所以兩個機器有等價的能力。