Activities/Turtle Art/Tutorials/Turtle Art Turing Machine
One can do a surprising amount of Computer Science in Turtle Art. This is an example of a universal computer designed by Alan Turing in order to investigate problems in computability. As far as we know (Church's Thesis), any function that can be computed by an effective algorithm can be computed by a Turing Machine. A multitude of other systems has been proposed, and all are equivalent to the Turing Machine and to each other. However, there are questions that we would like to ask that neither a Turing Machine nor any of those other systems can answer.
Before we get to those undecidable questions, however, how is a Turing Machine constructed, and what is this Turing Machine going to do?
Plan
This Turing Machine will be the simplest kind of adding machine. It will start with two blocks of cells with a separator in between. The number of cells in each block is our input. The output will be a single block containing as many cells as the sum of the two input numbers. It will do this by replacing the separator with the color of the number blocks, and erasing one number cell at the end of the second block.
The Structure of a Turing Machine
A Turing Machine is not designed for efficiency, like microprocessors. It is designed to be easy to reason about, and so is about as simple as Turing could make it.
The essential elements of a Turing machine are
- a tape consisting of cells containing symbols; here, a line of colored dots
- a program table, consisting of three columns and some number of rows of instructions; here, a rectangle of colored dots
- a read-write head that follows instructions in the program table; here, the turtle with certain Actions
The machine can be in any of a finite number of states, represented here by color values. The rows of the program table correspond to combinations of the current state with the current symbol read from the current cell on the tape. For a three-state machine with two symbols, such as the adding machine we will see below, the order of the program table is
| Write | Move | New State |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 2 | 2 |
| 2 | 1 | 3 |
| 2 | 2 | 4 |
| 3 | 1 | 5 |
| 3 | 2 | 6 |
In operation, the starting point is a given tape with a finite sequence of symbols prewritten on it, a given program, and the Turing Machine head over the leftmost symbol on the tape in state 1. At each step, the head reads the symbol in the current cell, then follows the instructions in the row corresponding to that symbol and the current state. There are three parts to the instruction:
- A symbol to write in the current cell
- An instruction to move one cell left or right
- The state for the next step
The actual program table in numerical symbols is
| Write | Move | State | Interpretation |
|---|---|---|---|
| 0 | 1 | 2 | If cell = 0 Write 0. Go right. State 2 End of first number |
| 1 | 1 | 1 | If cell = 1 Write 1. Go right. State 1. Continue to end of number |
| 0 | 0 | 3 | If 0 Write 0. Go left. State 3 End of second number |
| 1 | 1 | 2 | If 1 Write 1. Go right. State 2 |
| 0 | 1 | 4 | If 0 Write 0. Go right. State 4. halt |
| 0 | 1 | 4 | If 1 Write 0. Go left. State 4 |
Where
- Symbols 0 and 1 are represented as Red and Blue
- Move 0 is Left and 1 is Right
- States are really numbers
Turing's Research
Among others things, Turing
- designed a Universal Turing Machine, where the program of a regular Turing Machine would appear in a block on the tape, and the head would operate on the tape before and after it as if the two segments were connected together.
- proved that no Turing machine can analyze the program for another Turing machine to decide whether it would ever halt.