Turing machine examples

The following are examples to supplement the article Turing machine.

Turing's 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 symbol	Operations on the tape	Final m-configuration
b		P0	b
b	0	R, R, P1	b
b	1	R, R, P0	b

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 symbol	Print-operation	Tape-motion	Final m-configuration
q₁	blank	P0	R	q₂
q₂	blank	P blank, i.e. E	R	q₃
q₃	blank	P1	R	q₄
q₄	blank	P blank, i.e. E	R	q₁

Turing's statement still implies five atomic operations. At a given instruction the machine:

observes the tape-symbol underneath the head
based on the observed symbol goes to the appropriate instruction-sequence to use
prints symbol S_j or erases or does nothing
moves tape left, right or not at all
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:

Sequence	Instruction identifier					Head
		.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
1	1	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
2	2	.	.	.	.	.	0	.	.	.	.	.	.	.	.	.	.	.	.
3	3	.	.	.	.	.	.	0	.	.	.	.	.	.	.	.	.	.	.
4	4	.	.	.	.	.	1	.	0	.	.	.	.	.	.	.	.	.	.
5	1	.	.	.	.	.	.	1	.	0	.	.	.	.	.	.	.	.	.
6	2	.	.	.	.	.	0	.	1	.	0	.	.	.	.	.	.	.	.
7	3	.	.	.	.	.	.	0	.	1	.	0	.	.	.	.	.	.	.
8	4	.	.	.	.	.	1	.	0	.	1	.	0	.	.	.	.	.	.
9	1	.	.	.	.	.	.	1	.	0	.	1	.	0	.	.	.	.	.
10	2	.	.	.	.	.	0	.	1	.	0	.	1	.	0	.	.	.	.
11	3	.	.	.	.	.	.	0	.	1	.	0	.	1	.	0	.	.	.
12	4	.	.	.	.	.	1	.	0	.	1	.	0	.	1	.	0	.	.
13	1	.	.	.	.	.	.	1	.	0	.	1	.	0	.	1	.	0	.
14	2	.	.	.	.	.	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:

Read the symbol under the head
Write the output symbol decided by the state
Move the tape to the left or to the right decided by the state
Switch to the following state decided by the current state

Initial m-configuration	Tape symbol	Print operation	Tape motion	Final m-configuration
s₁	0	N	N	H
s₁	1	E	R	s₂
s₂	0	E	R	s₃
s₂	1	P1	R	s₂
s₃	0	P1	L	s₄
s₃	1	P1	R	s₃
s₄	0	E	L	s₅
s₄	1	P1	L	s₄
s₅	0	P1	R	s₁
s₅	1	P1	L	s₅
H

Print Operation: Prints symbol S or Erases or does Nothing
A "run" of the machine sequences through 16 machine-configurations :

Sequence	Instruction identifier						Head
1	s₁	0	0	0	0	1	1	0	0	0	0	0
2	s₂	0	0	0	0	0	1	0	0	0	0	0
3	s₂	0	0	0	0	0	0	1	0	0	0	0
4	s₃	0	0	0	0	0	0	0	1	0	0	0
5	s₄	0	0	0	0	1	0	1	0	0	0	0
6	s₅	0	0	0	1	0	1	0	0	0	0	0
7	s₅	0	0	1	0	1	0	0	0	0	0	0
8	s₁	0	0	0	1	0	1	1	0	0	0	0
9	s₂	0	0	0	0	1	0	0	1	0	0	0
10	s₃	0	0	0	0	0	1	0	0	1	0	0
11	s₃	0	0	0	0	0	0	1	0	0	1	0
12	s₄	0	0	0	0	1	1	0	0	1	0	0
13	s₄	0	0	0	1	1	0	0	1	0	0	0
14	s₅	0	0	1	1	0	0	1	0	0	0	0
15	s₁	0	0	0	1	1	0	1	1	0	0	0
16	H	0	0	0	1	1	0	1	1	0	0	0

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