寄存器機(jī)參見

圖靈機(jī)

停機(jī)問題

沒有標(biāo)準(zhǔn)術(shù)語;每個(gè)作者都以自己的助記符或符號(hào)下定義。

寄存器機(jī)構(gòu)成如下:

1 無界數(shù)目的標(biāo)定的、離散的、在寬度(容量)上無界的寄存器:

有限(在某些模型中無限)的寄存器集合 '0 ... ''，每個(gè)都有無限寬度并持有一個(gè)單一非負(fù)整數(shù) (0, 1, 2, ...)。寄存器可以做它們自己的算術(shù)，或者可以有也可以沒有一個(gè)或多個(gè)做算術(shù)的特殊寄存器，比如"累加器"或"地址寄存器"。

2 計(jì)數(shù)的籌碼或標(biāo)碼 -- 離散的、不可細(xì)分的唯一一類只適合這個(gè)模型的物件或標(biāo)記。

在最精簡(jiǎn)的計(jì)數(shù)器機(jī)模型中，對(duì)每個(gè)算術(shù)指令只有一個(gè)物件/標(biāo)記被要么增加到要么減少自它的位置/磁帶。在某些計(jì)數(shù)器機(jī)模型(比如 Melzak (1961), Minsky (1961))和多數(shù) RAM 與 RASP 模型中，在"加法"、"減法"、"乘法"和"除法"這樣的指令中多于一個(gè)物件/標(biāo)記可以增加或減少。某些模型有控制運(yùn)算比如"復(fù)制"(也叫做"移動(dòng)"、"裝載"、"存儲(chǔ)")一個(gè)動(dòng)作就從寄存器到寄存器移動(dòng)一堆物件/標(biāo)記。

3 (非常)有限的指令集:

指令可被分類 -- 3.1 算術(shù)和 3.2 控制。對(duì)指令集有一種限制: 一個(gè)指令集必須允許這個(gè)模型是圖靈等價(jià)的，就是說它必須能夠計(jì)算任何偏遞歸函數(shù):

3.1 算術(shù)

算術(shù)指令可以運(yùn)算于所有寄存器上或只在特殊的寄存器上(比如累加器)。他們通常被按如下集合來選擇(但例外大量存在):

*計(jì)數(shù)器機(jī): { 增加 (r), 減少 (r), 清零 (r) }

*精簡(jiǎn) RAM, RASP: { 增加 (r), 減少 (r), 清零 (r), 裝載立即常量 k, 加 (r1,r2), 真減 (r1,r2), 增加累加器, 減少累加器, 清除累加器, 加寄存器 r 的內(nèi)容到累加器, 從累加器真減寄存器 r 的內(nèi)容 }

*擴(kuò)充 RAM, RASP: 所有精簡(jiǎn)指令加上: { 乘法, 除法, 各種布爾逐位運(yùn)算 (左移位, 位測(cè)試, 等等)}

3.2 控制:

計(jì)數(shù)器機(jī)模型: 可選的 { 復(fù)制 (r1,r2) }

RAM 和 RASP 模型: 多數(shù)都有 { 復(fù)制 (r1,r2) }, 或 { 裝載累加器從 r, 存儲(chǔ)累加器到 r, 裝載立即常量到累加器 }

所有模型: 至少一個(gè)跟隨寄存器測(cè)試的條件"跳轉(zhuǎn)"(分支，goto)，比如 { 零時(shí)跳轉(zhuǎn), 非零時(shí)跳轉(zhuǎn)(就是，正時(shí)跳轉(zhuǎn)), 等時(shí)跳轉(zhuǎn), 非等時(shí)跳轉(zhuǎn) }

所有模型可選的: { 無條件程序跳轉(zhuǎn) (goto) }

3.3 寄存器尋址方法:

計(jì)數(shù)器機(jī): 沒有間接尋址，在高度原子化的模型中可能有立即操作數(shù)

RAM 和 RASP: 可用間接尋址，典型的立即操作數(shù)

3.4 輸入輸出:

所有模型: 可選的

4 狀態(tài)寄存器:

一個(gè)特殊的指令寄存器 "IR"，有限并獨(dú)立于上述寄存器，它存儲(chǔ)當(dāng)前的要執(zhí)行的指令和它在指令 TABLE(表格) 中的地址;這個(gè)寄存器和它的 TABLE 位于有限狀態(tài)機(jī)內(nèi)。

注釋 #1: IR 是對(duì)于所有模型都是禁區(qū)。在 RAM 和 RASP 的情況下，為了確定一個(gè)寄存器的地址，模型可以選擇要么 (i)在直接尋址的情況下 -- 地址通過 TABLE 指定而臨時(shí)位于 IR 中，或 (ii) 在間接尋址的情況下 -- 寄存器的內(nèi)容由 IR 的指令指定。

注釋 #2: IR 不是 RASP (或常規(guī)計(jì)算機(jī))的程序計(jì)數(shù)器(PC)。PC 只是類似累加器的另一個(gè)寄存器，只專門持有 RASP 的當(dāng)前基于寄存器的指令的編號(hào)。所以 RASP 有兩個(gè)"指令/程序"寄存器 -- (i) IR (有限狀態(tài)自動(dòng)機(jī)的指令寄存器) 和 (ii) PC (程序計(jì)數(shù)器) 用于位于寄存器中的程序。(同樣于專門的 PC 寄存器，RASP 可以有專門的寄存器如"程序-指令寄存器"(用名字如 "PIR, "IR", "PR" 等)

5 通常按順序的標(biāo)定指令的列表:

指令的有限列表 '1 ... ''。在計(jì)數(shù)器機(jī)、隨機(jī)存取機(jī)(RAM)和指針機(jī)的情況下，指令存儲(chǔ)于有限狀態(tài)機(jī)的 TABLE 中;因此這些模型是哈佛結(jié)構(gòu)的例子。在 RASP 的情況下，程序存儲(chǔ)在寄存器中;所以它是馮·諾伊曼結(jié)構(gòu)的例子。

通常像計(jì)算機(jī)程序，指令被按順序列出;除非成功跳轉(zhuǎn)否則缺省順序是眼數(shù)值次序。有個(gè)例外是算盤(Lambek (1961), Minksy (1961))計(jì)數(shù)器機(jī)模型 -- 所有指令都有至少一個(gè)"下一個(gè)"指令標(biāo)識(shí)符 "z"，而條件分支有兩個(gè)。(算盤模型組合了兩個(gè)指令 JZ 接著 DEC):

比如 { INC ( r, z ), JZDEC ( r, ztrue, zfalse ) }.

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

它只由如下組成:(i)一序列的一個(gè)或多個(gè)(唯一性)命名的"無界"寄存器(只包含一個(gè)單一無界正整數(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è)指令，從下列指令中劃分出來(簡(jiǎn)寫助記符是任意的):

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

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

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