About TMD-1

A project log for TMD-1: A Turing Machine Demonstrator

Develop a Turing machine that is simple to program and easy to understand.

Michael GardiMichael Gardi 07/13/2020 at 02:010 Comments


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:

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:

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.


In addition there will be controls to:

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: