Close

Only Eight Cells?

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 08/22/2020 at 16:190 Comments

One might think having an eight cell "input area" would  limit the tasks TMG-1 could perform.  In actual fact I could not find any interesting programs that could not be run in eight or less cells on an unbounded tape. What does interesting mean? Well the program would have to do something non-trivial (something more than writing a single symbol to the tape) and then stop. Stopping is important because there is nothing interesting about a program wondering down a tape to infinity (at least after the first millennia or so). 

To  be brutally honest, there is only one program that runs on on a 2-symbol (assume the b is not used)/ 3-state Turing machine that is truly interesting, the "busy beaver".  The busy beaver "game" consists of designing a halting, binary-alphabet Turing machine which writes the most 1s on the tape, using only a given set of states, in this case 3-states. By definition a busy beaver program running on TMG-1 is prohibited from using the endmarker. symbol I won't spoil the ending but this programs runs fine in eight cells.

In actual fact implementing TMG-1 as an Linear Bounded Automata suddenly makes it a lot more interesting and fun. Being able to determine the beginning and end of the input area is key. With this little LBA we will be able to:

You get the idea. As an LBA the Turing Machine Demonstrator is a much more capable teaching tool even with only eight cell for the input area.

Discussions