暫存器機

在數理邏輯和理論計算機科學中，暫存器機是以類似於使用圖靈機的方式使用的一類抽象機。所有模型都是圖靈等價的。暫存器機得名於它有一個或多個“暫存器” -- 替代了圖靈機的磁帶和磁頭，這個模型使用了多個唯一定址的暫存器，每個都持有一個單一正整數。

基本介紹

• 中文名：暫存器機
• 外文名：Register machine
• 又稱：暫存器機
• 學科：電子工程

簡介

在文獻中至少可找到 4 個子類，下面按最原始到最類似計算機的次序列出:

計數器機 -- 最原始和精簡的模型。缺乏間接定址。指令在按照哈佛結構的有限狀態機內。

指針機 -- 計數器機和 RAM 模型的混合。比這兩個模型更少共通更多抽象。指令在按照哈佛結構的有限狀態機內。

隨機存取機 (RAM) -- 帶有間接定址和通常擴充的指令集。指令在按照哈佛結構的有限狀態機內。

隨機存取存儲程式機 (RASP) -- 帶有指令在其暫存器中的 RAM，類似於通用圖靈機；因此它是馮·諾伊曼結構的一個例子。但是不同於計算機的是這個模型是帶有有效無限個暫存器的“理想”機器。不象計算機甚至RISC計算機，指令集在指令數目上是非常精簡的。

任何正確定義的暫存器機都是圖靈等價的。計算速度嚴重倚賴於模型細節。

定義

在數理邏輯和理論計算機科學中，暫存器機（英語：Register machine），又譯為暫存器機，是以類似於使用圖靈機的方式使用的一類抽象機器。所有模型都是圖靈等價的。

暫存器機得名於它有一個或多個“暫存器”——替代了圖靈機的磁帶和磁頭，這個模型使用了多個唯一定址的暫存器，每個都持有一個單一正整數。

在文獻中至少可找到4個子類，下面按最原始到最類似計算機的次序列出：

• 計數器機——最原始和精簡的模型。缺乏間接定址。指令在按照哈佛結構的有限狀態機內。
• 指針機——計數器機和RAM模型的混合。比這兩個模型更少共通更多抽象。指令在按照哈佛結構的有限狀態機內。
• 隨機存取機（RAM）——帶有間接定址和通常擴充的指令集。指令在按照哈佛結構的有限狀態機內。
• 隨機存取存儲程式機（RASP）——帶有指令在其暫存器中的RAM，類似於通用圖靈機；因此它是馮·諾伊曼結構的一個例子。但是不同於計算機的是這個模型是帶有有效無限個暫存器的“理想”機器。不像計算機甚至RISC計算機，指令集在指令數目上是非常精簡的。

任何正確定義的暫存器機都是圖靈等價的。計算速度嚴重倚賴於模型細節

形式定義

暫存器機構成如下：

1. 無界數目的標定的、離散的、在寬度（容量）上無界的暫存器：有限（在某些模型中無限）的暫存器集合r₀...r_n，每個都有無限寬度並持有一個單一非負整數（0, 1, 2, ...）。暫存器可以做它們自己的算術，或者可以有也可以沒有一個或多個做算術的特殊暫存器，比如“累加器”或“地址暫存器”。
2. 計數的籌碼或標碼——離散的、不可細分的唯一一類只適合這個模型的物件或標記。在最精簡的計數器機模型中，對每個算術指令只有一個物件/標記被要么增加到要么減少自它的位置/磁帶。在某些計數器機模型（比如Melzak（1961）, Minsky (1961))和多數RAM與RASP模型中，在“加法”、“減法”、“乘法”和“除法”這樣的指令中多於一個物件/標記可以增加或減少。某些模型有控制運算比如“複製”（也叫做“移動”、“裝載”、“存儲”）一個動作就從暫存器到暫存器移動一堆物件/標記。
3. （非常）有限的指令集：指令可被分類為算術和控制。對指令集有一種限制：一個指令集必須允許這個模型是圖靈等價的，就是說它必須能夠計算任何偏遞歸函式：
4. 所有模型：可選的
5. 計數器機：沒有間接定址，在高度原子化的模型中可能有立即運算元
6. RAM和RASP：可用間接定址，典型的立即運算元
7. 計數器機模型：可選的{複製（r₁,r₂）}
8. RAM和RASP模型：多數都有{複製（r₁,r₂）}，或{裝載累加器從r，存儲累加器到r，裝載立即常量到累加器}
9. 所有模型：至少一個跟隨暫存器測試的條件“跳轉”（分支，goto），比如{零時跳轉，非零時跳轉（就是，正時跳轉），等時跳轉，非等時跳轉}
10. 所有模型可選的：{無條件程式跳轉（goto）}
11. 計數器機：{增加（r），減少（r），清零（r）}
12. 精簡RAM, RASP：{增加（r），減少（r），清零（r），裝載立即常量k，加（r₁,r₂），真減（r₁,r₂），增加累加器，減少累加器，清除累加器，加暫存器r的內容到累加器，從累加器真減暫存器r的內容}
13. 擴充RAM, RASP：所有精簡指令加上：{乘法，除法，各種布爾逐位運算 (左移位，位測試，等等)}
14. 算術：算術指令可以運算於所有暫存器上或只在特殊的暫存器上（比如累加器）。他們通常被按如下集合來選擇（但例外大量存在）：
15. 控制：
16. 暫存器定址方法：
17. 輸入輸出：

狀態暫存器：一個特殊的指令暫存器"IR"，有限並獨立於上述暫存器，它存儲當前的要執行的指令和它在指令TABLE（表格）中的地址；這個暫存器和它的TABLE位於有限狀態機內。

• IR是對於所有模型都是禁區。在RAM和RASP的情況下，為了確定一個暫存器的地址，模型可以選擇要么（i）在直接定址的情況下——地址通過TABLE指定而臨時位於IR中，或（ii）在間接定址的情況下——暫存器的內容由IR的指令指定。
• IR不是RASP（或常規計算機）的程式計數器（PC）。PC只是類似累加器的另一個暫存器，只專門持有RASP的當前基於暫存器的指令的編號。所以RASP有兩個“指令/程式”暫存器——（i）IR（有限狀態自動機的指令暫存器）和（ii）PC（程式計數器）用於位於暫存器中的程式。（同樣於專門的PC暫存器，RASP可以有專門的暫存器如“程式-指令暫存器”(用名字如"PIR, "IR", "PR"等）

常按順序的標定指令的列表：指令的有限列表I₁...I_m。在計數器機、隨機存取機（RAM）和指針機的情況下，指令存儲於有限狀態機的TABLE中；因此這些模型是哈佛結構的例子。在RASP的情況下，程式存儲在暫存器中；所以它是馮·諾伊曼結構的例子。
通常像電腦程式，指令被按順序列出；除非成功跳轉否則預設順序是眼數值次序。有個例外是算盤（Lambek (1961), Minksy (1961)）計數器機模型——所有指令都有至少一個“下一個”指令標識符"z"，而條件分支有兩個。（算盤模型組合了兩個指令JZ接著DEC）：

• 比如{ INC(r, z), JZDEC(r, z_true, z_false)}