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

读你写的东西我想说你只需要:

• 间接递增指令(移动磁带)
• 响应当前磁带位置值的操作

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

这差不多就是脑力操的工作原理。

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

int inxSym;
int scannedSymbol = Symbols[inxSym]; 

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

机器可以改变扫描的符号

Symbols[inxSym] = newSymbol;

它的行为部分是由这个符号决定的,

switch(scannedSymbol) {....}

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

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

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

(在CPU级别,这是JMP操作代码的句柄)

我不确定这是否100%正确,但它会是这样的:

• 因此,指令获取和解码阶段等同于对扫描符号的解释。
• 执行将被表示为更复杂的TM操作序列。让我们以一个内存写入为例:将磁头移动到一个给定的内存位置,将数据从寄存器移到该位置,返回到IP寄存器所寻址的位置并递增。

注意,头部移动控制等同于流控制指令,即JMP及其兄弟。

register machine 更多细节。

最后,值得一提的是,虽然这对冯·诺依曼体系结构非常有效,但哈佛体系结构使用了两个不同的磁带,一个用于指令,一个用于数据。

因为图灵机完全由磁带上的alfabet和读取磁带的状态机的定义决定,所以将语言变成一个表是最有意义的

让我们把状态称为Qn,也就是我从磁带上读到的Alfabet字符。机器根据传输表an确定下一个状态,并将Ao写入磁带,然后向D:L/R方向移动

然后可以通过编写

QnAi->QmAoD

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

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

要实现这一点,左侧有一个元组,右侧有一个三元组,因此这映射到二维数组中的查找以读取三元组。用磁带上字符的#位移动状态并将它们粘在一起。乘法(好的,另一个移位操作)为三元组腾出空间,并用它作为表中的偏移量来读取三元组。

如果在三元组中找到数据,则在状态寄存器中写入新状态,在磁带上写入字符,然后inc递减,或者在没有数据时停止。装配时应该很有趣。