寄存器機

圖靈機

停機問題

沒有標準術語;每個作者都以自己的助記符或符號下定義。

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

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

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

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

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

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

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

3.1 算術

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

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

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

*擴充 RAM, RASP: 所有精簡指令加上: { 乘法, 除法, 各種布爾逐位運算 (左移位, 位測試, 等等)}

3.2 控制:

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

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

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

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

3.3 寄存器尋址方法:

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

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

3.4 輸入輸出:

所有模型: 可選的

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

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

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

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

5 通常按順序的標定指令的列表:

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

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

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

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

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

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

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

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

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