TMD-3: Turing Machine Demonstrator Mark 3

They say that the third time's a charm. Let's find out.

Similar projects worth following
It's been about three years since I built my existing Turing Machine Demonstrators. The goal for TMD-1 was to build a machine that was simple to program and easy to understand. TMD-2 was designed to increase the capabilities of the first version while maintaining it's simplicity. Both versions were designed to demonstrate the idea of a Turing machine with as much clarity as possible.

TMD-3 will be a refinement of the existing machines with a new approach to implementing the "tile interface" that I believe helped me to achieve the simplicity and ease of programming goals of the first two machines.

Really Mike, why a TMD-3?

Before I talk about what TMD-3 will be, I would like to give a brief overview of Turing machines, the TMD-1 and TMD-2 designs, and what prompted me to want to do a TMD-3.

Turing Machines 101

The Turing machine was invented in 1936 by Alan Turing.  By providing a mathematical description of a very 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 (mostly from Wikipedia):

  • 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. The tape is assumed to be arbitrarily extendable to the left and to the right, so that the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. 
  • 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.
  • 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.

About TMD-1

Briefly, Turing Machine Demonstrator (TMD-1) has the following characteristics:

  • One tape and one head.
  • The alphabet used has three symbols: {0, 1, b}. 0 is the blank symbol and b is a special endmarker.
  • There are three states: {A, B, C}. A is the start state plus there is a special HALT state H.

For more details  see the TMD-1 project.

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:

Both of the above describe the same 3-state 2-symbol "busy beaver" program.

Programming a Turing Machine

When building a physical Turing Machine Demonstrator, these definitions must somehow be translated into something that the machine can understand. I have seen these state transitions encoded onto paper tape or expressed as pegs on a 2-dimensional board. Since this project is supposed to be an easy to use Turing Machine Demonstrator, I wanted this "translation" to be as simple as possible. Then it struck me, "What if the state transition table and the Finite State Machine input were one in the same?". 

The Tile Interface

So this is what the input area for TMD-1 looks like, a state transition table.

The blank boxes in the table above 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 is able to "read" these tiles to determine the definition of the state machine. I was inspired to use tiles based on the popular tile based board game "Azul" . Without a doubt the tile interface is what helped me...

