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

Question

如果您采用原始的图灵机定义如下:

......以无限磁带的形式获得的无限存储容量,标记为正方形,每个磁带上可以打印一个符号.在任何时刻机器中都有一个符号; 它被称为扫描符号.机器可以改变扫描的符号,其行为部分由该符号决定,但其他地方的磁带上的符号不会影响机器的行为.但是,磁带可以在机器中来回移动,这是机器的基本操作之一.因此,磁带上的任何符号最终都可以有一局.(图灵1948年,第61页)

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

(我知道从这个问题中固有的Turing机器到Von Neuman机器的跳跃)

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的工作原理.