Turing Machine
In the theory of algorithms as an exact mathematical equivalent for general intuitive concept about algorithm the concept of the Turing machine is used.
The program for the Turing machine consists of sequence of the instructions. Everyone instruction looks like
CurrentState CurrentSymbol NextSymbol NextState Move
We assume, that from both sides from the entered sequence of symbols there is an infinite quantity of symbols blank (blank we shall designate by a symbol "b").
Initial internal condition is a condition "A", final internal condition - "Z".
Let's consider some examples of the program for the Turing machine.
Example 1. Replacement of each unit by two (tm.dtd , tm.xsl , tm12.xml).
| CurrentState | A | A |
| CurrentSymbol | b | 1 |
| NextSymbol | b | 2 |
| NextState | Z | A |
| Move | R | R |
Example 2. Doubling of quantity of units on a tape (tm.dtd , tm.xsl , tmmul2.xml).
If, for example, on a tape in the beginning there are 10 units, in the end will be 20 units.
| CurrentState | A | A | A | B | B | C | C |
| CurrentSymbol | b | 2 | 1 | 2 | b | 2 | b |
| NextSymbol | b | 2 | 2 | 2 | 2 | 1 | b |
| NextState | C | A | B | B | A | C | Z |
| Move | L | R | L | L | R | L | R |
The example of transformation of two units in four units (under a surveyed symbol is below adduced the current internal condition of the Turing machine) is written.
b b b 1 1 b b
A
b b b 2 1 b b
B
b b 2 2 1 b b
A
b b 2 2 1 b b
A
b b 2 2 2 b b
B
b b 2 2 2 b b
B
b b 2 2 2 b b
B
b 2 2 2 2 b b
A
b 2 2 2 2 b b
A
b 2 2 2 2 b b
A
b 2 2 2 2 b b
A
b 2 2 2 2 b b
C
b b 2 2 2 b b
C
b b 2 2 2 b b
C
b 2 2 2 2 b b
C
b 2 2 2 2 b b
C
b 2 2 2 2 b b
Z
Example 3. Check of structure of brackets (tm.dtd , tm.xsl , tmbrackets.xml).
At the end of job in a free square there will be a T, if structure correct, and F - if wrong.
| CurrentState | A | B | B | B | B | B | C | C | C | C | D | D | D | D |
| CurrentSymbol | b | l | r | ( | b | ) | l | r | ( | b | l | r | ( | b |
| NextSymbol | b | l | r | ( | b | r | l | r | l | F | ( | ) | F | T |
| NextState | B | B | B | B | D | C | C | C | B | Z | D | D | Z | Z |
| Move | R | R | R | R | L | L | L | L | R | R | L | L | R | L |
Example 4. Delete of points between units (tm.dtd , tm.xsl , tmdelete.xml).
For example, if in the beginning on a tape there were symbols .11..11..., then in the end we shall have 1111
| CurrentState | A | B | B | B | C | C | C | D | D | D | F | G | G | G | H |
| CurrentSymbol | b | 1 | . | b | . | 1 | b | . | 1 | b | . | . | 1 | b | b |
| NextSymbol | b | 1 | . | b | . | . | b | . | 1 | b | 1 | b | 1 | b | b |
| NextState | B | B | C | Z | C | D | G | D | F | F | C | G | H | H | Z |
| Move | R | R | R | R | R | L | L | L | R | R | R | L | R | R | R |
Example 5.Check of divisibility on 3 (tm.dtd , tm.xsl , tmdiv3.xml).
The program consists of 30 instructions, therefore we do not write here. Similarly, it is possible to make the program of check of divisibility on 9. Then the program will consist of 100 instructions.