計(jì)數(shù)器機(jī)

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

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

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

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

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

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

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

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

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

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

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

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