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

Question

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)

Answer 1

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

• A direct increment instruction (to add to the current tape location)
• An indirect increment instruction (to move the tape)
• Something to act in response of the current tape location value

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.

Answer 2

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.

Let's call that a int array. int[] Symbols

At any moment there is one symbol in the machine; it is called the scanned symbol.

int inxSym;
int scannedSymbol = Symbols[inxSym]; 

(At the CPU level, this is known as "main memory" or in modern system "program segment".

The machine can alter the scanned symbol

Symbols[inxSym] = newSymbol;

and its behavior is in part determined by that symbol,

switch(scannedSymbol) {....}

(At the CPU level, this is "executing an instruction". There is no op code to tell it to do so; it's just what CPU do.)

but the symbols on the tape elsewhere do not affect the behavior of the machine.

Nothing to do there.

However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine.

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

(At the CPU level, this is handle with JMP op codes)