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

Question

如果取原始图灵机定义如下:

...an infinite memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings. (Turing 1948, p. 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 的工作原理。