Program Examples

How the States for the Turing Machine are Written

Programming for my Turing machine is written as simple text files on any computer and saved to SD cards. The states described in these text files are then loaded into and interpreted by the Turing machine. I use a fairly standard notation for describing the states:
( State Number, Symbol Read) -> ( Next State Number, Symbol To Write) Next Cell

Each state normally consists of three rules, one for each of the three symbols (0, 1, blank) that can possibly be read from a cell. So the first rule in the following state sample tells the machine:
If the machine is in state "1" and there is a zero in the cell, change this to a one, change to state "0", and move one cell to the left.

```(1,0) -> (0,1) Left
(1,1) -> (1,0) Left
(1,B) -> (0,1) Right
```

The second rule tells the machine:
If there is a one in the cell, change this to a zero, leave the state as "1", and move one cell to the left.
The third rule tells the machine:
If the cell is blank, change this to a one, change to state "0", and move one cell to the right.

The only other rule you will see in the sample programs is the next cell move of "Halt".

```(1,B) -> (0,1) Halt
```

This is just as it sounds, when this rule is followed the cell is changed from blank to one and the machine stops.

Summary of The Examples

While I have taken some liberty with a number of terms and concepts, I hope you can see just how simple the rules that drive a Turing machine are. Changing ones to zeros, moving one cell to the left or right, these concepts are simple, yet they can compute anything that is computable. And from these simple concepts, the most complex computers of today are born.

Programming the Propeller Microcontroller

Get the authoritative guide to the Parallax Propeller chip.

Alan Turing: The Enigma The Centenary Edition

This classic biography of the founder of computer science, reissued on the centenary of his birth with a substantial new preface by the author, is the definitive account of an extraordinary mind and life.

Online Turing Machine Simulators

Here are a couple of simulators that will let you experiment with creating your own Turing machines.