原始图灵机上的操作的汇编语言等价物是什么？

Question

如果采用原始图灵机定义如下：

...无限的内存容量 以无穷大的形式获得 胶带已标记出来 分成正方形，每个正方形上都可以打印一个符号。随时 有 机器中的一个符号；它称为扫描符号。机器 可以改变 扫描的符号及其行为部分取决于 符号，但是 磁带上其他地方的符号不会影响磁带的行为 机器。然而， 磁带可以在机器中来回移动，这是 中的一个 机器的基本操作。磁带上的任何符号都可能 所以 最终有一局。 （图灵，1948 年，第 61 页）

如果您想将这些操作映射到能够解释汇编程序/二进制指令的处理器上完成的操作 - 将映射哪些操作？

（我知道这个问题固有的从图灵机到冯诺依曼机的跳跃）

Answer 1

阅读您所写的内容，我想说您只需要：

• 直接增量指令（添加到当前磁带位置）
• 间接增量指令（移动磁带）
• 磁带位置值的某些操作

响应当前 类似于 ARM 的汇编，例如，如果您有 R0 包含磁带上的地址，您应该只需要

ADDS r0, r0, #1 ;moves the tape forward
ADDS r0, r0, #-1 ;moves the tape backwards
ADDS [r0], [r0], #1 ;increments the value 'pointed by' the tape
ADDS [r0], [r0], #-1 ;decrements the value 'pointed by' the tape

然后，在当前符号假定某些值的情况下分支执行操作

BEQ Somewhere

这或多或少是 Brainfuck 的工作方式。

Answer 2

<块引用>

以无限带子的形式获得的无限存储容量，带子被标记为正方形，每个正方形上都可以打印一个符号。

我们称之为 int 数组。 int[] 符号

<块引用>

机器中任何时刻都有一个符号；它称为扫描符号。

int inxSym;
int scannedSymbol = Symbols[inxSym]; 

（在 CPU 级别，这被称为“主存储器”或在现代系统中被称为“程序段”。

<块引用>

机器可以改变扫描的符号

Symbols[inxSym] = newSymbol;

<块引用>

其行为部分由该符号决定，

switch(scannedSymbol) {....}

（在 CPU 级别，这是“执行指令”。没有操作代码告诉它这样做；这只是 CPU 所做的事情。）

<块引用>

但磁带上其他地方的符号不会影响机器的行为。

那里没什么可做的。

<块引用>

但是，磁带可以在机器中来回移动，这是机器的基本操作之一。

  ++inxSym;
  --inxSym
   inxSym +=10;
 // etc.

（在CPU级别，这是用JMP操作码处理的）

Answer 3

由于图灵机完全由磁带上字母表的定义和正在读取磁带的状态机决定，因此将语言设置为表格是最有意义的。

我们将状态称为 Qn，字母表字符 Ai 从磁带。机器从转换表 an 确定下一个状态，并将 Ao 写入磁带并沿 D : L/R 方向移动。

来定义机器

然后可以通过写入其QnAi → 。 QmAoD

来自维基百科的添加程序将变为

QbA0 -> QbA1R
QbA1 -> QbA1R
Q0A- -> Q0A-L
Q1A0 -> QrA-L
Q1A1 -> QaA-L
Q1A- -> QrA-L 

接受状态和拒绝状态。这是非常紧凑且可读的转移矩阵表示。

当然，这是假设磁带上的内容被解释为数据。但是没有什么可以阻止任何人创建转换矩阵以使状态机解释磁带上的指令。

为了实现这一点，您在左侧有一个元组，在右侧有一个三元组，因此这映射到二维数组中的查找来读取三元组。用磁带上字符的#bits 改变状态并将它们粘在一起。相乘（好吧，另一个移位运算）为三元组腾出空间，并将其用作表中的偏移量来读取三元组。

将新状态写入状态寄存器，磁带上的字符，如果在三元组中找到数据，则增加递减，或者停止那里没有数据。组装起来应该很有趣。

Answer 4

我不确定这是否 100% 正确，但它会是这样的：

• 图灵机头（在给定时间“扫描”符号的头）将与指令指针等效。
• 因此，指令获取和解码阶段相当于扫描符号的解释。
• 执行将被表示为更复杂的 TM 操作序列。让我们以内存写入为例：将磁头移动到给定的内存位置，将数据从寄存器移动到该位置，返回到 IP 寄存器寻址的位置并递增它。

注意，磁头运动控制相当于流程控制指令，即JMP及其兄弟指令。

另请注意，寄存器是经典 TM 的重要补充。它们可以表示为磁带上的特殊单元（或单元组）或单独的实体。有关更多详细信息，请参阅注册机器。

最后，值得一提的是，虽然这非常适合冯·诺依曼架构，但哈佛架构使用两种不同的磁带，一种用于指令，一种用于数据。