Close
0%
0%

TMD-1: A Turing Machine Demonstrator

Develop a Turing machine that is simple to program and easy to understand.

Similar projects worth following
There are numerous Turing machine implementations covered on this site 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 from the onset will be to demonstrate the idea of a Turing machine with as much clarity as possible. I want to build a machine that is simple to program and easy to understand. If the end result is also easy to build, so much the better. I guess that's my lofty goal for this project. Wish me luck.

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

There are numerous variations to the general Turing machine described above.  Some have multiple tapes and/or heads. Some tapes are bound (have an end) on the left or right or both. In addition Turing machines have varying numbers of symbols in their alphabets and varying numbers of states. The Turing Machine Demonstrator (TMD-1) will have the following characteristics:

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

Tale of the Tape

Having a tape that is "arbitrarily extendable" to the left or right would pose some serious implementation issues, not to mention being complete overkill for a 3-symbol / 3-state Turing machine. So I have chosen to implement a restricted form of Turing machine called a "linear bounded automata" (LBA). 

In addition to the normal Turing machine behaviors, an LBA has the following three conditions:

  • The input alphabet includes two special symbols, serving as left and right endmarkers. In an effort to simplify things even further, TMD-1 will only have a single endmarker symbol (b) in it's input alphabet. 
  • Transitions may not print other symbols over the endmarkers. In addition, TMD-1 will not allow an endmarker to be written to the other part of the tape (b is not part of the tape alphabet).
  • Transitions may neither move to the left of the left endmarker nor to the right of the right endmarker. For TMD-1 such a move will HALT the machine.

In other words, instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers.  It will look something like this:

The end cells (endmarkers) cannot be changed and furthermore cannot be written to the other portion of the tape. So the "input" part of the tape will only ever contain zeros and ones.

Only Eight Cells?

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

Read more »

TMD-1 Quick Start Guide.docx

A short introduction to what TMD-1 is and how it works.

document - 2.07 MB - 09/08/2020 at 14:22

Download

Transition Table Reader.zip

PCB to mount the 33 Hall Effect Sensors used to read the tiles in the Finite State Machine.

application/x-zip-compressed - 15.67 kB - 08/27/2020 at 23:40

Download

Servo Control.zip

PCB to manage the wiring for the 8 servos.

application/x-zip-compressed - 6.58 kB - 08/27/2020 at 23:40

Download

Flip-Bit Zero.stl

The 0 side of a flip bit.

netfabb - 495.20 kB - 07/13/2020 at 03:29

Download

Flip-Bit One One.stl

The 1 side of a flip bit.

netfabb - 425.28 kB - 07/13/2020 at 03:29

Download

View all 6 files

  • Postscript #2

    Michael Gardi08/31/2020 at 04:11 0 comments

    The TMD-1 Instructable has been posted. Much of the information duplicates what you can find here but in addition the Instructable includes all of the files required to build a TMD-1 (STL, DXF, etc,).

  • Postscript #1

    Michael Gardi08/26/2020 at 15:58 0 comments

    For all of the vintage "toy" computers that I have made reproductions of one thing stands out,  they all had excellent manuals.  To that end I have created the TMD-1 Quick Start Guide, a small 10 page document that contains:

    • A brief description of what a Turing machine is.
    • A summary of TMD-1's characteristics.
    • An explanation of what the various parts of TMD-1 are and what they do.
    • What you should expect when you power-up TMD-1.
    • A step-by-step guide to writing and testing a simple TMD-1 program.

    I don't know if it's excellent or not, but my hope is that this will be all a person needs to understand and use TMD-1. I'm going to try it out on a few people to see if they can start writing programs (without any help from me) . I have posted the guide as a Word doc to the the Files section.

  • Wrapping Up

    Michael Gardi08/25/2020 at 08:23 0 comments

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

    Next Step

    My plan over the next week or so is to create a TMD-1 Instructable. I'll post all the build files and details there and add a link to the Instructable here.

  • TMD-1 Quick Start Guide

    Michael Gardi08/24/2020 at 21:38 0 comments

    Welcome to TMD-1, the state of the art in Turing teaching technology.  

    Overview

    To get started let's deconstruct the Tape and Finite State Machine Panels to take a look at the main components of the machine and find out what they do.

    TAPE

    Reset: When pressed will set all input area cells to '0', position the Head at the rightmost input area cell, set the current STATE to 'A', and set the Next Transition Step to READ.

    Left: Move the Tape Head one cell to the left if after a Reset. If in RUN mode will make TMD-1 run slower. Can also be used to position the Head prior to running.


    Flip: Flip the symbol at the current Head position. In conjunction with Left and Right allows you to setup "data" in the input area.

    Right: Move the Tape Head one cell to the right if after a Reset. If in RUN mode will make make TMD-1 run faster. Can also be used to position the Head prior to running.

       Tape Controls:

    Tape: Turing machines are all about the tape. While some Turing machines have tapes that are infinitely long in one or both directions, TMD-1 has a more modest fixed tape length of ten cells. The left and rightmost cells have a special fixed symbol 'b' called an endmarker which can be read but not written on. The other eight cells comprise the "input area" of the Tape and can be set to either '0' or '1'. 

    Head: One lamp will be ON at any given time indicating the current position of the Tape Head.

    FINITE STATE MACHINE

    Transition Steps: The transition step to be executed next is highlighted. This is the step that will be executed when the PLAY button is pressed.
    State Register: The current active state will be highlighted here. By definition the state 'A' will always be the starting state. 

    Transition State Table: This is where you "program" TMD-1 by defining the transitions between states. You do this by placing tiles in the blank spaces that are appropriate to the Transition Step row they are being placed in. 

    For WRITE row tiles are '0' and '1',  for MOVE 'L' and 'R', and for GOTO 'A', 'B', 'C', and 'H'.


    Transition Indicator: Once the READ step has been performed, the current active transition column determined by the combination of current state and symbol being read will be highlighted.

    Finite State Machine Controls:

    RUN - TMD-1 will run the program until the HALT state is reached.

    STEP - Each time the PLAY button is pressed a Transition Step will be executed.


    PLAY - Use the PLAY button to start the machine RUNning or to execute the Next Transition Step.


    HALT - Will light up when TMD-1 has reached the HALT state.

    On System Start or Reset 

    When the machine is first turned on or has just been Reset you should see: 

    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.

    Your First TMD-1 Program

    With the "introductions" out of the way we are going to jump into the deep end and create our first Turing Machine Demonstrator program. The problem is simple:

    • Write a program to invert all of the symbols in the input area. So all 1s become 0s and vice-versa.

    Let's get started.

    Laying Some Tiles

    Programming TMD-1 is as simple and filling in the State Transition Table with the provided tiles.  Let's see how this works.

    When that first READ is executed, the symbol read could be any one of '1', '0', or 'b'. Since we are in the 'A' state, we will have to fill in all three Transitions associated with those symbols and 'A'. 

    Starting with '1', since we are inverting we are going to want to WRITE a '0' to the cell.  All of the remaining input cells to be processed are to the left of the current Head position...

    Read more »

  • Hardware Done

    Michael Gardi08/24/2020 at 19:12 0 comments

    With all the testing I have been doing I'm convinced that the hardware and firmware (an Arduino Sketch) are solid and ready for prime time.  So far I have written and successfully run TMD-1 "programs" to do the following:

    • 3-State / 2-Symbol busy beaver
    • 1s compliment of input area
    • 2s compliment of input area
    • counting (ascending)
    • shifting (left) / multiply by 2
    • sorting all 1s in input area to the left

    So I'm declaring the TMD-1 hardware officially finished.

  • Programming More Demonstrations

    Michael Gardi08/24/2020 at 16:42 0 comments

    I've been having a lot of fun "programming" my TMD-1. It's actually a pretty cool development environment. Just lay down the tiles in the state transition table, press reset to load the table into memory and initialize the machine, then press the Play button. STEP mode is extremely useful for "debugging" your program as you might expect.  I can really see TMD-1 as an interactive tool for teaching Turing concepts.

    I created a sorting program. It's purpose is to move all of the 1s to the left most side of the input area. This demonstration also show how you can use the controls on the Tape unit to reset a value in the input area and position the Head prior to running the program. Here it is in action:

    This next one I didn't program myself. 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:

    All in all I'm really happy with how TMD-1 is working.

  • Only Eight Cells?

    Michael Gardi08/22/2020 at 16:19 0 comments

    One might think having an eight cell "input area" would  limit the tasks TMG-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 2-symbol (assume the b is not used)/ 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 TMG-1 is prohibited from using the endmarker. symbol I won't spoil the ending but this programs runs fine in eight cells.

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

    • Treat the input area as a binary number and 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).
    • Make a 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 cell for the input area.

  • Testing and a First Demonstration

    Michael Gardi08/20/2020 at 20:22 0 comments

    Testing went well. On the hardware side I only had two incidents with crossed wires from the Transaction Table Reader to the Arduino and a single broken LED that needed replacing. Otherwise the build was pretty solid.

    Coding also went faster than expected. I'm still tweaking the UI a little but as you can see in the demo that follows IT WORKS (I'm so happy).

    Without further adieu here is TMG-1 in action counting to ten. Basically the head adds one to the number already present in the input region (between the b markers) then goes back to the beginning and repeats.

    How fast the machine works in RUN mode is one of the things I'm still playing around with.  I want people to see what is going on with each step but not get too frustrated waiting for things to happen. Maybe TMD-1 should RUN faster leaving the learning to STEP mode.  UPDATE: I have made a change so that you can now press the left and right arrow buttons on the Tape Panel when in RUN mode to decrease  or increase the running speed. 

  • Finite State Machine Panel Wiring

    Michael Gardi08/19/2020 at 06:58 0 comments

    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:

    FromTo
    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 +5VExtender Pins: VCC
    Transition Table Reader GNDExtender 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:

    A1A0AbB1B0BbC1C0Cb
    WRITE2223n/a2425n/a2627n/a
    MOVE282930313233343536
    GOTO 1373839404142434445
    GOTO 2464748495051525310

    In addition the following connections were made:

    FromTo
    HALT Lamp Arduino Pin: 11
    PLAY ButtonArduino Pin: 12
    RUN/STEP SwitchArduino Pin: 13
    Extender Pin: GNDArduino Pin: GND
    Extender Pin: VCCArduino Pin: VCC
    Extender Pin:  SCLTape's Extender Pin: SCL
    Extender Pin: SDATape's Extender Pin: SDA

    Done Wiring

    That's it.  The Turing Machine Demonstrator hardware is completed. More testing and a lot of coding are in my immediate future.

  • Tape Panel Wiring

    Michael Gardi08/16/2020 at 14:11 0 comments

    Wire Wrangling

    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:

    FromTo
    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, P A6,  PA5,  PA4,  PA3,  PA2,  PA1,  PA0,  PB0,  PB1
    Move Right ButtonExtender Pin: PB7
    I/O (Flip Bit) ButtonExtender Pin: PB6
    Move Left ButtonExtender Pin: PB5
    Reset ButtonExtender Pin: PB4
    Tape Panel: GNDExtender Pin: GND
    Servo Control Pin: VCCExtender Pin: VCC
    Servo Control Pin: GNDExtender 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:

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

    Done Wiring

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

View all 20 project logs

Enjoy this project?

Share

Discussions

B.B wrote 09/13/2020 at 21:03 point

Would your reproduction DEC H-500 have enough logic to implement the state machine for this (excluding the tape)?

Or maybe implement it in TTL? https://archive.org/details/byte-magazine-1976-12/page/n115/mode/1up

  Are you sure? yes | no

Michael Gardi wrote 09/20/2020 at 13:37 point

The H-500 definitely does not have enough logic elements to implement a state machine.

The Byte article was very cool. I wish there had been some pictures of an actual implementation. I love the idea of a dedicated CPU with a single “state machine” instruction. You could for sure use this in lieu of the Arduino for the state machine “core” but still need the Arduino to read the sensors and buttons and drive the LEDs. 

  Are you sure? yes | no

Dan Maloney wrote 08/25/2020 at 21:40 point

Mike, this is fantastic! I watched a few of your programs run and it's finally clear to me how Turning machines work. Thanks so much for the work on this - it really helped me understand things better.

One question: How is the concept of the "head" implemented? I see that the head markers light up as the state machine transitions left and right, but is the head actually reading any physical property of the cell above it? Or are you instead reading the state of the cell by knowing the state of the servo that controls that flip-bit?

  Are you sure? yes | no

Michael Gardi wrote 08/25/2020 at 23:31 point

