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