Build Your Own Turing Machine

I've posted here before about some of the projects my talented cousin, Michael Gardi, has been developing. His latest is a bit of a departure from his previous recreations of classic 60s educational computing toys. It's a Turing Machine demonstrator.  

For something that has been around since the 1930s and is so foundational to computer science, you’d think that the Turing machine, an abstraction for mechanical computation, would be easily understood. Making the abstract concepts easy to understand is what this Turing machine demonstrator aims to do.

The TMD-1 is a project that’s something of a departure from [Michael Gardi]’s usual fare, which has mostly been carefully crafted recreations of artifacts from the early days of computer history, like the Minivac 601  trainer and the DEC H-500 computer lab. The TMD-1 is, rather, a device that makes the principles of a Turing machine more concrete. To represent the concept of the “tape”, [Mike] used eight servo-controlled flip tiles. The “head” of the machine conceptually moves along the tape, its current position indicated by a lighted arrow while reading the status of the cell above it by polling the position of the servo.

Mike goes into more detail about his design choices in his Hackaday project site. Here'a a bit of it.

One might think having an eight cell "input area" would  limit the tasks TMD-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 3-symbol / 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 TMD-1 is prohibited from using the endmarker symbol. I won't spoil the ending but this program runs fine in eight cells.

In actual fact implementing TMD-1 as an Linear Bounded Automata 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:

• Treating the input area as a binary number find the one's compliment. (Making the input/tape alphabet 0 and 1 was not by accident in this case, although by convention this is often the case. )
• Find the two's compliment of the "binary" number in the input area.
• Count in binary (ascending and descending).
• Sorting. Move all the 1's in the input area to the right or left.
• Shift the input area one cell to the right or left (multiply / divide by 2).
• Cylon eye with head lamps ;-)

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

He has more detailed instructions, including a parts list and the files needed for 3D printing, on the Instructables site.