Early versions of the design had the head actually moving up and down the tape (stepper and belt mechanism) and reading the value with a Hall Effect sensor like the State Transition Table. At the end of the day I felt that there was not enough value add from a learning point of view to warrant the substantial additional complexity of implementing this compared to what I ended up with. It would have been cool though ;-)

To answer your question, there is an internal array in the Sketch that keeps track of the tape values. This does allow me to not trigger a servo call if the value to be written is already set.

  Are you sure? yes | no

Michael Gardi wrote 08/26/2020 at 02:22 point

Thanks for the kind words. I’m glad that TMD-1 helped you understand Turing machines better. That was my hope going into this project. 

  Are you sure? yes | no

Michael Gardi wrote 08/12/2020 at 22:36 point

@Michael Möller  Thanks!  Appreciate the interest. 

  Are you sure? yes | no

agp.cooper wrote 08/01/2020 at 06:19 point

Hi Michael,

I have finally finished my Turing machine! It has been coded with "Busy Beaver 4", which has 107 steps.

I thought I had screwed up the schematic again but my problem was old code on the flash chip.

Although a flash chip seems like a cheat, it can be replaced with a diode array ROM if more retro feel is important.

My TD4B CPU uses a 16 bit by 8 bit diode array for programming and it works well.

Still it is an interesting demo for those interested in the Turing Machine.

Regards AlanX

  Are you sure? yes | no

Michael Gardi wrote 08/01/2020 at 09:04 point

Congratulations! Very cool project. You should post a short video of your creation in action. In a few weeks I too hope to join the small “club” of people  who have built working Turing machines. 

Mike

  Are you sure? yes | no

agp.cooper wrote 08/02/2020 at 05:28 point

Hi Michael,

I was independently making a video for my project!
It's not fancy, 5fps and 640x480 to make the file small:

  http://alanx.surge.sh/

AlanX

  Are you sure? yes | no

Dan Maloney wrote 07/06/2020 at 20:22 point

Good luck, and keep us posted - this sounds really interesting!

  Are you sure? yes | no

Michael Gardi wrote 07/06/2020 at 21:16 point

Thanks Dan. You can expect to see log entries over the next couple of weeks. I'm pretty excited about this project.

  Are you sure? yes | no

agp.cooper wrote 07/06/2020 at 07:12 point

I have had a go at this (https://hackaday.io/project/27528-the-turing-computer-plays-busy-beaver-iii), I have a board waiting (months and months!) to be populated. I just can't get it (the design) right (maybe this time).

Anyway, the tape per say is not much of an issue for a demonstration purposes. I used LEDs and the 74HC194 for my machine. I ordered a set of 74HC194s months and months ago and they only just turned up last week. Basically I forgot about them.

The finite state machine is the place where something clever is needed. Perhaps a "Turtle" like language.
I am however only focusing on the Busy Beaver problem. This seems to be the best bang for buck for a demonstration Turing Machine.

Regards AlanX

  Are you sure? yes | no

Michael Gardi wrote 07/06/2020 at 12:49 point

Hi AlanX,  I've started following your project, obviously I'm interested in all things Turing right now.  It looks interesting and I look forward to seeing a working busy beaver machine.  I totally agree that the busy beaver is a pretty cool demonstration of a Turing machine.  

I have some ideas for the finite state machine, but I want to do some more design work before I talk about it.  

Mike

  Are you sure? yes | no

agp.cooper wrote 07/09/2020 at 14:18 point

Now that I have the parts, I just have to find the PCBs, and I will try again to get it working. Last time it was because I did not actually get address 00 upon reset.

AlanX

  Are you sure? yes | no

Michael Möller wrote 07/05/2020 at 08:47 point

"Good luck"

(IMHO many Turingmachine focus too much on the Tape, and not enough on the StateMachine)

  Are you sure? yes | no

Michael Gardi wrote 07/05/2020 at 17:05 point

Thanks Michael. I’ll keep your suggestion in mind. 

  Are you sure? yes | no

Michael Möller wrote 08/12/2020 at 22:02 point

Well, you really nailed the state machine! (The StateMachine log entry)

  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