TMD-1: a Turing Machine Demonstrator

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:
  1. 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.
  2. Move the head either one cell to the left or one cell to the right.
  3. 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.

Step 1: Print the Parts

I printed the parts with the following settings (unless other wise specified):

Print Resolution: .2 mm

Infill: 20%

Filament: AMZ3D PLA

Notes: No supports. Print the parts in their default orientation.

To make a TMD-1 you will need to print the following parts:

• 6 - A Tile - Set a color change at 6.2 mm to print the A.
• 6 - B Tile - Set a pause at the 2.6 mm mark to insert a magnet and a color change at 6.2 mm to print the B.
• 6 - C Tile - Set a pause at the 2.6 mm mark to insert a magnet and a color change at 6.2 mm to print the C.
• 6 - H Tile - Set a pause at the 2.6 mm mark to insert 2 magnets and a color change at 6.2 mm to print the H.
• 6 - Left Tile - Set a color change at 6.2 mm to print the L.
• 6 - One Tile - Set a pause at the 2.6 mm mark to insert a magnet and a color change at 6.2 mm to print the 1.
• 6 - Right Tile - Set a pause at the 2.6 mm mark to insert a magnet and a color change at 6.2 mm to print the R.
• 6 - Zero Tile - Set a color change at 6.2 mm to print the 0.
• 1 - Tile Rack (optional) - To hold all the programming tiles.
• 8 - Display Digit Clip
• 8 - Display Digit One - Set a color change at 6.2 mm to print the 1.
• 8 - Display Digit Zero - Set a color change at 6.2 mm to print the 0.
• 1 - Display Digits Cradle
• 1 - Finite State Machine Panel Braces - Within this file print 2 long pieces, 2 short pieces, and 4 corners.
• 1 - Finite State Machine Panel Left - Print the Right and Left pieces if your print bed is too small. Set a color change at 2.2 mm to print the text.
• 1 - Finite State Machine Panel Right - Set a color change at 2.2 mm to print the text.
• 1 - Finite State Machine Panel - Do not print Right and Left if you can print this panel on your printer. Set a color change at 2.2 mm to print the text.
• 1 - Hall Sensor Wire Bending Jig - To make sure that all of the Hall Effect sensors are mounted the same.
• 1 - Hexagonal Lamp - For HALT
• 27 - Triangular Lamp - Various uses.
• 1 - Push Button 1-0 - For the 1/0 push button. Set a color change at 15.2 mm to print the 1/0.
• 5 - Push Button Frame - To hold the 5 push buttons.
• 2 - Push Button Left-Right - For the < and > push buttons. Set a color change at 15.2 mm to print the < and >.
• 1 - Push Button Play - For the play push button. Set a color change at 15.2 mm to print the play symbol.
• 1 - Push Button Reset - For the reset push button. Set a color change at 15.2 mm to print the reset symbol.
• 1 - Slider Switch Frame - For the STEP/RUN toggle switch.
• 1 - Slider Switch - For the STEP/RUN toggle switch.
• 1 - Tape Panel Braces - Within this file print 1 long piece, 1 short piece, and 2 end pieces.
• 1 - Tape Panel Left - Print the Right and Left pieces if your print bed is too small. Set a color change at 2.2 mm to print the text.
• 1 - Tape Panel Right - Set a color change at 2.2 mm to print the text.
• 1 - Tape Panel - Do not print Right and Left if you can print this panel on your printer. Set a color change at 2.2 mm to print the text.
• 6 - Transition Table Reader Holder - To secure the Transition Table Reader PCB to the Finite State Panel.

Step 2: Assemble the Tape Panel

There are two major parts to the TMD-1, the Tape Panel and the Finite State Table Panel. We'll work on the Tape Panel first. Note that there are a few "mini-Instructables" in this step plus a reference to another related Instructable.

The Tape Panel

The Tape Panel will hold a "Flip-Byte" and implement the Tape Head. In addition some buttons will be added to allow the user to reset the tape to a default state and to modify the bits and starting head position on the tape prior to running the machine should they choose. It looks like this:

Make a Flip-Byte

