What will be the equivalent of the assembly language of operations on the original Turing machine?

Question

If you take the original definition of a Turing machine as follows:

... unlimited memory capacity obtained in the form of an infinite marked tape on squares, on each of which a symbol can be printed. At any moment there is one character in the car; it is called a scanned symbol. The machine may change the scanned character and its behavior is partially determined by the fact that the character, but the characters on the tape in another place do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine; this is one of the basic operations of the machine. Any character on the tape can therefore ultimately have innings. (Turing 1948, p. 61)

If you want to compare these operations with those processed on a processor capable of interpreting assembler / binary instructions, what operations will be displayed?

(I know that the transition from Turing machines to von Neumann machines is inherent in this issue)

Answer 1

Reading what you wrote, I would say that you just need to:

• Direct increment command (to add to the current tape location)
• Indirect increment command (to move the tape)
• Something to act on in response to the current tape location value

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

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 things in case of certain values ​​accepted by the current character

 BEQ Somewhere 

This is more or less how Brainfuck works.

Answer 2

infinite memory capacity obtained in the form of an endless tape allocated to squares, on each of which a symbol can be printed.

Let me call this array int. int[] Symbols

There is one character in the car at any time; it is called a scanned symbol.

 int inxSym; int scannedSymbol = Symbols[inxSym]; 

(At the CPU level, this is called the "main memory" or in the "software segment" of a modern system.

The machine can change the scanned character.

 Symbols[inxSym] = newSymbol; 

and its behavior is partially determined by this symbol,

 switch(scannedSymbol) {....} 

(At the CPU level, this is “executing instructions.” There is no op code to say this, this is what the CPU does.)

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

That's that.

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

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

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

Answer 3

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

• The head of a Turing machine (one that “scans” a character at a given time) would be equivalent to an instruction pointer.
• The phases of fetching and decoding instructions are thus equivalent to interpreting the scanned character.
• Execution will be presented as a more complex TM workflow. For example, take a memory record: move the head to a given memory location, move data from the registers to a location, return to the address addressed by the IP register, and increase it.

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

Also note that registers are an important addition to classic TM. They can be presented in the form of special cells (or sets of cells) on a tape or as separate objects. For details, see the registrar .

Finally, it is important to note that while this works great for Von Neumann architecture, Harvard architecture uses two different tapes: one for instructions and one for data.

Answer 4

Since the turing machine is completely determined by the definition of alfabet on the tape and the state machine that reads the tape, it would be wiser to make the language as a table

Allows you to name the state Qn, characters Alfabet Ai, read from the tape. The machine determines the following state from the transisiton an table and writes Ao to tape and moves in the D direction: L / R

Then the machine can be identified by writing it

QnAi → QmAoD

The wikipedia add program will then become

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

with the receiving state and r rejecting state. This is a fairly compact and readable presentation of the transliteration matrix.

This, of course, suggests that what is on the tape is interpreted as data. But there is nothing stopping the creation of a transition matrix in order to make a statemachine interpretative instruction from tape.

To implement this, you have a tuple on the left side and a triple on the right, so it displays a search in a 2D array for reading a triplet. Move the C # state to the bits of the character on the tape and connect them together. Multiply (ok, another switching operation) to make room for the triplet, and use it as an offset in the table to read the triplet.

Write the new state in the status register, char on the tape and inc decrement if you find the data in the triplet or stop any data there. It should be fun to build.