A Turing Machine

Some have asked what exactly (more or less) is a Turing machine.  The machine itself is nothing but a tape consisting of cells  of various colors (imagine a long row) and a reader head positioned somewhere on the tape.  Imagine that this reader head can be in a certain state, again as many as you like.  The head can move to the right or to the left one cell at a time depending on certain rules.  These  rules constitute  the definition of the Turing MACHINE.  The rules when executed will:
a) Move the head either to the left or to the right.
b) Possibly change the state of the head.
c) And possibly alter the color of the new cell where the head now sits.
Similar to  the instruction pointer, an execution of the rules will place the pointer to the right or to the left, maybe change the state of the head, and maybe alter the color of the cell on which the pointer now sits.  This process will repeat sequentially.  
You start with a certain initial state, giving the cell on which the reader head sits a color and the head itself a cetain state.  Then you just let it go, and like the instruction pointer, it clicks away until you say stop.  
Please understand that no one was interested in building such a machine or doing anything practical with it!  Its importance was just this: Turing showed that any formal mathematical proof can be represented by a program  which when executed by a Turing machine will also return the value "True" and conversely.  Turing obtained the important result that there are perfectly nice initial conditions for some Turing machines that will never terminate with the result True or False.  Conclusion:  There are mathematical theorems that can never be determined whether they are True or False from the axioms. Another formulation: There does not exist a program that can check the validity of any given program.   
But back to constructing a simple example of a Turing machine.   
There are rules for the rules!  You cannot have rules that depend on the neighboring cells, but only the cell on which the head is sitting.  So no need to know the color of adjacent cells.  

An Example of a Simple Turing Machine

Let us imagine there are three possible states and call them up, left, and right which we indicate by a small teardrop.  Let us also imagine there are only two colors for the cells, black and white. We will start with the head in an up state and on a white colored cell.  We need to specify rules as to the color, position, and state of the head for a single execution of the rules.  

We give ourselves some rules, first pictorially:


This gives the six possible states of the head, and the picture below tells us what happens with a single execution of the the instruction.  This set of instructions can also be given as a list of lists, with the arrow indicating the update of the head and tape after execution of the instruction.  For example, in our case where we start with the head at a white cell pointing up, then the update will change the cell to grey and move the head to the left with the state pointing to the left as well.  If you represent the status of the head an ordered pair (a,b), with the first position a, taking on values 0, 1,2,3 for the state of the head, and the second position, b,  the color of the cell on which the head rests, 0 for white, 1 for black, then we would write (1,0) for the initial position, that is, state is up and the cell is white.  Now the rule would update (1,0)  by greying the cell on which the head was situated, moving to the left, and changing the state of the head to 3, so the rule would be specified by: (1,0) -> (3,1,-1) where the last number -1 means a move to the left.  So another representation of our picture for our rules and so more suitable for programming would be:
{{1,1}→{2,0,1},{1,0}→{3,1,-1},{2,1}→{3,1,1},{2,0}→{1,1,1},{3,1}→{1,0,-1},{3,0}→{2,1,1}}
This is just a different representation of what we had as a picture above.
Let us give ourselves say 5 cells and do this updatting twice:




The third row is now the state of the tape and the head is on a grey cell  in a state pointing to the right.
Do you see how the rules determine what the 3rd row is?  Let us do some more.  Make the tape of length 8, and let us do 8 iterations:


But this can go on . . . how about a tape of length 100 and 100 iterations:



Does this do anything useful for us ?  I doubt it.  But please note this formulation of the essence of a computer is so abstract that few programmers would even recognize their own computers in this.  There are no chips, no memory, and only a small number of rules that make this computer do its thing.  Furthermore, it is no PHYSICAL THING!
And if you  instead of using just two colors and  use  5, then the number of possible Turing machines far exceeds the number of atoms in the universe!
Finally, there are initial conditions which will produce totally random output, utterly unpredictable. There are patents for Cellular Automata that produce random numbers.  But the paradox is curious.  The ouput of these programs is completely determined by the initial conditions, BUT the ouput is completely UNPREDICTABLE, and the only way you can find the output is actually just to run the program!  

Created by Mathematica  (January 30, 2007)