The Flip-Byte forms the display component of the Tape Panel. A Flip-Byte is made up of eight Flip-Bits each of which can show either a 1 or a 0. There is a separate Insructable for making a Flip-Byte. So following the Flip-Bit Instructable steps make a Flip-Byte. Here is a Flip-Byte assembly ready to go:

Make Some Buttons

The tape control buttons will go into the four spots on the upper right of the panel. Rather than buying "off the self" I decided to design my own buttons so that I could coordinate the look with the numerous panel mounted lamps that will be used for this build. Anyone that has seen some of my other work will not be surprised by this.

So we are talking about a simple push button switch here that I built around the small micro switch listed in the Supplies section. Here are the mostly printed parts:

Assembly is pretty straight forward. Start by sliding the micro switch into the base piece making sure that the lever actuator does not extend past the edge of the base (there is one right and one wrong way to do this).

Next slide the button into the console mounting piece. Make sure that the slot on the button is aligned with the smaller slot at the top of the shaft.

Now attach the base piece to the bottom of the console mounting piece. I used a small amount of glue to hold it firmly in place.

Finally (for now) slide the locking tab into the slot at the top.

This will keep the button from popping out and when it is time to mount the button on the panel it will serve to hold the button assembly in place on the panel

This is the "Reset" button. Also make two Left-Right buttons and a 1/0 (Flip) button.

Make Some Lamps

Since the Tape itself is fixed it means that the Tape Head has to move. There is a spot under each cell of the tape for a lamp that will indicate the "current" position of the Tape Head. The lamps are just simple white high intensity 3 mm LEDs with a custom 3D printed housing. Here are the parts:

Nothing to the assembly. Start by sliding the LED into to the hole at the base of the lamp as far as it will go. I bend the leads slightly apart to make the next part easier.

Then press the small plug into the hole keeping the leads separated. This will hold the LED firmly in place.

And that's it. When it comes time to mount the lamp to the panel the small C clamp pictured below will hold it in place.

You will need ten of these lamps for the Tape Panel.

Tape Panel Assembly

I can't say enough about the Hilbert Curve Top Layer infill option in PrusaSlicer for getting a nice even looking matte finish on the large panel surfaces.

If your print bed is large enough print the Tape Panel as one piece, but as you can see I had to print mine in two pieces, so the first order of business is to connect them together. I printed some braces to assist with this task. I use some gel superglue along the edges and to attach the braces.

Next install the Flip-Byte unit to the panel with four 3 mm x 10 bolts. The holes in the Flip-Byte are sized to self thread.

Then it's a simple matter of adding the control buttons and the Tape Head current position lamps.

That's it the Tape Panel is ready to be wired into the rest of the project.

Step 3: Assemble the Finite State Machine Panel

Note that there are a few "mini-Instructables" in this step as well.

The Finite State Machine

The core of a Turing machine is the Finite State Machine, a finite set 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 how to transition to the next state of the computation. These Finite State Machines are usually described in one of two ways. As state transition diagrams:

or as state transition tables:

For this build the input will be accomplished using a state transition table. So this is what the input area for TMD-1 will look like:

The blank boxes in the table above will have shallow rectangular depressions into which appropriately labeled "tiles" can be set: 1/0 for Write, L/R for Move, and A/B/C/H for Goto. TMD-1 will be able to "read" these tiles to determine the definition of the state machine. I'm calling this my "Azul" interface based on the name of the popular tile based board game.

Reading Tiles

The reading of tiles will be accomplished with Hall Effect sensors placed under the state transition table and small magnets placed in the tiles themselves.

Tiles will be identified based on their row and "magnetic" signature. So tiles placed in the WRITE row will be considered to be a 0 or 1 based on the absence or presence of an embedded magnet. Similarly the MOVE row will assume the placement of R and L tiles. The GOTO row must recognize four different tiles (A, B, C, and H) so two magnet positions will be used to create four unique identities.

Since the parts themselves are so small and to ensure that they line up correctly with the input squares on the Finite State Machine transition table I created a PCB "reader" board.

