• The Finite State Panel

    Michael Gardi07/29/2020 at 16:50 0 comments

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

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

    It looks like this:

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

    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.

    Next Steps

    When the transition table reader board PCB arrives and I've had a chance to verify the alignment of the hall effect sensors with the input areas, I'll start printing the Finite State Machine board.

  • The Finite State Machine

    Michael Gardi07/28/2020 at 13:47 0 comments

    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. TMG-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.  It should be back from the fab in a few days or so now.

    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.

  • Tape Panel Assembly

    Michael Gardi07/27/2020 at 20:27 0 comments

    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 Tape Panel

    Michael Gardi07/26/2020 at 02:01 0 comments

    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:

    So while I wait for the actual Tape Panel to finish printing I thought that I would talk about the controls. 

    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.

    So when the panel is finished printing in about 14 hours or so, all will be ready for the final Tape Panel assembly.

  • The Tape Implementation (Continued)

    Michael Gardi07/19/2020 at 17:02 0 comments

    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 Implementation

    Michael Gardi07/13/2020 at 03:27 0 comments

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

  • About TMD-1

    Michael Gardi07/13/2020 at 02:01 0 comments

    Overview

    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 four states: {A, B, C, H}. A will be the start state and H is a special HALT state.

    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 / 4-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.
    • 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.

    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 state of the machine as it processes each step.  I'm very excited about this piece and will reveal more details when I've done a bit more testing.

    Controls

    In addition there will be controls to:

    • Start the machine in either Run or Step mode.
    • Enter "data" into the Tape and set the Head's start position prior to running a program.
    • Reset the Tape to a known starting state.

    The Soul of the Machine

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

    •  Implement the finite state machine as defined by the user's input.
    • Manage the movement of the Head and the changes to the Tape.
    • Process the Controls.

  • Background

    Michael Gardi07/07/2020 at 23:24 0 comments

    Not going to go into too much detail here. I just want to provide enough Turing machine background so that the pieces being designed and built will make sense.

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