7

如果你把原来的图灵机定义如下：

...以无限磁带的形式获得无限的记忆容量，标记成正方形，每个正方形上都可以打印一个符号。任何时候机器里都有一个符号；它被称为扫描符号。机器可以更改扫描的符号，其行为部分由该符号决定，但磁带上其他地方的符号不会影响机器的行为。然而，磁带可以在机器中来回移动，这是机器的基本操作之一。因此，磁带上的任何符号最终都可能有一个局。（图灵 1948 年，第 61 页）

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

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

4

4 回答 4

7

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

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

例如，在类似 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 的工作方式。

于 2010-08-21T13:26:06.753 回答
3

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

我们称其为 int 数组。 int[] Symbols

任何时候机器里都有一个符号；它被称为扫描符号。

int inxSym;
int scannedSymbol = Symbols[inxSym];

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

机器可以更改扫描的符号

Symbols[inxSym] = newSymbol;

它的行为部分地由那个符号决定，

switch(scannedSymbol) {....}

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

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

那里没什么可做的。

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

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

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

于 2010-08-21T13:21:08.193 回答
1

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

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

注意头部运动控制等价于流控制指令，即JMP及其兄弟。

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

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

于 2010-08-21T23:28:19.113 回答
0

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

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

然后可以通过编写它来定义机器

QnAi -> QmAoD

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

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

a 是接受状态，r 是拒绝状态。这是转换矩阵的非常紧凑且可读的表示。

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

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

如果在三元组中找到数据，或者停止那里没有数据，则将新状态写入状态寄存器，磁带上的 char 和 inc 减量。组装应该很有趣。

于 2010-08-21T13:52:49.747 回答