複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/寄存器機/4893538
複製
複製成功

寄存器機

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

目錄

  1. 1 簡介
  2. 2 定義
  3. 3 形式定義

寄存器機簡介

在文獻中至少可找到 4 個子類，下面按最原始到最類似計算機的次序列出:
計數器機 -- 最原始和精簡的模型。缺乏間接尋址。指令在按照哈佛結構的有限狀態機內。
指針機 -- 計數器機和 RAM 模型的混合。比這兩個模型更少共通更多抽象。指令在按照哈佛結構的有限狀態機內。
隨機存取機 (RAM) -- 帶有間接尋址和通常擴充的指令集。指令在按照哈佛結構的有限狀態機內。
隨機存取存儲程序機 (RASP) -- 帶有指令在其寄存器中的 RAM，類似於通用圖靈機；因此它是馮·諾伊曼結構的一個例子。但是不同於計算機的是這個模型是帶有有效無限個寄存器的“理想”機器。不象計算機甚至RISC計算機，指令集在指令數目上是非常精簡的。
任何正確定義的寄存器機都是圖靈等價的。計算速度嚴重倚賴於模型細節。 [1] 

寄存器機定義

在數理邏輯和理論計算機科學中，寄存器機（英語：Register machine），又譯為暫存器機，是以類似於使用圖靈機的方式使用的一類抽象機器。所有模型都是圖靈等價的。
寄存器機得名於它有一個或多個“寄存器”——替代了圖靈機的磁帶和磁頭，這個模型使用了多個唯一尋址的寄存器，每個都持有一個單一正整數。
在文獻中至少可找到4個子類，下面按最原始到最類似計算機的次序列出：
  • 計數器機——最原始和精簡的模型。缺乏間接尋址。指令在按照哈佛結構的有限狀態機內。
  • 指針機——計數器機和RAM模型的混合。比這兩個模型更少共通更多抽象。指令在按照哈佛結構的有限狀態機內。
  • 隨機存取機（RAM）——帶有間接尋址和通常擴充的指令集。指令在按照哈佛結構的有限狀態機內。
  • 隨機存取存儲程序機（RASP）——帶有指令在其寄存器中的RAM，類似於通用圖靈機；因此它是馮·諾伊曼結構的一個例子。但是不同於計算機的是這個模型是帶有有效無限個寄存器的“理想”機器。不像計算機甚至RISC計算機，指令集在指令數目上是非常精簡的。
任何正確定義的寄存器機都是圖靈等價的。計算速度嚴重倚賴於模型細節 [2] 

寄存器機形式定義

寄存器機構成如下：
  1. 無界數目的標定的、離散的、在寬度（容量）上無界的寄存器：有限（在某些模型中無限）的寄存器集合r0...rn，每個都有無限寬度並持有一個單一非負整數（0, 1, 2, ...）。寄存器可以做它們自己的算術，或者可以有也可以沒有一個或多個做算術的特殊寄存器，比如“累加器”或“地址寄存器”。
  2. 計數的籌碼或標碼——離散的、不可細分的唯一一類只適合這個模型的物件或標記。在最精簡的計數器機模型中，對每個算術指令只有一個物件/標記被要麼增加到要麼減少自它的位置/磁帶。在某些計數器機模型（比如Melzak（1961）, Minsky (1961))和多數RAM與RASP模型中，在“加法”、“減法”、“乘法”和“除法”這樣的指令中多於一個物件/標記可以增加或減少。某些模型有控制運算比如“複製”（也叫做“移動”、“裝載”、“存儲”）一個動作就從寄存器到寄存器移動一堆物件/標記。
  3. （非常）有限的指令集：指令可被分類為算術和控制。對指令集有一種限制：一個指令集必須允許這個模型是圖靈等價的，就是説它必須能夠計算任何偏遞歸函數：
    1. 算術：算術指令可以運算於所有寄存器上或只在特殊的寄存器上（比如累加器）。他們通常被按如下集合來選擇（但例外大量存在）：
    2. 控制：
    3. 寄存器尋址方法：
    4. 輸入輸出：
  4. 狀態寄存器：一個特殊的指令寄存器"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"等）
  5. 常按順序的標定指令的列表：指令的有限列表I1...Im。在計數器機、隨機存取機（RAM）和指針機的情況下，指令存儲於有限狀態機的TABLE中；因此這些模型是哈佛結構的例子。在RASP的情況下，程序存儲在寄存器中；所以它是馮·諾伊曼結構的例子。　　通常像計算機程序，指令被按順序列出；除非成功跳轉否則缺省順序是眼數值次序。有個例外是算盤（Lambek (1961), Minksy (1961)）計數器機模型——所有指令都有至少一個“下一個”指令標識符"z"，而條件分支有兩個。（算盤模型組合了兩個指令JZ接着DEC）：
    • 比如{ INC(r, z), JZDEC(r, ztrue, zfalse)} [2] 
參考資料
  • 1.    Marvin Minsky. Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines. Annals of Math. 1961, received August 15, 1960, 74: 437–455.
  • 2.    John C. Shepherdson and H. E. Sturgis（1961）received December 1961 Computability of Recursive Functions, Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".