So the user will be able to "program" TMD-1 by simply using tiles to "fill out" a state transition table for the Finite State Machine. I don't think it gets much easier than that.

Preparing The Transition Table Reader

First I installed the headers that will bring out the signals for the 33 Hall Effect sensors. These are mounted on the back of the board. Once soldered, trim the short leads on the front of the board as close as possible to the PCB.

Next I started installing the sensors. There are a couple of things I had to be careful of here. Since I wanted the sensor to lie flat on the PCB I needed to make a 90 degree bend in the leads. It was also important to do this consistently for all sensors so I made a little jig.

The idea is to lay the sensor into the slot as far up as it will go.

And here is the second important thing. The sensor must be "face up". That is to say the face with the two facets visible on the left and right and the lettering must be visible. Holding the sensor firmly in place, bend the leads back 90 degrees.

The outer leads can then be spread out slightly from the center lead, inserted into the front of the board, and soldered in place.

Repeat 32 more times.

The Finite State Machine Panel

The Finite State Machine Panel will hold the transition table input area. In addition:

• numerous lamps will highlight the current “internal state" of the machine.
• a slider switch will be added to allow the user to toggle between "Run" and "Step" modes.
• there will be a "Play" button to start or step the machine.
• a special lamp will indicate when the machine has entered the HALT state.

It looks like this:

As with the Tape Panel the controls have been designed specifically for this project.

Make a Slider Switch

A slider switch will drop into the top right corner of the panel with labels RUN and STEP. It is simply a standard miniature slider switch with a custom 3D shell to give it a "look" consistent with the rest of the project. Here are the parts:

Start the assembly by cutting off the two top plate mounting holes from the switch

then sliding the switch into the base piece as far as it will go. You might need a bit of glue to hold it in place.

Next attach the base piece to the bottom of the console mounting piece. I used a small amount of glue to hold it firmly in place.

Finally attach the slider to the shaft of the switch. Again apply a drop of glue to hold it in place.

Don't forget to save the C clamp (pictured in the first photo) to hold this switch in place when mounted onto the panel.

Make a Play Button

Exactly the same is the buttons used for the Tape Panel but with a slightly different look.

Make a Halt Lamp

Same design as the indicator lamps on the Tape Panel but with a different diffuser design.

Finite State Machine Panel Assembly

Like the Tape Panel the Finite State Machine Panel was printed in two parts.

Here I also printed some braces and used some gel superglue along the edges and to attach the braces.

Mounting the Transition Table Reader

The Transition Table Reader is mounted on the back of the Finite State Machine Panel. The Hall Effect sensors must be carefully aligned with the shallow indentations where the tiles will be placed so that they can get a good read on the embedded magnets.

I found that the easiest way to do this was to hold the Transition Table Reader board roughly in place behind the Finite State Machine Panel while shining a bright light through the PCB from behind. You will be able to see the "black dots" of the sensors through the thin floor of the tile cutout areas. For the top two rows the single "dot" should be in dead the center of the tile cutout areas.

The last row has two dots for each cutout that should be diagonally arranged at equal distances from their corresponding corners in the cutout area.

When everything is lined up tape the PCB in place. (NOTE: This process is much easier if two people are involved.)

I printed some brackets to hold the Transition Table Reader board in place.

Carefully go around the PCB replacing the tape with the brackets that get glued to the back of the Finite State Machine Panel.

Almost done in this photo.

Add the Switches and Lamps

Install the lamps and switches as shown in the next two photos.

One final sensor alignment check. Looking good!

And now that's the Finite State Machine Panel ready to be wired into the rest of the project.

Step 4: Make a Console to Hold the Panels

Without going into a lot of details, I designed the TMD-1 console. In hind sight I think I took my inspiration from the Commadore PET computer. I guess retro is part of my DNA now.

I created the following DXF files.

Tape Panel Box

Finite State Machine Panel Box

Console Frame

I laser cut these files from 6 mm plywood. The Tape Panel Box and the Finite State Machine Panel Box were assembled separately with glue and a few brad nails.

Corner clamps were a big help here.

