Main Content

You can find numerous Turing machine implementations on the internet that are absolutely stunning. The makers of these devices often set lofty goals for themselves, like “mechanical only solutions”, which they met and exceeded with aplomb. In my humble opinion though, the complexity of these excellent and imaginative solutions often detracted from the understanding of what a Turing machine actually does.
So my approach with this project from the onset was to demonstrate the idea of a Turing machine with as much clarity as possible. I tried to build a machine that is simple to program and easy to understand. I guess that was my lofty goal for this project.
In this Instructable I will focus on the steps required to build a TMD-1. However I think that a little background will be required now and then to provide context to the build.

What is a Turing Machine?

The Turing machine was invented in 1936 by Alan Turing. By providing a mathematical description of a simple device capable of arbitrary computations, he was able to prove the properties of computation in general.

A Turing machine mathematically models a mechanical machine that operates on a tape. More explicitly, a Turing machine consists of:

- A tape divided into adjacent cells. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol and one or more other symbols. Cells that have not been written before are assumed to be filled with the blank symbol.
- A head that can read and write symbols on the tape and move on the tape left and right one (and only one) cell at a time.
- A state register that stores the state of the Turing machine, one of many. Among these is the special start state with which the state register is initialized.
- A finite table of instructions that, given the state the machine is currently in and the symbol it is reading on the tape (symbol currently under the head), tells the machine to do the following transition steps in sequence:
- Write a symbol from the finite alphabet replacing the one that was there. Note that the symbol written might be the same as before or different.
- Move the head either one cell to the left or one cell to the right.
- Assume the same or a new state as prescribed by the go to state.

TMD-1

The Turing Machine Demonstrator (TMD-1) will have the following characteristics:

- One tape with 10 cells and a single head.
- The alphabet used will have three symbols: {0, 1, b}. 0 will be the blank symbol and b is an endmarker symbol that can be read from the tape but not written.
- There will be three states: {A, B, C}. A will be the start state plus there is a special HALT state H.

With TMD-1 you can perform the following tasks among others:

- Treating the input area as a binary number find the one’s compliment.
- 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.
- Cylon eye with head lamps ;-)

Additional Information

- If you are interested in more details about Turing machines in general the Wikipedia entry is very good.
- For background on TMD-1 in particular, I have a blog on Hackaday where I chronicle the journey I took conceiving and building A Turing Machine Demonstrator.
- I have also written a small booklet, TMD-1 Quick Start Guide, that describes the operation of TMD-1 and helps the user run their first “program”.

OK. Let’s build a TMD-1.

Supplies:
In addition to the 3D printed parts you will need:

1 - Arduino Mega 2560
27 - 3 mm White LEDs - Amazon - Gikfun LED Lamps 3 mm White Light Super Bright for Arduino.
27 - 220 R Resistors - 1/4 Watt
33 - SS451A Hall Effect Sensors - Digi-Key part number 480-3587-ND - Digital Switch Omnipolar Switch Open Collector Hall Effect TO-92-3
8 - SG90 Micro 9g Servo - Amazon - RioRand® SG90 Micro 9g Servo For RC Airplane Car Boat Genuine
2 - 16 Channel GPIO Expander - Universal Solder - for Arduino etc. with MCP23017 and I2C Interface.
5 - Micro Switches - Amazon - Gikfun Micro Switch Long Hinge Lever (Pack of 20pcs) for Arduino EK1713)
1 - Slider Switch - Amazon - uxcell® 2 Position 3P SPDT Panel Mount Micro Slide Switch
5 - feet 22 AWG hookup wire
50 - Breadboard Jumper Wires Female to Female 0.1” Square Head - Amazon - Hellotronics (15 cm, F/F)
50 - Breadboard Jumper Wires Female to Female 0.1” Square Head - Amazon - Hellotronics (30 cm, F/F)
50 - Breadboard Jumper Wires Male to Female 0.1” Square Head - Amazon - Hellotronics (15 cm, M/F)
50 - Breadboard Jumper Wires Male to Female 0.1” Square Head - Amazon - Hellotronics (30 cm, M/F)
4 - M3 bolts 3 mm x 12 mm
30 - 3 mm x 1.5 mm Disc Rare-Earth Neodymium Magnets - Amazon - MB-THISTAR

There are a couple of custom PCBs required as well. I could not attach the ZIPs containing the files to fab the PCBs to this Instructable but you can get them from my Hackaday blog linked above.”

Link to article