Example of a Turing Machine
If you had already watched the Demo Video (at the link at the top of this page), then you saw a simple example of a Turing Machine. It is the Turing Machine UN+1 that Sir Roger Penrose described on page 54 of his book The Emperor's New Mind (Oxford University Press, 1989). What it does is read the number on the tape (in Unary Notation), add one to it, and display the answer on the tape (again in Unary Notation).
Below is a portion of the Excel file that you saw in the Demo Video.
In the above picture, you can see that this Turing Machine has two states; they are called 0 and 1. (The states are listed in row 4 of the Excel file.)
Rows 5 and 6 have the "instructions" that the Turing Machine follows as it runs. So, for example, if the Turing Machine is in state 0 and its Read/Write Head reads 0 on the tape, then it executes command 00R. (00R means write 0 on the tape, move the Read/Write Head one position to the right, and go to state 0.) Or, if the Turing Machine is in state 0 and its Read/Write Head reads 1 on the tape, then it executes command 11R. (11R means write 1 on the tape, move the Read/Write Head one position to the right, and go to state 1.) And so on.
As the Turing Machine runs, the cell with the next "instruction" to be executed is shaded gold.
The paper tape used by the Turing Machine is in row 11. It is an infinitely long paper tape, but only a portion of it is shown in the Excel file, starting at cell F11 and in the cells to the right of it.
The only symbols allowed on the tape are 0 and 1. (In my Excel implementation of Penrose's UN+1, I also allowed the blank to be an input symbol. The blank, when read by this Turing Machine, is treated in exactly the same way as if it were 0.)
In the Excel file, the cell that is shaded green shows the current position of the Turing Machine's Read/Write Head on the tape.
OK. Well, all this is fine and good, but what does this have to do with the Formal Definition of a Turing Machine?
The formal definition of a Turing Machine is the 7-tuple:
M = (Q, Σ, Γ, δ, q0, B, F)
where
Q is the set of states
Σ is the set of input symbols
Γ is the set of tape symbols
δ is the transition function
q0 is the start state
B is the blank symbol
F is the set of final states
and where the transition function δ is defined as:
δ(q, X) = (p, Y, D)
where q and p are states, X and Y are symbols on the tape, and D is the direction in which the Read/Write Head is to move.
So, in the case of Roger Penrose's UN+1 Turing Machine, we have:
Q = {0, 1}
Σ = {0, 1}
Γ = {0, 1}
q0 = 0
F = {1}
and the transition function δ is definied as follows:
δ(0, 0) = (0, 0, R)
δ(0, 1) = (1, 1, R)
δ(1, 0) = (0, 1, STOP)
δ(1, 1) = (1, 1, R)
Once you have the Formal Definition specified (as in the example above) then you have all the information you need about your Turing Machine. Then, you can build a physical Turing Machine based on those specifications, or write a computer simulation of it, or even see how it works using paper and pencil and eraser.
Using the Formal Definition is just one way that can be used to completely describe any particular Turing Machine. Another way is to give its Turing Machine Number. The Turing Machine Number (or Turing Machine Description Number) has embedded into it all the information that is also in the Formal Definition of that Turing Machine.
Version 1.0 -- April 23, 2017