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)

Sil

If this is homework, please tag as such. – Disharoon

Finished Uni 8 years ago - this is just for interest. – Sil

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.

Idem

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)

Mylor

Answer 3

Since the turing machine is completely determined by the definition of the alfabet on the tape and the state machine which is reading the tape it would make most sense to make the language like a table

Lets call the states Qn, the Alfabet characters Ai read from the tape. The machine determines the next state from the transisiton table an and writes Ao to the tape and moves in the direction D : L/R

The machine can then be defined by writing its

QnAi -> QmAoD

The adding program from wikipedia would then become

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

wit a the accepting state and r the rejecting state. This is pretty compact and a readable presentation of the transisition matrix.

This of course assumes that what is on the tape is interpreted as data. But nothing stops anyone of creating the transition matrix to make the statemachine interprete instruction from the tape.

To implement this you have on the left side a tuple and on the right side a triple, so this maps on a lookup in a 2D array to read the triplet. Shift the state with the #bits of the character on the tape and stick them together. Multiply (ok, another shift operation) to make room for the triplet, and use that as the offset in a table to read the triplet.

Write the new state in the state register, the char on the tape, and inc decrement, if you find data in the triplet, or stop of there is no data there. Should be fun in assembly.

Ultramontanism

Answer 4

I'm not sure if this is 100% correct, but it would go something like this:

• The Turing Machine head (the one that "scans" a symbol at a given time) would be equivalent with the Instruction Pointer.
• The Instruction Fetch and Decode phases are therefore equivalent with an interpretation of the scanned symbol.
• Execution would be represented as a more complex sequence of TM operations. Let's take a memory write, for example: move the head to a given memory location, move data from registers to the location, go back to the location addressed by the IP register and increment it.

Note that head movement control is equivalent to flow control instructions, i.e. JMP and its brothers.

Also note that the registers are an important addition to the classical TM. They could be represented as special cells (or sets of cells) on the tape or as separate entities. See the register machine for more details.

Finally, it's important to mention that while this works perfectly for the Von Neumann architecture, the Harvard architecture uses two distinct tapes, one for instructions and one for data.

Marchal