Turing machine examples


The following are examples to supplement the article Turing machine.

Turing's very first example

The following table is Turing's very first example :
With regard to what actions the machine actually does, Turing states the following:
He makes this very clear when he reduces the above table to a single instruction called "b", but his instruction consists of 3 lines. Instruction "b" has three different symbol possibilities. Each possibility is followed by a sequence of actions until we arrive at the rightmost column, where the final m-configuration is "b":
Current m-configuration Tape symbolOperations on the tapeFinal m-configuration
b-P0b
b0R, R, P1b
b1R, R, P0b

As observed by a number of commentators including Turing himself,, Post, Kleene, Wang ) the Turing instructions are not atomic — further simplifications of the model can be made without reducing its computational power; see more at Post–Turing machine.
As stated in the article Turing machine, Turing proposed that his table be further atomized by allowing only a single print/erase followed by a single tape movement L/R/N. He gives us this example of the first little table converted :
Current m-configuration Tape symbolPrint-operationTape-motionFinal m-configuration
q1P0Rq2
q2P blank, i.e. ERq3
q3P1Rq4
q4P blank, i.e. ERq1

Turing's statement still implies five atomic operations. At a given instruction the machine:
  1. observes the tape-symbol underneath the head
  2. based on the observed symbol goes to the appropriate instruction-sequence to use
  3. prints symbol Sj or erases or does nothing
  4. moves tape left, right or not at all
  5. goes to the final m-configuration for that symbol
Because a Turing machine's actions are not atomic, a simulation of the machine must atomize each 5-tuple into a sequence of simpler actions. One possibility — used in the following examples of "behaviors" of his machine — is as follows:
So-called "canonical" finite state machines do the symbol tests "in parallel"; see more at microprogramming.
In the following example of what the machine does, we will note some peculiarities of Turing's models:
Thus when printing he skips every other square. The printed-on squares are called F-squares; the blank squares in between may be used for "markers" and are called "E-squares" as in "liable to erasure." The F-squares in turn are his "Figure squares" and will only bear the symbols 1 or 0 — symbols he called "figures".
In this example the tape starts out "blank", and the "figures" are then printed on it. For brevity only the TABLE-states are shown here:
SequenceInstruction identifier    Head             
..................
11..................
22.....0............
33......0...........
44.....1.0..........
51......1.0.........
62.....0.1.0........
73......0.1.0.......
84.....1.0.1.0......
91......1.0.1.0.....
102.....0.1.0.1.0....
113......0.1.0.1.0...
124.....1.0.1.0.1.0..
131......1.0.1.0.1.0.
142.....0.1.0.1.0.1.0

The same "run" with all the intermediate tape-printing and movements is shown here:
A close look at the table reveals certain problems with Turing's own example—not all the symbols are accounted for.
For example, suppose his tape was not initially blank. What would happen?
The Turing machine would read different values than the intended values.

A copy subroutine

This is a very important subroutine used in the "multiply" routine.
The example Turing machine handles a string of 0s and 1s, with 0 represented by the blank symbol. Its task is to double any series of 1s encountered on the tape by writing a 0 between them. For example, when the head reads "111", it will write a 0, then "111". The output will be "1110111".
In order to accomplish its task, this Turing machine will need only 5 states of operation, which are called. Each state does 4 actions:
  1. Read the symbol under the head
  2. Write the output symbol decided by the state
  3. Move the tape to the left or to the right decided by the state
  4. Switch to the following state decided by the current state
Initial m-configuration Tape symbolPrint operationTape motionFinal m-configuration
s10NNH
s11ERs2
s20ERs3
s21P1Rs2
s30P1Ls4
s31P1Rs3
s40ELs5
s41P1Ls4
s50P1Rs1
s51P1Ls5
H---

A "run" of the machine sequences through 16 machine-configurations :
SequenceInstruction identifierHead
1s100001100000
2s200000100000
3s200000010000
4s300000001000
5s400001010000
6s500010100000
7s500101000000
8s100010110000
9s200001001000
10s300000100100
11s300000010010
12s400001100100
13s400011001000
14s500110010000
15s100011011000
16H00011011000

The behavior of this machine can be described as a loop:
it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1s and the first 0 encountered. s3 then skips over the next sequence of 1s and replaces the first 0 it finds with a 1. s4 moves back to the left, skipping over 1s until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1s until it finds the 0 that was originally written by s1.
It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop.
This continues until s1 finds a 0 at which time the machine halts.

Alternative description

Another description sees the problem as how to keep track of how many "1"s there are. We can't use one state for each possible number, because then we'd need infinite states to represent all the natural numbers, and the state machine is finite - we'll have to track this using the tape in some way.
The basic way it works is by copying each "1" to the other side, by moving back and forth - it is intelligent enough to remember which part of the trip it is on. In more detail, it carries each "1" across to the other side, by recognizing the separating "0" in the middle, and recognizing the "0" on the other side to know it's reached the end. It comes back using the same method, detecting the middle "0", and then the "0" on the original side. This "0" on the original side is the key to the puzzle of how it keeps track of the number of 1's.
The trick is that before carrying the "1", it marks that digit as "taken" by replacing it with an "0". When it returns, it fills that "0" back in with a "1", then moves on to the next one, marking it with an "0" and repeating the cycle, carrying that "1" across and so on. With each trip across and back, the marker "0" moves one step closer to the centre. This is how it keeps track of how many "1"'s it has taken across.
When it returns, the marker "0" looks like the end of the collection of "1"s to it - any "1"s that have already been taken across are invisible to it and so it is as if it is working on an number of "1"s - similar to a proof by mathematical induction.
A full "run" showing the results of the intermediate "motions". To see it better click on the image, then click on the higher resolution download:

3-state [Busy Beaver]

The following Turing table of instructions was derived from Peterson page 198, Figure 7.15. Peterson moves the head; in the following model the tape moves.
The "state" drawing of the 3-state busy beaver shows the internal sequences of events required to actually perform "the state". As noted above Turing makes it perfectly clear that this is the proper interpretation of the 5-tuples that describe the instruction. For more about the atomization of Turing 5-tuples see Post–Turing machine:
The following table shows the "compressed" run — just the Turing states:
SequenceInstruction identifierHead
1b00000000000000
2B00000001000000
3A00000110000000
4C00001100000000
5B00011100000000
6A00111100000000
7B00011111000000
8B00001111100000
9B00000111110000
10B00000011111000
11B00000001111100
12A00000111111000
13C00001111110000
14H00001111110000

The full "run" of the 3-state busy beaver. The resulting Turing-states are shown highlighted in grey in column A, and also under the machine's instructions ):