assemblyturing-machinesvon-neumann

What would the assembly language equivalents of the operations on the original Turing machine be?


If you take the original Turing machine definition as follows:

...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)

If you want to map these operations to those done on a processor capable of interpreting assembler/binary instructions - which operations would be mapped?

(I'm aware of the jump from Turing machines to Von Neuman machines inherent in this question)


Solution

  • Reading what you've written I'd say you just need:

    In an ARM-like assembly, for example, if you have R0 containing the address on the tape you should just need

    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
    

    Then, branches to do stuff in case of certain values assumed by the current symbol

    BEQ Somewhere
    

    This is more or less how Brainfuck works.