Read more »

  • A Tile Organizer

    Michael Gardi09/16/2023 at 18:16 0 comments

    For my first two TMD's I made bins to hold the various tiles.

    For TMD-3 I decided to take advantage of the fairly strong magnets in the tiles so I designed a grid to hold the tiles and ordered some sheet steel to mount behind the grid to attract the tiles.

    Well live and learn. I discovered that the steel I ordered was Austenitic Stainless Steel which is non-magnetic. Fortunately it was not a costly mistake and I'm sure I'll find a use for it in the future. So my plan B was to order a small cheap magnetic white board. Much better. After removing the cheap plastic frame and cardboard backing I had a nice flat magnetic backboard.

    I cut the metal sheet to size and, using a CA glue, mounted it into the tile organizer frame that I printed.

    Similarly I glued in the tile organizer grid.

    And here it is with a set of tiles installed. 

    The magnets hold the tiles in place nicely. You can flip the frame upside down without the tiles dislodging, yet they are easy to remove when needed. I like the coordinated look of the TMD-3 and tile organizer.

  • TMD-3 Finished

    Michael Gardi09/11/2023 at 15:44 0 comments

    After playing around a bit with my TMD-3 I'm ready to say it's finished. Tiles are recognized with great accuracy which was my first goal. The end result turned out to quite compact which was something else I had hoped to achieve. Here are my three Turing Machine Demonstrators for a comparison. 

    One thing that I noticed is that the tiles themselves tend to lump together when loose due to the magnets that I used (6 mm). They are fine when placed into the state panels. I did not notice this with TMD-1 because the magnets that I used were smaller (3 mm) and the tiles much bigger and heavier. For TMD-2 the tiles didn't have any magnets at all. I did a quick test with 4 mm magnets and the effect was much less. I could also print the small tiles with 100% infill so they would be heavier. For now given the number of tiles I have printed and the time invested in calibration I'm not going to make the switch. In fact I plan to take advantage of the stronger magnets by creating a tile organizer backed with a steel sheet to hold the tiles in place.

  • Calibration

    Michael Gardi09/10/2023 at 18:28 0 comments

    I finished the tedious but not too arduous task of calibrating the SS49E Linear Hall Effect Sensors. What does this mean. Well I run a small test program that I wrote that detects the presence of a tile and emits the location of the sensor and the value returned by reading that sensor. Here is the Python code.

    import time
    import busio
    import digitalio
    import board
    import adafruit_mcp3xxx.mcp3008 as MCP
    from adafruit_mcp3xxx.analog_in import AnalogIn
    import pigpio
    # Access the gpio pins.
    GPIO = pigpio.pi()
    # Select pins for the CD4067BE.
    S0 = 23
    S1 = 27  
    S2 = 17
    S3 = 18
    # Selct pins are all OUTPUT.
    GPIO.set_mode(S0, pigpio.OUTPUT)
    GPIO.set_mode(S1, pigpio.OUTPUT)
    GPIO.set_mode(S2, pigpio.OUTPUT)
    GPIO.set_mode(S3, pigpio.OUTPUT)
    # Select the C8 pin.
    GPIO.write(S0, 0)
    GPIO.write(S1, 0)
    GPIO.write(S2, 0)
    GPIO.write(S3, 0)
    # Create the spi bus.
    spi = busio.SPI(clock=board.SCK, MISO=board.MISO, MOSI=board.MOSI)
    # Create the cs (chip select).
    cs = digitalio.DigitalInOut(board.D22)
    # Create the mcp object.
    mcp = MCP.MCP3008(spi, cs)
    # Create analog input channels.
    chan0 = AnalogIn(mcp, MCP.P0)
    chan1 = AnalogIn(mcp, MCP.P1)
    chan2 = AnalogIn(mcp, MCP.P2)
    chan3 = AnalogIn(mcp, MCP.P3)
    chan4 = AnalogIn(mcp, MCP.P4)
    chan5 = AnalogIn(mcp, MCP.P5)
    def selectPin(pin):
        if pin & 0b00000001:
            GPIO.write(S0, 1)
            GPIO.write(S0, 0)
        if pin & 0b00000010:
            GPIO.write(S1, 1)
            GPIO.write(S1, 0)
        if pin & 0b00000100:
            GPIO.write(S2, 1)
            GPIO.write(S2, 0)
        if pin & 0b00001000:
            GPIO.write(S3, 1)
            GPIO.write(S3, 0)
    # The hall effect sensor will read in the middle of the range
    # someplace. Get the middle values for all 16 sensors.
    mids0 = []
    mids1 = []
    mids2 = []
    mids3 = []
    mids4 = []
    mids5 = []
    for i in range(0,16):
    while True:
        for i in range(0,16):
            val = chan0.value-mids0[i]
            if abs(val) > 200:
            val = chan1.value-mids1[i]
            if abs(val) > 200:
            val = chan2.value-mids2[i]
            if abs(val) > 200:
            val = chan3.value-mids3[i]
            if abs(val) > 200:
            val = chan4.value-mids4[i]
            if abs(val) > 200:
            val = chan5.value-mids5[i]
            if abs(val) > 200:

    So for each of the 96 sensors I get the values for only those tiles that are valid for that position. So for instance the MOVE row only accepts L and R tiles. By only accepting valid row tiles there is some error checking, but because there are only 8 different magnet configurations, some tiles are interchangeable like the 2 and E tiles for instance.  I add those values to a table specific to the state being checked. Here is the table for the C state.

        # Add the valid tiles to each sensor along with the expected sensor value.
        # C
        # READ Row
        sensors[0][8]["tiles"] = [(-627,'b'), (282,'4')]  
        # WRITE Row
        sensors[0][4]["tiles"] = [(-435,'0'), (-301,'1'), (691,'2'), (429,'3'), (301,'4')]
        sensors[0][5]["tiles"] = [(-410,'0'), (-282,'1'), (640,'2'), (397,'3'), (275,'4')]
        sensors[0][6]["tiles"] = [(-384,'0'), (-262,'1'), (589,'2'), (365,'3'), (262,'4')]
        sensors[0][7]["tiles"] = [(-371,'0'), (-256,'1'), (576,'2'), (358,'3'), (256,'4')]
        sensors[0][9]["tiles"] = [(-358,'0'), (-250,'1'), (563,'2'), (352,'3'), (250,'4')]
        # MOVE Row
        sensors[0][0]["tiles"] = [(-205,'L'), (205,'R')]  
        sensors[0][1]["tiles"] = [(-192,'L'), (192,'R')]
        sensors[0][2]["tiles"] = [(-179,'L'), (179,'R')]
        sensors[0][3]["tiles"] = [(-179,'L'), (179,'R')]
        sensors[0][10]["tiles"] = [(-173,'L'), (173,'R')]
        # GOTO Row
        sensors[0][12]["tiles"] = [(-749,'A'), (-474,'B'), (-307,'C'), (-218,'D'), (723...
    Read more »

  • Final Assembly

    Michael Gardi09/09/2023 at 19:18 0 comments

    I attached the wired State Panels to the console frame using some two sided tape. Notice here that I have added a logo and some labels for the state panels.

    Then I connected the bottom and top row panels with the cable I made and plugged in the cable from the Pi 4.

    Finally I glued the six State Panels together to create a more stable connection between the PCBs and printed panels.

    When the glue dried I placed the joined panels into the console. Nice clean fit with no jiggle. Just what I was looking for.

    All that's left now is to calibrate the 96 sensors against this final configuration. 

  • Finished Wiring

    Michael Gardi09/07/2023 at 21:08 0 comments

    Well after installing 96 SS49E Linear Hall Effect Sensors, 6 16-channel Analog Multiplexers, 1 8-channel 10-bit A/D converter chip, and 72 wires to connect the 6 State Panels, the wiring is done.

    To make installation into the chassis easier I have made a cable and added headers to join the top and bottom rows of the state table.

    After connecting the first two State Panels together I realized that the 12 short 22 AWG wires were too "stiff" which made aligning the two joined panels harder than it should have been. So for subsequent joins I used 22 AWG for the two outside joins. and used 28 AWG wire for all the rest. Much better.

  • More Console Work

    Michael Gardi09/02/2023 at 13:59 0 comments

    I reworked the frame for the 7" Raspberry Pi Touch Display and integrated it into the existing console.

    Just four more panel PCB to populate as I approach the finishing line.

  • Two Panels Now Working

    Michael Gardi08/30/2023 at 19:25 0 comments

    So I got the second panel integrated into the Console application.

    I'm pretty happy with the way that everything is working out and now have the confidence to proceed with the additional four panels. 

    One thing that I have learned is that there is enough variance between the sensors to warrant taking the time to calibrate each sensor against the tiles that are expected to be placed in that position of the State Panel. I'm sure that despite my best efforts to position each sensor in the precise same position that readings are bound to differ. Calibrating the sensors helps to mitigate the slight difference I am finding between tiles of the same value. Here is what that calibration looks like in my code (so far).

    # Sensors connected to channel 0 of the MCP3008 8-channel A/D converter.
    # READ row.
    sensors[0][8]["tiles"] = [(-621,'b'), (275,'4')] 
    # WRITE row
    sensors[0][4]["tiles"] = [(-493,'0'), (-339,'1'), (768,'2'), (474,'3'), (339,'4')]
    sensors[0][5]["tiles"] = [(-454,'0'), (-301,'1'), (678,'2'), (429,'3'), (307,'4')]
    sensors[0][6]["tiles"] = [(-403,'0'), (-282,'1'), (627,'2'), (390,'3'), (282,'4')]
    sensors[0][7]["tiles"] = [(-397,'0'), (-275,'1'), (614,'2'), (384,'3'), (282,'4')]
    sensors[0][9]["tiles"] = [(-390,'0'), (-275,'1'), (589,'2'), (371,'3'), (266,'4')]
    # GOTO row
    sensors[0][0]["tiles"] = [(-230,'L'), (237,'R')]
    sensors[0][1]["tiles"] = [(-218,'L'), (224,'R')]
    sensors[0][2]["tiles"] = [(-205,'L'), (205,'R')]
    sensors[0][3]["tiles"] = [(-198,'L'), (205,'R')]
    sensors[0][10]["tiles"] = [(-198,'L'), (198,'R')]
    # MOVE row.
    sensors[0][12]["tiles"] = [(-877,'A'), (-563,'B'), (-358,'C'), (-256,'D'), (890,'E'), (576,'F'), (371,'H')]
    sensors[0][13]["tiles"] = [(-787,'A'), (-506,'B'), (-320,'C'), (-224,'D'), (794,'E'), (518,'F'), (339,'H')]
    sensors[0][14]["tiles"] = [(-749,'A'), (-486,'B'), (-307,'C'), (-224,'D'), (762,'E'), (493,'F'), (320,'H')]
    sensors[0][15]["tiles"] = [(-762,'A'), (-480,'B'), (-314,'C'), (-224,'D'), (755,'E'), (493,'F'), (320,'H')]
    sensors[0][11]["tiles"] = [(-749,'A'), (-474,'B'), (-307,'C'), (-218,'D'), (742,'E'), (480,'F'), (314,'H')]

    If you look at the columns for each row and tile you can see a variance of as much as 100 in some cases.

    Another thing that I want to look at is to somehow attach the printed panel to the PCB so that the calibration doesn't change. (Two sided tape maybe?)  Right now the panels are just resting on the PCBs.

  • Starting to Put Together the Console

    Michael Gardi08/29/2023 at 14:58 0 comments

    I populated a second State Panel PCB with the Linear Hall Effect Sensors and  a CD4067BE multiplexer.  Only the first panel needs to have a MCP3008 8-channel A/D converter. I then connected the two panels together via the bus pins with some AWG22 solid core wire.

    I designed and printed a frame to hold all six State Panels.

    Notice that the second (leftmost) panel is wired to Channel 1 of the MCP3008 on the first panel  (via the bus).

    One more change, I increased the size of the cutouts on the bottom of the printed panel so that the panel and the PCB now lie flush.

  • Demonstration of the State PCB

    Michael Gardi08/23/2023 at 15:00 0 comments

    Here is a short video of the State PCB in action.

    I also posted the KiCad files I used to produce the PCB to GitHub.

  • Setting Up the Pi

    Michael Gardi08/21/2023 at 18:49 0 comments

    Up until now I have been running all my tests on the Raspberry Pi that I used for my TMD-2 project. I'm moving to a new Pi so I though I would document the steps I have taken to get the Console running on the new image.

    I'm not going to detail getting the Raspberry Pi OS onto the Pi 4 as there are a lot of guides out there like this one from tom'sHARDWARE.  Basically I just loaded a Raspberry Pi OS image onto a 32G microSD card using Raspberry Pi Imager.

    I plugged the microSD card with the brand new OS image into the Pi 4 I have been using for testing with it's small LCD screen, wireless mouse, and keyboard.  You could do the installation completely "headless" as outlined here,  but I prefer to do the configuration interactively with this setup. I powered up the Pi and went through the initial configuration dialogs to set the login user, keyboard, language, locale, and wireless connection.  Super easy.

    Ultimately the Pi could be running headless with no keyboard or mouse. There will however be a display to show the console's screen.  My preference is to use VNC to accomplish this. Raspberry Pi OS ships with RealVNC pre-installed.  So the first thing that I did after the basic OS had been installed was to setup a virtual server for the RealVNC client to connect to. The easiest way I have found to do this is to add the following lines to the end of the /etc/rc.local file before the exit 0 on the Pi.

    # Setup a virtual screen for the VNC server.
    sudo -u xxxxxx vncserver-virtual -randr=1920x1080
    # Start the Pi GPIO daemon.
    sudo pigpiod

    xxxxx is the login user that you setup to access the Raspberry Pi. Set the screen dimension (randr=) to be the same as the machine that you will be accessing the TMD-3 Console from. 

    At the same time that I added the virtual VNC server I added the "sudo pigpiod" line to start a daemon that the console needs to access the Pi's GPIO pins.

    I found in my setup that there were a few issues accessing this server with the RealVNC client on my Windows machine. The first was that the menu bar at the top of the desktop was missing.  If you encounter this issue, to restore the desktop menu bar enter the following command.

    sudo apt-get remove --purge alsa-base pulseaudio

    On a similar note the title bar on open application windows and the corresponding windows controls (v ^ x) were missing as well. To fix this I edited the desktop.conf file,

    sudo nano /etc/xdg/lxsession/LXDE-pi/desktop.conf

    and changed the line:

       window_manager=mutter    to    window_manager=openbox-lxde-pi

    then saved the changes.

    An additional library is required by the Console to interact with the MCP3008 ADC chip used to "read" the Hall Effect sensors.  To load the library:

    sudo pip3 install adafruit-circuitpython-mcp3xxx

    With these changes made reboot the Pi 4 for them to take effect.

    I downloaded and installed the RealVNC client on my Windows machine.  Run the RealVNC VNC Viewer. You should see this window.

    From the menu select File->New connection... to bring up the following dialog. Add the Server address and common name then click OK.

    Note the :1 added to the server address. This references the instance of the VCN Server running. 

    To find the VNC Server address you can just hover over the WiFi (or network) connection on the server desktop.

    From the main VNC Viewer window double click on the TMD-3 connection just created.

    The first time you attempt a connection you will be prompted to enter the Raspberry Pi's login credentials. Check Remember password if you don't want to have to do this every time you connect. Enter the credentials and click OK.

    You should see an instance of the Pi 4's desktop.

    Be To get the Console onto the Pi 4 you can simply clone the repository from github. Open a terminal...

    Read more »

View all 19 project logs

Enjoy this project?



Dan Maloney wrote 09/17/2023 at 22:31 point

Hey Mike --

Love it! Clever way to reduce the BOM and keep from killing the budget on Hall sensors. Nicely done. Wrote it up for the blog, should publish soon. Thanks for tipping us off!

  Are you sure? yes | no

Michael Gardi wrote 09/18/2023 at 13:36 point

As always thanks Dan.

  Are you sure? yes | no

Peabody1929 wrote 07/20/2023 at 20:23 point

A Raspberry Pi 4 to run a Turing Machine?  What would Turing say?

  Are you sure? yes | no

Michael Gardi wrote 07/20/2023 at 20:44 point

Turing might have said something like, “idiot, you’re not supposed to build the bloody thing!”  The Pi 4 is from my TMD-2 machine where I needed it to do OCR. Obviously something lesser would do here.

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates