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):

    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:

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:

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 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 3-symbol / 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 TMD-1 is prohibited from using the endmarker symbol. I won't spoil the ending but this program runs fine in eight cells.

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

You get the idea. As an LBA the Turing Machine Demonstrator is a much more capable teaching tool even with only eight cells for the input area.

Finite State Machine

There will be an area on TMD-1 that will allow a user to both define the behavior of the finite state machine (basically the program), as well as see the current internal state of the machine as it processes each step.  

Controls

There will be controls to:

The Soul of the Machine

Driving everything will be an Arduino Mega 2560 as I anticipate needing a lot of I/O pins to drive all of the above. The Mega will:

The Tape Implementation

Having decided that the Tape would be of a fixed size with endmarkers, it was time to consider the underlying implementation.  Given the fixed length it seemed simplest to have the Tape be stationary with a movable Head.  

Since the endmarkers are immutable, only the inner cells of the tape would ever change between 0 and 1.  Such a binary implementation could be accomplished in number of ways including a simple on/off LED. I thought about 7-segment and LCD displays.  I started thinking that something more analog would be a good fit for this project and Flip-Dots (Flip-Disks) came to mind.  Then it struck me, not Flip-Dot but...

Introducing Flip-Bits

I'll just string eight of these together to form the "input" area of my tape. I'll call that a Flip-Byte ;-)

Making a Flip-Bit

First print the parts. The STL files have been posted to this project.

You will also require a standard SG90 Micro 9g Servo (from Amazon: SG90 Micro 9g Servo For RC Airplane Car Boat Genuine).

Glue the 1 and 0 pieces together. Use the pegs to help align the two pieces.

To prepare the servo cut down one of the included horns at the third small hole from the center.

Make sure the servo is in it's 0 position. I hooked mine up to an Arduino and wrote a small program to do this. Attach the horn parallel to the long axis of the servo as shown below.

Slide the 0/1 flipper piece loosely into the base.

Insert the servo into the base then push the flipper onto the horn.

Finally snap the c shaped spacer onto the flipper shaft to hold everything in place.

And voila, a Flip-Bit. 

To test the Flip-Bit:

#include <Servo.h>

// Create servo object to control a servo.
Servo myservo;  

void setup() {
  // Attaches the servo on pin 9 to the servo object. 
  // Adjusts the min and max pulse widths, in microseconds, 
  // corresponding to the minimum (0-degree) and maximum
  // (180-degree) angles on the servo.
  myservo.attach(9, 500, 2450);  
}

void loop() {
  // Show the zero.
  myservo.write(0); 
  delay(500);  
  
  // Show the one.
  myservo.write(180); 
  delay(500);       
}

I found that I had to tweak the min and max values for the servo attach() method to get the flipper to line up horizontally.

The Flip-Byte

Having sorted out the mechanics with the Flip-Bit it was time to extend that to the 8 bits I will be using for the Tape, a Flip-Byte. So I mashed together 8 of the bases used for the Flip-Bit and came up with this:

Then following the instructions for constructing the Flip-Bit 8 times I ended up with this:

Ready to be mounted under the Tape Panel.

The Tape Panel

The Tape Panel will hold the 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:

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 a small micro switch (Amazon: Gikfun Micro Switch Long Hinge Lever (Pack of 20pcs) for Arduino EK1713) that I had lying around. 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 my "Reset" button. More to come.

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 (Amazon: Gikfun LED Lamps 3MM White Color White Light Super Bright for Arduino (Pack of 100pcs) AE1124) 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 separate. 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.

Tape Panel Assembly

The Tape Panel print went well. I can't say enough about the Hilbert Curve Top Layer infill option in PrusaSlicer for getting a nice even looking matte finish.

As you can see I had to print this 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 I installed 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.

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.

When building a Turing Machine, these definitions must somehow be manifested in a way that the machine can understand them. 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 a 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?".

State Machine Setup

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

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

Once I determine how I wanted the Finite State Machine input to work, I had to figure out how to make it work. My first idea was to use magnetic reed switches, but I had been looking for an excuse to play around with Hall Effect Sensors. So I ordered some SS451A Omnipolar Magnetic Switches from Digi-Key. 

I guess I shouldn't have been, but when they arrived I was surprised at how small these components were. I chose the omnipolar part because I didn't want to have to worry about the polarity of the "triggering" magnets. 

I setup a test. First I secured one of the sensors to the back of a small panel that I printed to represent a tile input square on my state machine. 

I connected this to an Arduino so that when the sensor was triggered an LED would light. Then I printed a couple of test tiles.

The tile with the "1" has a small 3 mm x 1.5 mm magnet embedded .6 mm from the bottom and centered in the tile, while the "0" tile has no magnet. Here is my first test:

Testing showed that the hall effect sensor can clearly be triggered by some very small magnets embedded into the tiles. Furthermore I found that the magnet must be lined up within a few millimetres of the central axis if the sensor. This is a good thing because it means that multiple sensors can be embedded within a small area (the tiles are only 20 mm x 25 mm) without the risk of interfering with each other. 

Tiles will be identified based on their row and "magnetic" signature. So tiles placed in the WRITE row will be considered to 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.

This will be mounted directly below the input area of the transition table.  

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.

Making 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 a rack to store them in.

The Finite State Machine Panel

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

It looks like this:

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

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 (Amazon: uxcell® uxcell20Pcs 2 Position 3P SPDT Panel Mount Micro Slide Switch Latching Toggle 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.

Play Button

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

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.

Preparing The Transition Table Reader

The PCB I designed for this arrived this week.

I have to admit this is version 2. The first board was too big. I had failed to allow enough clearance for the lamps and switches that will surround it. Also I found that the .05 pitch spacing for the TO-92 leads was a bit too challenging for my soldering skills, so I spread the leads out to .1 pitch in this version. Live and learn I guess. Costly lesson though.

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.

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.

"Console"idating 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. 

While there is still a great deal of wiring and programming work to do, this is pretty much what the final project will look like.

In this photo you can also see the finished "programming" tiles and a rack I made to hold them.   On to the wiring.

Tape Panel Wiring

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:

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.

Finite State Machine Panel Wiring

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.

Testing and First Demonstration

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

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. Without further adieu here is TMD-1 in action counting to ten. 

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. 

Programming More Demonstrations

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 shows how you can use the controls on the Tape unit to set 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.

TMD-1: Quick Start Guide

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: 

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:

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 so MOVE should be an 'L'.  We will stick with 'A'' for the GOTO state, since there may be more 1s to process in the same way. With the '1' Transition column done:

The '0' Transition will be very similar except we want to WRITE the inverted '1' symbol:

And finally if we encounter the 'b' symbol we know that the whole input area has been processed so just HALT. It doesn't matter what MOVE direction we use here:

So that's it. Our first program is finished, using only a single state to accomplish the task. But is the program correct? We should probably STEP through the first Transition to make sure everything is working as expected.

Slow and Steady 

Using the STEP feature is a great way to debug a TMD-1 program. 

Before we can start testing the program we just "entered" we have to press the Reset button in order to "load" the State Transition Table into TMD-1's memory.  Having done that, set the RUN/STEP toggle switch to STEP and press the PLAY button once:

We can see that the READ operation has selected the 'A0' Transition to execute which is correct since we are in state 'A' and the Head is on a '0' cell. The Next Transition Step has been set to WRITE. Check!

Press the PLAY button again:

WRITE was execute and the Head's cell has been update to a '1'. Next Transition Step set to MOVE. Check!

Press the PLAY button again:

Next Transition Step set to GOTO. Head has been correctly moved one cell to the left. Check!

Press the PLAY button one more time:

GOTO has Transitioned back to the 'A' state and is ready to READ the next cell. Check!

All is looking good. Time to RUN the program and see what happens.

Running 

I pressed Reset again to reestablish my clean starting state and switched the RUN/STEP toggle to RUN. You will see at the beginning of the video that I used the Tape Controls to put a few 1s into the input area to get some good test data, being careful to position the Head back at the rightmost input area cell before pressing the PLAY button. Here is the result:

Your Next Program

Hopefully I've convinced you how easy it is to write a TMD-1 program. A good next step might be to extend the inversion program we just wrote. 

If you consider the input area with its 0s and 1s to be a binary number, then what the inversion program does is to create what is called the 1s compliment of that number. The 2s compliment of a binary number is just the 1s compliment of the number to which a 1 is added (mathematically). 

You have 2 whole unused states to add the 2s compliment functionality. Are you up to the challenge?

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.

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.