寄存器机
维基百科,自由的 encyclopedia
在数理逻辑和理论计算机科学中,寄存器机(英语:Register machine),又译为暂存器机,是以类似于使用图灵机的方式使用的一类抽象机器。所有模型都是图灵等价的。
寄存器机得名于它有一个或多个“寄存器”——替代了图灵机的磁带和磁头,这个模型使用了多个唯一寻址的寄存器,每个都持有一个单一正整数。
在文献中至少可找到4个子类,下面按最原始到最类似计算机的次序列出:
- 计数器机——最原始和精简的模型。缺乏间接寻址。指令在按照哈佛结构的有限状态机内。
- 指针机——计数器机和RAM模型的混合。比这两个模型更少共通更多抽象。指令在按照哈佛结构的有限状态机内。
- 随机存取机(RAM)——带有间接寻址和通常扩充的指令集。指令在按照哈佛结构的有限状态机内。
- 随机存取存储程序机(RASP)——带有指令在其寄存器中的RAM,类似于通用图灵机;因此它是冯·诺伊曼结构的一个例子。但是不同于计算机的是这个模型是带有有效无限个寄存器的“理想”机器。不像计算机甚至RISC计算机,指令集在指令数目上是非常精简的。
任何正确定义的寄存器机都是图灵等价的。计算速度严重倚赖于模型细节。