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
( 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
Lego Turing Machine
If you like Turing machines, check out this Lego version.
The Essential Turing
The papers in this book are the key works for understanding Turing's phenomenal contribution.
Programming the Propeller with Spin
A Beginner's Guide to Parallel Processing walks you through the essential skills you need to build and control devices using the Propeller chip and its parallel processing environment.