寄存器机

在数理逻辑和理论计算机科学中，寄存器机是以类似于使用图灵机的方式使用的一类抽象机。所有模型都是图灵等价的。寄存器机得名于它有一个或多个“寄存器” -- 替代了图灵机的磁带和磁头，这个模型使用了多个唯寻址的寄存器，每个都持有一个单一正整数。

寄存器机详细介绍

在数理逻辑和理论计算机科学中，寄存器机是以类似于使用图灵机的方式使用的一类抽象机。所有模型都是图灵等价的。寄存器机得名于它有一个或多个“寄存器” -- 替代了图灵机的磁带和磁头，这个模型使用了多个唯寻址的寄存器，每个都持有一个单一正整数。

寄存器机简介

在文献中至少可找到 4 个子类，下面按最原始到最类似计算机的次序列出:

计数器机 -- 最原始和精简的模型。缺乏间接寻址。指令在按照哈佛结构的有限状态机内。

指针机 -- 计数器机和 RAM 模型的混合。比这两个模型更少共通更多抽象。指令在按照哈佛结构的有限状态机内。

随机存取机 (RAM) -- 带有间接寻址和通常扩充的指令集。指令在按照哈佛结构的有限状态机内。

随机存取存储程序机 (RASP) -- 带有指令在其寄存器中的 RAM，类似于通用图灵机；因此它是冯·诺伊曼结构的一个例子。但是不同于计算机的是这个模型是带有有效无限个寄存器的“理想”机器。不象计算机甚至RISC计算机，指令集在指令数目上是非常精简的。

任何正确定义的寄存器机都是图灵等价的。计算速度严重倚赖于模型细节。

寄存器机定义

在数理逻辑和理论计算机科学中，寄存器机（英语：Register machine），又译为暂存器机，是以类似于使用图灵机的方式使用的一类抽象机器。所有模型都是图灵等价的。

寄存器机得名于它有一个或多个“寄存器”——替代了图灵机的磁带和磁头，这个模型使用了多个唯一寻址的寄存器，每个都持有一个单一正整数。

在文献中至少可找到4个子类，下面按最原始到最类似计算机的次序列出：

任何正确定义的寄存器机都是图灵等价的。计算速度严重倚赖于模型细节

寄存器机形式定义

寄存器机构成如下：

无界数目的标定的、离散的、在宽度（容量）上无界的寄存器：有限（在某些模型中无限）的寄存器集合r₀...r_n，每个都有无限宽度并持有一个单一非负整数（0, 1, 2, ...）。寄存器可以做它们自己的算术，或者可以有也可以没有一个或多个做算术的特殊寄存器，比如“累加器”或“地址寄存器”。
计数的筹码或标码——离散的、不可细分的唯一一类只适合这个模型的物件或标记。在最精简的计数器机模型中，对每个算术指令只有一个物件/标记被要么增加到要么减少自它的位置/磁带。在某些计数器机模型（比如Melzak（1961）, Minsky (1961))和多数RAM与RASP模型中，在“加法”、“减法”、“乘法”和“除法”这样的指令中多于一个物件/标记可以增加或减少。某些模型有控制运算比如“复制”（也叫做“移动”、“装载”、“存储”）一个动作就从寄存器到寄存器移动一堆物件/标记。
（非常）有限的指令集：指令可被分类为算术和控制。对指令集有一种限制：一个指令集必须允许这个模型是图灵等价的，就是说它必须能够计算任何偏递归函数：
算术：算术指令可以运算于所有寄存器上或只在特殊的寄存器上（比如累加器）。他们通常被按如下集合来选择（但例外大量存在）：
控制：
寄存器寻址方法：
输入输出：

状态寄存器：一个特殊的指令寄存器"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)}