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

如果取原始图灵机定义如下：原始图灵机上的操作的汇编语言等价物是什么？

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

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

（我知道从图灵机冯·诺依曼的机器在这个问题中固有的跳转的）

来源

2010-08-21 hawkeye

如果这是家庭作业，请标记为这样。 – danben 2010-08-21 13:08:02

8年前完成Uni - 这仅仅是为了兴趣。 – hawkeye 2010-08-21 13:11:43

读你写我说你什么只需要：

一直接增量指令（添加到当前磁带位置）
间接增量指令（用于移动磁带）
东西在目前大盘位置值

在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-21 13:26:06

在一个无限带的标出来成正方形的形式获得，在一个无限的存储容量每一个都可以打印符号。

让我们调用一个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-21 13:21:08

由于图灵机完全由它读取磁带它将使最有意义做出那样的表

让我们称之为状态QN的语言磁带和国家机器上的alfabet的定义确定，Alfabet人物艾从磁带上读取。机器从transisiton表中确定下一个状态，并写入敖到磁带并沿方向d：L/R

机器可然后通过写入其

QnAi被定义 - > QmAoD

从维基百科加法方案将随即成为

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

机智接受状态和r拒收状态。这非常紧凑并且可读的传输矩阵表示。

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

为了实现这个，你在左边有一个元组，在右边有一个三元组，因此这个映射在二维数组中的一个查找中以读取三元组。用磁带上字符的＃位移动状态并将它们粘在一起。相乘（ok，另一个移位操作）为三元组腾出空间，并将其用作表中的偏移量以读取三元组。

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

来源

2010-08-21 13:52:49

我不知道这是否是100％正确的，但它会去是这样的：

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

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

另请注意，寄存器是经典TM的重要补充。它们可以在磁带上表现为特殊的细胞（或细胞组）或作为独立的实体。有关更多详细信息，请参阅register machine。

最后，重要的是要提到，虽然这对冯诺依曼体系结构完美适用，哈佛架构使用两个不同的磁带，一个用于指令，一个用于数据。

来源

2010-08-21 23:28:19 spyked

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

回答

相关问题