Then I attached these two assemblies to the Console Frame pieces.

Once the glue was dry I painted the whole console a light gray color.You can see in the above photos where I added some Velcro to hold the panels in place.

Step 5: Wire the Tape Panel

At the same time that I was having the Transition Table Reader board made I had a small PCB done to help wrangle the wires from the eight servos.

I just added headers to allow me to plug the servo connectors into the board with the PWM signals brought out.

Not Enough Pins

Now you would think that since I am using an Arduino Mega there would be enough I/O pins to go around. The Mega has 54 I/O pins plus the 16 Analog pins can be used as digital I/O for a total of 70! Well it turns out I need 74 in total. The breakdown:

• 27 outputs for LEDs
• 33 inputs for Hall Effect sensors
• 8 outputs for Servos
• 6 inputs for buttons and switches

I could have used a Charlieplexing Matrix for the LEDs and a Keyboard Matrix scheme for the sensors but that would have made my programming job that much harder.

Instead I chose to use a couple of 16 Channel GPIO Expanders based on the MCP23017 part.

I'll use one for the 10 LEDs and 4 buttons on the Tape Panel, and the other for all 16 LEDs on the Finite State Machine Panel. Using these also has the advantage of "localizing" some of the wiring making for a neater job. It's also nice that they have extra VCC and GND pins in addition to doubling up on the control pins making wiring easier.

Wiring the Tape Panel

I started by joining all of the ground leads together for the LEDs and buttons then added a jumper so I could attach the grounds to one of the expander's extra GND pins.

To the LED anodes and the normally OFF terminal of the push buttons I attached jumper cables with female connectors to mate with the expander. I also added 220 R limiting resistors to the LEDs.

I mounted the Servo Control And Expander PCBs to the inside of the Tape Panel Box part of the frame using two sided tape.

The following connections were made:

From	To
Servo 3 pin connectors from left to right.	Servo Control left to right (middle to edge of board). Make sure that the leads have the proper orientation.
LEDs from left to right.	Extender Pins: PA7, PA6, PA5, PA4, PA3, PA2, PA1, PA0, PB0, PB1
Move Right Button	Extender Pin: PB7
I/O (Flip Bit) Button	Extender Pin: PB6
Move Left Button	Extender Pin: PB5
Reset Button	Extender Pin: PB4
Tape Panel: GND	Extender Pin: GND
Servo Control Pin: VCC	Extender Pin: VCC
Servo Control Pin: GND	Extender Pin: GND

Connecting to the Arduino

I mounted the Arduino below the Tape Panel boards to a reinforcing cross bar that I had added to the console again using two sided tape.

The following connections were made:

From	To
Servo Control PMW pins left to right.	Arduino Pins: 2, 3, 4, 5, 6, 7, 8, 9
Extender Pin: GND	Arduino Pin: GND
Extender Pin: VCC	Arduino Pin: VCC
Extender Pin: SCL	Arduino Pin: SCL (21)
Extender Pin: SDA	Arduino Pin: SDA (20)

Done Wiring

That's it. The Tape Panel is completely wired up and ready for testing.

Step 6: ​Wire the Finite State Machine Panel

As with the Tape Panel I started by wiring all of the ground leads together for the LEDs and buttons then added a jumper so I could attach the ground(s) to one of the Expander's extra GND pins.

I added limiting resistors to all of the lamps.

Then I mounted a second Expander PCB to the back of the Finite State Machine Panel with two sided tape and connected all 16 of the purple status lamps to it. I had to change the I2C address for this board so it would not conflict with the first. There are jumpers for this.

Here are all the connections made:

From	To
Lamps: C, B, A, READ, WRITE, MOVE, GOTO, A1, A0, Ab, B1, B0, Bb, C1, C0, Cb	Extender Pins: PB7, PB6, PB5, PB4, PB3, PB2, PB1, PB0, PA0, PA1, PA2, PA3, PA4, PA5, PA6, PA7
Transition Table Reader +5V	Extender Pins: VCC
Transition Table Reader GND	Extender Pin: GND
Wire Ground	Extender Pin: GND

