Close
0%
0%

TMD-2: Turing Machine Demonstrator Mark 2

Build a Turing machine based on TMD-1 but with support for more states and symbols.

Similar projects worth following
I was really happy with the way that my TMD-1: A Turing Machine Demonstrator turned out. I believe it met the stated goals of "simple to program" and "easy to understand". To help accomplish those goals the machine itself was limited to 3-states / 3-symbols, and a small 10 cell bounded tape. Fine for educational purposes, but a bit anemic if you want to explore Turing machines with a little more depth.

So for this project I'm going to try to "up the ante". My goal is to make a 6-state / 6-symbol machine. As much as possible I will try to bring forward the simple to use, easy to understand principles from TMD-1.

Why Another Turing Machine Project?

This started with a comment made by Newspaperman5: "Sweet! I would love a smaller and/or more capable version of [TMD-1] as a desk toy!", and it made me realize that I did too!  I loved messing around with TMD-1. The tile interface is fun to use. There is enough there for educational purposes but I found that I am wanting more.

In this next iteration I will try to bring forward the simple to use, easy to understand, principles from TMD-1, but the emphasis will definitely be on increasing the overall functionality. 

I'm thinking a 6-state / 6-symbol machine would be a good target. With it for instance, you could explore the 5-state / 2-symbol "busy beaver" problem for which there is still no definitive solution. Pretty cool. 

So that's the why, and a little bit of the what, so now I just have to figure out the how.

Keeping the Tile Interface?

IMHO the best part of TMD-1 is the tile interface. Programming the machine by filling out the State Transition Table with "special" tiles feels natural, something about the tactile nature of the process I guess. It's also a lot of fun. I've had a few people run through the Quick Start Guide on my TMD-1 and they all agree: easy and fun. So if at all possible I would like to keep using tiles.

Keeping the tile interface with the larger machine does have some serious issues however, the biggest of which is that the technology that I used to "read" the tiles does not scale well. It took 33 Hall Effect Sensors to interpret the 24 tiles on the State Transition Table for TMD-1.  A 4-state / 4-symbol machine would require 88 sensors, and my 6-state / 6-symbol machine would need 252 sensors.  At about $2 apiece it adds up pretty quick, not to mention the wiring nightmare. Clearly this will not work. I need a better way.

To keep the State Transition Table layout down to a reasonable size with a 6-state / 6-symbol machine, the tiles themselves will have to be significantly smaller that those on TMD-1, as much as one quarter the size perhaps. I think that this would rule out something like NFC or RFID. The tags would just be too close together and even if they were not, you would have to implement a mechanism to move a reader across each tile. Still need a better way I think. 

Newspaperman5: suggested: "My only viable solution would be to place 2 electrodes on each block with a resistor in it, and then reading the resistance, but that makes block-production pretty complicated compared to just placing a magnet or 2 in them, and I’m not sure how reliable it would be". Interesting idea, but I must say that I agree with his comments about block-production and reliability. Also for larger machine you would still have to somehow route 150 inputs into analog pins on the controlling CPU. 

About the only thing that I can think of that might work is Optical Character Recognition (OCR). Mount a camera above the State Transition Table matrix, take a picture,  and process the resulting image. In a past life I had the opportunity to work with Tesseract.  An OCR engine originally developed by Hewlett-Packard as proprietary software in the 1980s, Tesseract was released as open source in 2005 and development has been sponsored by Google since 2006. Having used the software, I am fully aware of its limitations. While it works quite well at deciphering and extracting the text from say the page of a book, a letter, or other similar documents, one often gets poor results when trying to read from a structured layout like say a "State Transition Table". Still I am pretty confident that I can get it to work.

What Technologies?

Having decided to at least try using OCR, and Tesseract specifically, I need to decide what I'm going to run my new machine on. Throw in the requirement that, if all goes well, I will have to take a picture of the State Transition Table of my larger machine to apply...

