Overview

There are numerous variations to the general Turing machine described above.  Some have multiple tapes and/or heads. Some tapes are bound (have an end) on the left or right or both. In addition Turing machines have varying numbers of symbols in their alphabets and varying numbers of states. The Turing Machine Demonstrator (TMD-1) will have the following characteristics:

• One tape and one head.
• The alphabet used will have three symbols: {0, 1, b}. 0 will be the blank symbol and b is an endmarker as described below.
• There will be four states: {A, B, C, H}. A will be the start state and H is a special HALT state.

Tale of the Tape

Having a tape that is "arbitrarily extendable" to the left or right would pose some serious implementation issues, not to mention being complete overkill for a 3-symbol / 4-state Turing machine. So I have chosen to implement a restricted form of Turing machine called a "linear bounded automata" (LBA). 

In addition to the normal Turing machine behaviors, an LBA has the following three conditions:

• The input alphabet includes two special symbols, serving as left and right endmarkers. In an effort to simplify things even further, TMD-1 will only have a single endmarker symbol (b) in it's input alphabet. 
• Transitions may not print other symbols over the endmarkers. In addition, TMD-1 will not allow an endmarker to be written to the other part of the tape.
• Transitions may neither move to the left of the left endmarker nor to the right of the right endmarker. For TMD-1 such a move will HALT the machine.

In other words, instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers.  It will look something like this:

The end cells (endmarkers) cannot be changed and furthermore cannot be written to the other portion of the tape. So the "input" part of the tape will only ever contain zeros and ones.

Finite State Machine

There will be an area on TMD-1 that will allow a user to both define the behavior of the finite state machine (basically the program), as well as see the current state of the machine as it processes each step.  I'm very excited about this piece and will reveal more details when I've done a bit more testing.

Controls

In addition there will be controls to:

• Start the machine in either Run or Step mode.
• Enter "data" into the Tape and set the Head's start position prior to running a program.
• Reset the Tape to a known starting state.

The Soul of the Machine

Driving everything will be and Arduino Mega 2560 as I anticipate needing a lot of I/O pins to drive all of the above. The Mega will:

•  Implement the finite state machine as defined by the user's input.
• Manage the movement of the Head and the changes to the Tape.
• Process the Controls.