I installed the Finite State Machine Panel onto the console and proceeded to wire the 33 Hall Effect Sensors to the Arduino.

Here are the Arduino pins the sensors are connected to:

A1	A0	Ab	B1	B0	Bb	C1	C0	Cb
WRITE	22	23	n/a	24	25	n/a	26	27	n/a
MOVE	28	29	30	31	32	33	34	35	36
GOTO 1	37	38	39	40	41	42	43	44	45
GOTO 2	46	47	48	49	50	51	52	53	10

In addition the following connections were made:

From	To
HALT Lamp	Arduino Pin: 11
PLAY Button	Arduino Pin: 12
RUN/STEP Switch	Arduino Pin: 13
Extender Pin: GND	Arduino Pin: GND
Extender Pin: VCC	Arduino Pin: VCC
Extender Pin: SCL	Tape's Extender Pin: SCL
Extender Pin: SDA	Tape's Extender Pin: SDA

Done Wiring

That's it. The Turing Machine Demonstrator hardware is completed.

Step 7: Make Some Tiles

TMD-1 tiles are 20 mm wide, 25 mm high, and 6 mm deep. The trick is that some of them have small embedded magnets. This is done by creating a "void" inside the tile STL files large enough to comfortably hold the magnet. When the tile STL file is being sliced a print pause is introduce at the first layer printed above the void. Here are all the different tiles:

and this is the where the pause should be introduced:

This also shows how each tile is encoded. So when printing these tiles, and the printer pauses, simply drop a magnet into each of the holes then resume the print. It should be noted for these tiles that a second "change filament" command will be added to switch to black filament for the lettering.

So I made a bunch of tiles and a rack to store them in.

Step 8: Wrapping Up

This has been a very fun, exciting, and rewarding project for me. Fun because well, all my projects are fun or I wouldn't be putting so much time and effort into them. Exciting because I really loved the idea of TMD-1 and unlike my more usual "reproduction" projects this one was an original idea that allowed me to exercise my creative juices. Rewarding because the end result turned out so much better than I could have imagined.

I've been so consumed by all things Turing for the past two months that it's hard for me to judge if I have achieved my "easy to understand" goal. It's certainly easy for me to understand sure, but what about someone not as immersed in the subject as I am. When I get a chance to show TMD-1 around a bit I might be able to get a better sense of whether I hit the mark or not.

I'm a little more confident to think that I have accomplished the "simple to program" goal. I loved using the "tile" interface when I was making my demonstration programs. Development is very iterative with a quick load, run, test, fix cycle. While the single step function was added as a learning feature it sure works great as a debugging tool as well. So I'm going to pat myself on the back for "simple to program".

I wouldn't necessarily say that TMD-1 was "easy to build", I will say that it was pretty straight forward though. There is nothing too tricky about the build, just a fair amount of complexity to deal with.

Step 9: Testing Your TMD-1

Plug in the Arduino Mega and load the attached Turing Machine Demonstrator sketch. Power on the machine. If everything is wired correctly and the sketch is loaded TMD-1 should look like this:

This means that TMD-1 has been initialized with the following starting settings:

• All cells in the input area have been cleared to 0s.
• The Tape Head is set to the rightmost cell of the input area.
• The State Register is set to the default starting state of 'A'.
• The Next Transition Step to be executed has been set to READ.

In other words TMD-1 is ready to go.

Next try using the Tape Panel Controls to move the Head position left and right. Make sure that the 1/0 Flip button changes the cell at the Head position correctly.

The ultimate test is of course to actually run a "program", and one of the most interesting is the "busy beaver". A busy beaver program tries to write as many 1s to the tape as possible, but it must Halt on its own. The state transition table for this 3-state "busy beaver" is pretty well known:

I'm not sure how long it would have taken me to figure this out for myself. Here is the result:

If you are having issues check all of the wiring carefully. In my case I discovered that I had two instances where I had crossed a couple of wires connecting the Transition State Reader to the Arduino. If you go into the Arduino code and remove the comment from the #ifdef DEBUG the Sketch will dump what it thinks the transition state values are to the serial monitor.