Program Examples
Through the links above you will find a number of examples of the Turing machine running. Each includes a short explanation of how it works and the transition rules (states) that made it happen. I've keeped each video around 2 minutes long.
Turing Machine Counting
Counting is one of the first math skills we learn. It's really not that much different for a computer or a Turing machine except they normally use binary numbers, so they count in binary. In this Turing machine example, you can see the machine following a simple set of steps to count in binary.
How the Turing Machine Counts
Counting is really just repeatedly adding one to a number. If we count in decimal like most humans do, we keep adding one to a number. When adding one causes a digit to change to a zero we have to carry an extra one over to the digit to the left and add it there. This has become so automatic for us that we seldom even think about it any more. The Turing machine counts in the same way, it's just adding one to the number that is currently on the tape. The big difference is that the Turing machine counts in binary. When it changes a digit to a zero it also carries and adds the one to the digit to the left. But because there are only zeros and ones in binary this carry happens a lot more often.
The states required for counting with the Turning machine are some of the easiest to understand. The three rules that make up state "0" do not change the tape, they simple move to the right most cell without changing the tape. When a blank cell is found, the tape moves one cell back to the left and changes to state "1".
State "1" is where the counting happens. The three rules of state "1" are really rules for adding one and carrying. We know that we are starting from the right most digit because we are coming to this state from state "0". If we read a zero, we change it to a one and have finished adding because there is nothing to carry. So the state is changed back to "0" and the tape is moved back to the right. If though, we read a one, it is changed to a zero, and we now need to carry that one to the left. This carry is accomplished with the second rule of state "1". It does this by moving to the left one digit and staying in state "1". By staying in state "1" the machine in a sense stays in the add one mode, thus carrying the one. The machine will stay in state one until it finds a zero to add the one to or it finds a blank. The third rule of state "1" handles blank cells by treating them just like zeros, that is they are changed to a one and the adding of one is completed.
The States Used For This Example (Explanation of the Programming Syntax Used)
(0,1) -> (0,1) Right //This state moves the tape to the right most digit (0,0) -> (0,0) Right //This state moves the tape to the right most digit (0,B) -> (1,B) Left //When a blank at the right is found we change to state 1 //This next block, state 1, is where the counting really happens (1,0) -> (0,1) Right //If we change a 0 to a 1 we change back to state 0 (1,1) -> (1,0) Left //If we change a 1 to a 0 we keep looking to the left (1,B) -> (0,1) Right //If we change a Blank to a 1 we change back to state 0
For the Keen Observers
Keen observers will note that
the sample shown in the video stops on its own after it reaches 16 in decimal.
This was done for the video and only takes one change to the program shown
above. The
third rule of state "1" is changed to:
(1,B) -> (0,1) Halt //If we change a Blank to a 1 we stop
This has the effect of stopping the counting when the tape adds a one to the blank cell at the left of the number.
For the Really Keen Observers
Really keen observers will note
that the sample shown in the video continues to move to the left after a one
was written to the tape. This was done so that the whole tape was visible
on each pass of adding one. It doesn't change the outcome in any way. It was
done by adding a state "2" and changing state "1" like
this:
(1,0) -> (2,1) Left //If we change a 0 to a 1 we change to state 2 (1,1) -> (1,0) Left //If we change a 1 to a 0 we keep looking (1,B) -> (0,1) Halt //We have to stop sometime, so if we find a blank we stop (2,1) -> (2,1) Left //This state moves the tape to the left most digit (2,0) -> (2,0) Left //This state moves the tape to the left most digit (2,B) -> (0,B) Right //When the blank at the left is found we switch to state 0