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.


Turing's Cathedral: The Origins of the Digital Universe

The book focuses on a small group of men and women, who built one of the first computers to realize Alan Turing’s vision of a Universal Machine.


The Essential Turing

The papers in this book are the key works for understanding Turing's phenomenal contribution.


Programming the Propeller Microcontroller

Get the authoritative guide to the Parallax Propeller chip.