Read more »

  • Is TMD-2 a Universal Turing Machine?

    Michael Gardi2 days ago 0 comments

    Short answer, yes. Turing machines with state-symbol pairs of (4,6), (5, 5), and (6, 4), have all been proven to be "universal". So TMD-2, with 6-states and 6-symbols, certainly qualifies. But what does this mean?

    Simply put a universal Turing machine (UTM) is one that can simulate any arbitrary Turing machine on arbitrary input. It achieves this by reading both the description of the machine to be simulated, as well as the input to that machine from its own tape.  Another way to put this: the first part of the tape contains an arbitrary Turing machine's state transition table (program) that has been encoded to the tape's input alphabet, and the rest of the tape holds the input to be operated on. The state table of the UTM itself "executes" this program on the tape by shuttling the tape head back and forth between the state table area and the input area, all the while following the rules that have been established for Turing machines like only reading and writing from the head position, and only moving one cell at at time to the left or right. 

    Since there is no "memory" in a Turing machine (except for the current state register), the process of executing a program on the tape requires that the tape itself be used to remember the current state of the program being executed and the current head position within the input area (at a minimum). This can be accomplished by having two symbols for each tape input, like 1 and say x for a 1 that is also the current position of the tape head, or as in Turing's own example leaving empty spaces on the tape for such markings.

    Here are a few links that really helped me understand UTMs. They all come from a post by Mark L Lyons where talks about the book Formal Languages and Their Relation to Automata by Hopcroft and Ullman.  

    Frankly it hurts my head trying to think about writing a UTM program, especially with only 6-states and 6-symbols to work with, but I accept that it can be done because other people way smarter than me say it is so. 

  • Speeding Up the OCR

    Michael Gardi3 days ago 0 comments

    I was a little disappointed with how long TMD-2 took to capture the state transition table symbols via OCR.  I had mentioned in my previous log that the pytesseract library "executes" the whole Tesseract engine for each call, essentially using the command line interface, and I was making a call once for each table cell.  My planned switch to  tesserocr, which integrates directly with Tesseract's C++ API using Cython, didn't pan out due to segmentation fault integration issues.  

    So I began looking at how I might use Tesseract itself to speed things up. Tesseract has a lot of options. One in particular --psm allows you to define what the image you are passing in represents. Here is the full list of options:

    0 = Orientation and script detection (OSD) only.
    1 = Automatic page segmentation with OSD.
    2 = Automatic page segmentation, but no OSD, or OCR. (not implemented)
    3 = Fully automatic page segmentation, but no OSD. (Default)
    4 = Assume a single column of text of variable sizes.
    5 = Assume a single uniform block of vertically aligned text.
    6 = Assume a single uniform block of text.
    7 = Treat the image as a single text line.
    8 = Treat the image as a single word.
    9 = Treat the image as a single word in a circle.
    10 = Treat the image as a single character.
    11 = Sparse text. Find as much text as possible in no particular order.
    12 = Sparse text with OSD.
    13 = Raw line. Treat the image as a single text line,
         bypassing hacks that are Tesseract-specific.

    I had been using option 10 - "Treat the image as single character. ".  I started thinking about what it would take to use option 8 - "Treat the image as a single word. ".  With "words", I knew it would be important to preserve the spacing between symbols so that they could be written into the correct cells.

    The first thing that I tried was to "read" whole rows from the table across the three state panels. I was hoping that the cells with squares would register as a period (.) or dash (-) or even a space( ), but no such luck. So I took the image of the state table and substituted an M for each empty cell. Here is what a final image that is used for OCR looks like:

    And when I OCR each row (skipping the state headers) as a "word" I get the following results back:

    01234b01234M01234M
    524130MMMMMMMMMMMM
    LLRLRRMMLRMMMMRLMM
    CEBFADMMMMMMMMMMMM
    01234M01234M01234M
    MMMMMMMMMMMMMMMMMM
    MMLLMMMRRMMMMML4MM
    MMMMMMMMMMMMMMMMMM
    

     I tried using other characters as space substitutes like X and +, but M seems to work the most reliably. I do some reasonableness checks on the retrieved text, like the "word" should be 18 characters in length and should only ever contain characters from the tile set. If this is not the case, I mark the character or row with X's. When retrieving a cell value from the "table" above, if the value is an X,  I OCR for just the character since single character recognition seems to work better than word based OCR. 

    Here is my new capture process in action:

    I have gotten the whole table refresh process down to under 10 seconds. I'm pretty happy with that.

  • Putting It All Together

    Michael Gardi6 days ago 0 comments

    Yesterday I finally got the UI, camera, and OCR pieces of TMD-2 all working together. Here is a short video where I "scan" the State Transition Table tiles with the Pi camera into the UI using Tesseract OCR to determine the symbol in each "cell".

    This is running on my Raspberry Pi 4 but I am using RealVNC to capture this video.

    One thing you will notice is that the process is not particularly fast. Sigh. I am using the pytesseract library to interface with the underlying OCR engine. I am calling the engine once for each cell because tesseract does not work well with tables.  Under the covers, pytesseract "executes" the tesseract engine for each call, essentially using the command line interface. It works well but with significant overhead.  

    I had hoped to switch to the tesserocr which integrates directly with Tesseract's C++ API using Cython. With it you only invoke tesseract once and use the same instance for making all of your calls. Unfortunately I could not get this to work. Just loading the library in my environment cased a segmentation fault.  

    So what happened when I clicked on SCAN?  First the Pi Camera took the following picture of my state table panel. 

    Note that this does not represent a Turing program, I just added some tiles to the panel for testing purposes. This image is used as the background for the Scan dialog so that the user can isolate the state table part with the "rubber band" rectangle. Now I could have figured out this bounding box for the table with some clever programming, and I have done this in the past, but the techniques were error prone enough that I ended up using the "rubber bands" as a backup anyway, so I though in this case I would just "cut to the chase" as it were.

    When the user clicks START, the bounding box is used to create a "cropped" image that is passed to the OCR code.

    Notice that the bounding box doesn't have to be perfect, but the edges in the photo should not be too skewed for good OCR fidelity.  The image processing pipeline that has been mentioned in previous logs has changed a little. I starts the same with a conversion from color to greyscale.

    Then I do a contrast equalization step.

    The equalized image is converted to binary.  As has been mentioned, the table borders are removed by applying a single white color "flood fill" to them. I'm amazed at how well this works.

    And finally a dilation is applied to the image to reduce noise.

    At this point, in my previous trials, I would apply some edge detection and contouring to determine the bounding boxes for each of the tile symbols. Now however, because I know that the bounding box for the table has been well defined, I can just calculate the positions of each cell with reasonable accuracy. Without the borders, there is enough white space around the symbols to provide a good margin of error. So I just go ahead at this point and OCR the cells. As each cell is recognized, the value is passed back to the UI for display.

    Once all of the cells have been recognized, the state table in the UI looks like this.

    Notice that some of the cells have a purple ?. When loading the cell values, I do a reasonableness check on each. If a symbol does not belong in the cell based on the allowable row values, the ? is shown instead. This is what we see for the L in A-4-WRITE, the  1 in A-3-MOVE, and the 4 in D-3-MOVE. This can happen if the user places a tile in the wrong row, or if the OCR engine fails to identify the a symbol correctly. At this point the user can correct the errors in the UI, or fix the cells on the panel and rescan.

    I have updated github with the new and modified files. Note that the Tmd2Console application will still run stand-alone without needing a camera or OCR.

  • The TMD-2 Application Has Been Posted to Github

    Michael Gardi11/01/2020 at 17:52 0 comments

    As promised in my previous log, I have uploaded my TMD-2 application to a github repository.  While it is still intended to be the console for my TMD-2 project with the capability of reading from my tile based state transition diagram panel,  I have found it to be a pretty good stand alone application. The repository contains the following:

    • Tmd2Console.py - The Turing machine application script.
    • TMD-2 Quick Start Guide -  In both DOCX and PDF formats, this guide talks a little bit about Turing machines in general, and the TMD-2 implementation specifically.  It shows you how to run the TMD-2 application with examples.
    • *.png - These are the various image assets required by the application.
    • beavern.tmd2 - beaver3, beaver4, and beaver5 are pre-built TMD-2 "programs" for 3-State, 4-State, and 5-State busy beaver implementations. They are referenced in the Quick Start Guide.

    A few caveats:

    • As this script is designed to be my console application, the screen size is fixed at 800 x 480 pixels, which is the resolution of the 7" display that I am using. As much as possible I have tried to parameterize the placement and size of the screen objects through constants in the script, so it should be relatively easy to make adjustments should you wish to do so.
    • I believe that PyGame is the only dependency, but I'm new to the Python environment so I could be wrong about this.
    • I have been developing and testing with Python 3.8 and am not sure if other releases will work or not.
    • This is definitely not the final version. I still have to add the OCR code to read the state table panel for sure, but  there will undoubtedly be other changes as well.
    • I have done quite a bit of testing, but the code is definitely not "production" ready. 
    • This is my first Python program. Be kind. I know that underscores (_) are all the rage in Python land, but I'm a CamelCase guy from way back and couldn't quite get the hang of doing it differently. 

    So that's about it.  If you do give this program a try, I would appreciate any feedback, good or bad.

  • TMD-2 The Program?

    Michael Gardi10/28/2020 at 00:12 0 comments

    I've continued to work on the TMD-2 user interface while getting the finite state machine running. When I was implementing the state machine, I found myself wanting to enter values into the state transition table to test various features, so I created the ability to add symbols by clicking on the table cells. Each click advances to the next valid symbol for that cell in a circular fashion.  Clicking on the top part of the cell will switch to the previous symbol, while a click on the lower part will go to the next symbol. Note that I had already implemented a similar scheme for the tape cells.

    As testing continued I got tired of entering the same "programs" over and over so I added the ability to Load and Save "workspaces".  A workspace contains a snapshot of the tape and state transition table values at the point that Save is invoked.  Save will also produce a dump of the same information plus counts of how many of each symbol were found on the tape. Load of course changes the current console values of the tape and state transition table to those in the saved file.  

    Here is a quick demo of TMD-2 loading and running a 3-state / 2-symbol busy beaver. The console is running in Demo mode where steps are executed every 300 ms or so:

    After the busy beaver program was finished running I saved the workspace to a different file and produced the following summary:

    Showing tape from cell -2 to cell 3.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    | 1 | 1 | 1 | 1 | 1 | 1 |
    
    Counts
    ~~~~~~
    0: 0
    1: 6
    2: 0
    3: 0
    4: 0
    5: 0
    b: 0
    
    State Transition Table
    ~~~~~~~~~~~~~~~~~~~~~~
                A
    | 0 | 1 | 2 | 3 | 4 | 5 |
    | 1 | 1 | - | - | - | - |
    | R | L | - | - | - | - |
    | B | C | - | - | - | - |
    
                B
    | 0 | 1 | 2 | 3 | 4 | 5 |
    | 1 | 1 | - | - | - | - |
    | L | R | - | - | - | - |
    | A | B | - | - | - | - |
    
                C
    | 0 | 1 | 2 | 3 | 4 | 5 |
    | 1 | 1 | - | - | - | - |
    | L | L | - | - | - | - |
    | B | H | - | - | - | - |
    
                D
    | 0 | 1 | 2 | 3 | 4 | 5 |
    | - | - | - | - | - | - |
    | - | - | - | - | - | - |
    | - | - | - | - | - | - |
    
                E
    | 0 | 1 | 2 | 3 | 4 | 5 |
    | - | - | - | - | - | - |
    | - | - | - | - | - | - |
    | - | - | - | - | - | - |
    
                F
    | 0 | 1 | 2 | 3 | 4 | 5 |
    | - | - | - | - | - | - |
    | - | - | - | - | - | - |
    | - | - | - | - | - | - |
    
    

    I was able to reproduce most of the runtime features from TMD-1, like highlighting each step within the state transition table while executing the program in Demo and Step modes.  I feel that TMD-2 thus maintains the "simple to program and easy to understand' characteristics of it's predecessor. 

    At some point after adding load and save workspaces, plus the ability to input values directly into the state transition table cells through the console, I realized that I had a pretty good stand alone Turing machine application here. While I personally enjoy the tactile nature of placing physical tiles onto the TMD-1 and 2 transition table panels,  clicking on the screen's virtual cells, while not as satisfying, works pretty well.  This also makes my "simple to program easy to understand" Turing machine concept available to a much wider audience.

    So I'm going to take a few days to do some more testing and to figure out how best to package up "TMD-2 The Program", then I will post a link in this blog with the result.  Once that's done I'll move on to the final task of integrating the OCR input unit because I really do like working with the tiles.

  • User Interface Progress

    Michael Gardi10/16/2020 at 19:45 0 comments

    I haven't posted in a while because I have been learning the ins and outs of Python. Having never used it in my professional career (I was mostly a Java guy) I have to say I'm really liking the language. 

    So I hit a couple of milestones today. First of all I finished my first cut at the user interface for TMD-2.

    Now when I say finished, what I really mean is that the layout is done (for now), the tape can be scrolled and the cells changed manually, the other buttons react to mouse clicks or touches but are not currently "live". Certainly I still have quite a bit of work to do before the whole system is end-to-end complete, but so far so good.

    I'm doing all of the UI development on my Windows laptop under Eclipse (because I'm familiar with it) and PyDev.  At the recommendation of a fellow makerspace buddy I'm using the PyGame framework.  I'm really liking this environment as well. The double buffering makes for very smooth screen transitions. 

    So this leads me to my second milestone. I probably should have tried this a lot sooner, but today I copied the python script and images from my laptop to the target environment, a Raspberry Pi with the official 7" LCD touch display, and as can be seen in the image above it worked! First try! I have used other pieces of software that claim to be "cross platform", but you end up having to make small (sometimes large) tweaks to get your program working in each new environment.  Not this time.  I'm very impressed. 

    My next step is to get the finite state machine running and fully working with the UI, then I'll tackle integrating the camera piece that I already have working as a separate project.

  • TMD-2 Hardware

    Michael Gardi09/28/2020 at 03:20 0 comments

    My Raspberry Pi 4, camera, and 7" display arrived so I though I would get the hardware part of the build sorted. I designed and printed a stand for the Pi 4 and display.

    I like the way that the the two components integrate, and don't believe in hiding anything, so it's open concept much like my Working Digital Computer design. 

    Next I built a base to hold the State "cards" and a legend with labels for each row.

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

    I found an articulated arm design by Chris Rogers (hackoholic) on Thingiverse.  His motion capture rig is very similar to the base that I built so it's a good fit. The Raspberry Pi camera snaps snugly into the camera mount and the ribbon cable slides easily through the guides. Great design!

    Finally I put the State Transition Table base camera together with the Pi and display. For development purposes only I have added a wireless keyboard and mouse.

    So that's basically the TMD-2 hardware done. It's mostly a software project from here on in.

  • Testing the OCR With Some Real Tiles

    Michael Gardi09/23/2020 at 17:26 0 comments

    For my last bit of OCR testing I wanted to use a photo of some real printed tiles on a printed base. So I created a single state "card" with rectangular indentations for tiles.

    Since I will be combining six of these I wanted to scale things down as much as possible and still be useable.  You can see the A tiles above for comparison, the larger being from TMD-1.  The smaller tiles still feel pretty good and are easy to pick and place. Notice that the empty spots above have a square dot as a "place holder".

    The Pi camera was not in yet so I just used my phone to take this shot.

    The process is almost as before. One change is that I now identify where the black borders are around and between the "cells" and use a "flood fill" algorithm with white to eliminate them.  Here is the resulting binary image:

    Use dilation to eliminate the noise:

    Edge detect the objects:

    Then use contours to identify where the objects are:

    And the happy result after using Tesseract on each of the table cells:

    Since the size seems good I will print five more of these "cards" for states B, C, D, E, and F. I'll also make a legend down the side with each row's actions: Read, Write, Move, and Goto and combine them all on a base of some sort. I'll also have to figure out a way to mount the Pi camera above this base. 

  • Project Status Changed

    Michael Gardi09/23/2020 at 14:29 0 comments

    I have done enough research to convince myself that I will be able to OCR the State Transition Table and reliably determine what tiles have been placed there. As a result I have decided to go ahead and build a 6-state / 6-symbol Turing machine. I have change the status from Research to an Ongoing project to reflect this.

  • More OCR Research

    Michael Gardi09/13/2020 at 20:30 0 comments

    I created a new image that that I feel is more representative of what my 6-state / 6 symbol State Transition Table will look like:

    I revisited my idea of having a registration mark for each "Tile" when I realized that I could better identify the tile bounding boxes with contours alone.  So here is what the binary image for the above looks like:

    Now in order for this to work I needed to add a "dot" as a placeholder for  the empty cells. I'm thinking these will be part of the "mat" that the tiles when placed will cover.  The edge image:

    So now when I use findContours I end up with the following bounding boxes around the tiles:

    When I pass these sub images to Tesseract, based on the binary image above, I get the following result:

    So the first image above will be printed to scale (when I can get to the color printer at kwartzlab), imaged with the Raspberry Pi camera, and I'll try this process with the photo. I expect that I will have to do considerably more working cleaning up the photo. We'll see.

View all 14 project logs

Enjoy this project?

Share

Discussions

Richard Geerligs wrote 10/27/2020 at 11:57 point

Thanks

  Are you sure? yes | no

Tom Nardi wrote 10/01/2020 at 00:19 point

Your designs always have such an elegant simplicity, this one makes me think of some kind of Apple product from an alternate timeline. OCR was an absolutely brilliant way to affordably scale up the tile interface.

  Are you sure? yes | no

Michael Gardi wrote 10/01/2020 at 12:14 point

Thanks for the kind words Tom, and your interest in my Turing projects.

  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