TMD-2: Turing Machine Demonstrator Mark 2

Fusion Projects »

This Instructable is a follow-on to my TMD-1: A Turing Machine Demonstrator project.

I was really happy with the way that TMD-1 turned out. I believe I succeeded in creating a Turing machine that was both "simple to program" and "easy to understand". To help accomplish those goals, the machine itself was limited to only 3 states, 3 symbols, and a small 10 cell bounded tape. Fine for educational purposes, but a bit anemic if you want to explore Turing machines with a little more depth.

For this project I wanted to "up the ante". I made a 6 state, 6 symbol machine, with a large tape capacity. As much as possible I tried to bring forward the simple to use, easy to understand principles from TMD-1.

In this Instructable I will focus on the steps required to build a TMD-2. However I think that a little background will be required now and then to provide context to the build, like now for instance.

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-2

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

One tape with 100,000 cells and a single head.
The alphabet used will have seven symbols: {0, 1, 2, 3, 4, 5,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 six states: {A, B, C, D, E, F}. A will be the start state plus there is a special HALT state H.

With TMD-2 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.
Run "busy beaver" programs with up to six states.

Additional Information

If you are interested in more details about Turing machines in general the Wikipedia entry is very good.
For background on TMD-2 in particular, I have a blog on Hackaday where I chronicle the journey I took conceiving and building the Turing Machine Demonstrator Mark 2.
I have also written a small booklet, TMD-2 Quick Start Guide. It describes the operation of TMD-2 and helps the user run their first "program". You will find the guide attached to this instructable.

OK. Let's build a TMD-2.

Supplies

In addition to the printed parts you might require:

Raspberry Pi - Mine was a Raspberry Pi 4 with 2GB of memory.
Raspberry Pi Camera Module - Mine was an 8-megapixel V2 model.
Raspberry Pi Touch Display - The 7″ touchscreen monitor.
Raspberry Pi Flex Cable - At least 1 meter, mine was 2 meters.
6 Feet of 3 1/2 x 3/4 inch lumber (approximately).
10 Feet of 1/2 x 1/2 inch doweling.
1 Piece of 1/8 inch plywood at least 364 x 224 mm.

Step 1: Decide How Much TMD-2 You Want to Make

At it's heart, TMD-2 is a stand-alone program written in Python. If you just want to try the application, it will run on any computer that supports Python (which is most machines), skip ahead to the Installing the TMD-2 Software step to get started.

I built my TMD-2 using a Raspberry Pi with a Raspberry Pi 7" touchscreen display as my computer. A display holder was designed to house these parts and becomes the console for my overall project. You can load the "console" with the TMD-2 software and stop there. This configuration makes a nice "desktop toy" Turing machine. I added a wireless mouse and keyboard to my configuration but they are not required.

For a full blown TMD-2 experience you might want to build the Finite State Machine input panel. You can then program the Turing machine by populating this transition table with 3D printed "tiles". Using a Raspberry Pi camera module, these tiles are "scanned" into the machine by processing an image from the camera with OCR software.

How much TMD-2 do you want?

Step 2: Print the Parts

Depending on what TMD-2 configuration chosen, you might be printing some or all of the parts listed here. 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-2 you will need to print the following parts:

1 - Raspberry Pi Display Holder
4 - Display Locking Tabs
10 - Tile 0 Note: Print all of the tiles white. Pause the prints at the 6.2 mm mark and switch to black.
10 - Tile 1
10 - Tile 2
10 - Tile 3
10 - Tile 4
10 - Tile 5
10 - Tile b
10 - Tile L
10 - Tile R
10 - Tile A
10 - Tile Big B
10 - Tile C
10 - Tile D
10 - Tile E
10 - Tile F
10 - Tile H
1 - A State Transition Table Note: Print all of the tables white. Pause the prints at the 4.2 mm mark
1 - B State Transition Table and switch to black.
1 - C State Transition Table
1 - D State Transition Table
1 - E State Transition Table
1 - F State Transition Table
1 - State Labels
1 - Tile Bin Base Note: Only print the following if you want to make a bin for your tiles.
1 - Tile Bin Base Left Note: Only print the Left and Right bases if the base above is too big.
1 - Tile Bin Base Right
15 - Tile Bin
1 - Tile Bin Labels Note: Print in white. Pause the print at the 1.2 mm mark and switch to black.

Step 3: Assemble the Console

Not much to this step really. Attached the Raspberry Pi to the back of the display following the instructions that came with the display and can also be found here.

Set the display into the back of the Raspberry Pi Display Holder and secure in in place with the Display Locking Tabs as pictured above.

Step 4: Assemble the Finite State Machine Panel

A little background on finite state machines.

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-2 will look like:

The blank boxes in the table above will have shallow rectangular depressions into which appropriately labeled "tiles" can be set: 0/1/2/3/4/5/b for WRITE, L/R for MOVE, and A/B/C/D/E/F/H for GOTO. TMD-2 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.

Assembly

Start by printing the six State Transition Table "cards" with rectangular indentations for tiles, one for each state (A, B, C, D, E, F).

Next build a base to hold the state "cards" and a legend with labels for each row. Use the 3 1/2" x 3/4" lumber for the frame. Use the 1/2" x 1/2" to create a "ledge" for a 1/8" piece of plywood to sit in.

The two important things here are that the plywood piece should sit about 1/8" below the top of the frame and should be 14 1/3" x 8 57/64" (364 mm x 224 mm) in size to ensure that the cards and legend fit in snugly.

A little white paint plus the addition of the printed State Transition Table pieces looks like this.

I found an articulated arm design by Chris Rogers (hackoholic) on Thingiverse. His motion capture rig is very similar to the base that I built so it's a good fit. Build the arm as per Chris's "Thing". The arm is mounted onto the back of the State Transition Table box centered on the table itself (above the B).

The Raspberry Pi camera snaps snugly into the camera mount and the ribbon cable slides easily through the guides. Great design!

Connect the Finite State Machine Panel's camera with the Console's Raspberry Pi following the instructions that came with the camera or found here.

And that's it for the hardware.

Step 5: Installing the TMD-2 Software

Requirements

There are only two prerequisites for the basic TMD-2 application to run.

Python 3 must be installed onto the target machine.
PyGame modules must be loaded into the Python environment.

How this is done is going to vary depending on what operating system you are using. Here is a great link on How to Install Python 3 in various environments. Similarly here is a link to Install PyGame into those same environments.

Installing TMD-2

Go to the Turing Machine Demonstrator Mark 2 releases page on github.
Download the Source code archive for the latest release, either the .zip or the tar.gz file.
Unpack the archive retrieved into a folder of your choice.

Running TMD-2

Open a command prompt.
Navigate to the folder that you expanded the Source code into.
Run the command: python3 Tmd2Console.py

You should see the following window open:

Learning TMD-2

With the application running I highly recommend that you work through the TMD-2 Quick Start Guide that is attached to this Instructable. The first part will tell you how the TMD-2 application works, followed by an exercise that will teach you how a Turing machine works. At the end are some additional challenges for those that want to learn more.

Auto Start TMD-2

If you are running TMD-2 as a dedicated console on a Raspberry Pi like I am it's convenient to have the program start automatically when the machine boots. Here is what I did to make this happen.

I created an autostartfolder on my Pi and switched to that folder.

mkdir /home/pi/.config/autostart
cd /home/pi/.config/autostart

Into the autostart folder just created I added the following two files.

runTmd2

cd /home/pi/Apps/Tmd2Console
/usr/bin/python3 Tmd2Console.py

TMD-2.desktop

[Desktop Entry]
Type=Application 
Name=TMD-2
Exec=/home/pi/.config/autostart/runTmd2

In addition the runTmd2 file must be made executable with the following command:

chmod -x runTmd2

If you reboot the system, you should briefly see the desktop appear, and shortly after TMD-2 application will load.

Step 6: Installing the Camera and OCR Software

If you are going to use the Finite State Machine input panel there is some additional software that needs to be installed. These instructions are for the Raspberry Pi Raspbian operating system only.

Camera Software

Since we are accessing the Pi camera from a Python environment we need to install the picamera library. Picamera was already part of my Raspbian distribution. If it isn't on yours, from a command line on your Raspberry Pi run:

$ sudo apt-get update
$ sudo apt-get install python-picamera python3-picamera

OCR Software

TMD-2 uses the Tesseract OCR library. To use OCR a few packages have to be installed, namely:

tesseract-ocr
libtesseract-dev
pytesseract
opencv

The tutorial Optical Character Recognition Using Raspberry Pi With OpenCV and Tesseract describes how to install these packages.

Step 7: Running the TMD-2 State Transition Table Scanner

As delivered via github, the TMD-2 application is configured to run in stand-alone mode without a camera. To enable the camera, and the ability to Scan the State Transition Table panel, edit the Tmd2Console.py file and change line 4 from hasCamera = False to hasCamera = True.

When you start Tmd2Console.py again, you should see the screen pictured above. You will notice a couple of differences. First the application is full screen, meant to fill all of the Raspberry Pi display without any "window" controls. The other difference is the new SCAN button. If you click SCAN, the following full screen dialog will appear.

The screen shows a still image of the State Transition Table panel taken by the Raspberry Pi camera. If you need to adjust the articulated arm to achieve a view similar to the one above, click on the REFRESH button to enable continuous updates of the image so that you can make adjustments. When you are happy that the image contains the whole table (the labels to the left don't matter), and that the table edges are relatively square to the image frame (ie. the table should not be skewed too much from a rectangle), click REFRESH again to stop continuous updates.

Use the purple "rubber bands" to outline just the table. When you are done setting the outline, click on the START button to scan the tiles. Here is a video of the capture process in action.

Note that in this example the tiles do not represent a true Turing program, they were just included for demonstration and testing purposes. You only have to do this "setup" on the first use of SCAN. Subsequent scans will update the photo and remember the outline settings so that all you should have to do is click START.

Step 8: Make Some Tiles

If your are using the State Transition Table panel you will need a bunch of tiles. I printed about 10 of each for a start. The tiles should be printed in white with black symbols for best OCR results.

I have included the STL files for a simple parts box in this Instructable, but any cheap parts organizer will of course do.

Step 9: Final Thoughts

Designing and building TMD-2 was a great "stretch" experience for me. For the hardware, I had never worked extensively with the Raspberry Pi or Pi Camera. On the software side I had never used Python or PyGame before. So I learned a lot putting TMD-2 together.

Python is a great language but it took a little getting used to. I come from a mostly Java background so giving up on { } as block delimiters felt pretty unnatural. Even after a few months with Python, I still find myself wanting to put a ; at the end of lines. And I never did get the hang of using the _ in variable names, and stuck with camelCase. But that's just me. Python certainly lives up to it's cross-platform name. Development of the console application shifted smoothly between my Windows/Eclipse development environment and my Raspbian target environment. When I started integrating the camera and switched to the Pi for all my development, I found I was easily able to use RealVNC from my laptop to develop on the Pi, which gave me more screen real estate since the only display I had on the Pi was the a 7" touch-screen.

PyGame was recommended to me, and I'm glad that I chose it as the framework for the console. The only thing that I missed was some sort of GUI module. I tried integrating a number of the recommended external libraries, but in the end created my own dialogs in PyGame itself. The disadvantage of doing this is that my implementations were a little feature light, but on the other hand they maintained the aesthetic of the overall application.

There was more software development in this project than I thought there would be. When I first started, I was thinking of TMD-2 as the hardware successor to TMD-1. I would build the hardware and write a little program for the console. Somewhere in the middle of writing the console, I realized that what I was doing would make a pretty good stand-alone application. I added features so that the program could be run without the camera based input, primarily allowing the state table to be edited with mouse clicks. And since Python is cross platform, it would run almost anywhere. In the end I was thinking of TMD-2 to as a Turing machine program, that took the ease of use and simple to program concepts from TMD-1, and made them accessible to a much wider audience. TMD-2 also supports a cool optional tile based interface for defining the state transition table.

I think with the completion of TMD-2 that I have Turing machines out of my system for a while. On to the next project whatever that might be.

I'll leave you with a video of TMD-2 running a 3-state 2-symbol "busy beaver" program in DEMO mode.