TMD-2: Turing Machine Demonstrator Mark 2

I've kicked off a new Turing Machine Project: TMD-3.

In the February issue of MagPi magazine (102) there is a nice two page spread about TMD-2. You can download a free PDF version here.

As one last finishing touch I added a virtual keyboard to the TMD-2 application with thanks to Anthony Maro and William B Phelps for their PyGame virtualKeyboard module.

This mitigates the need for a keyboard and mouse if you are using a touch screen like the 7" Raspberry Pi panel that I am using. The github references in this project writeup have been updated to the new release.

Designing and building TMD-2 was a great  "stretch" experience for me. For the hardware, I had never worked extensively with the Raspberry Pi or Pi Camera. On the software side I had never used  Python or PyGame before. So I learned a lot  putting TMD-2 together.

Python is a great language but it took a little getting used to. I come from a mostly Java background so giving up on { } as block delimiters felt pretty unnatural. Even after a few months with Python, I still find myself wanting to put a ; at the end of lines. And I never did get the hang of using the _ in variable names, and stuck with camelCase. But that's just me. Python certainly lives up to it's cross-platform name. Development of the console application shifted smoothly between my Windows/Liclipse development environment and my Raspbian target environment. When I started integrating the camera and switched to the Pi for all my development, I found I was easily able to use RealVNC from my laptop to develop on the Pi, which gave me more screen real estate since the only display I had on the Pi was the a 7" touch-screen.

PyGame was recommended to me, and I'm glad that I chose it as the framework for the console. The only thing that I missed was some sort of GUI module. I tried integrating a number of the recommended external libraries, but in the end created my own dialogs in PyGame itself.  The disadvantage of doing this is that my implementations were a little feature light, but on the other hand maintained the aesthetic of the application.

There was more software development in this project than I thought there would be. When I first started, I was thinking of TMD-2 as the hardware successor to TMD-1.  I would build the hardware and write a little program for the console. Somewhere in the middle writing the console I realized that what I was doing would make a pretty good stand-alone application. I added features so that the program could be run without the camera based input, primarily allowing the state table to be edited with mouse clicks. And since Python is cross platform, it would run almost anywhere. In the end I was thinking of TMD-2 to as a Turing machine program, that took the ease of use and simple to program concepts from TMD-1, and made them accessible to a much wider audience.  TMD-2 also supports a cool optional tile based interface for defining the state transition table.

I think with the completion of TMD-2 that I have Turing machines out of my system for a while.  On to the next project whatever that might be.

To keep things neat I printed a parts box to hold all the tiles.

Since I no longer needed the small black squares in the empty tiles as registration marks, I redid the State Transition Table without them. I think it looks a lot cleaner.

Finally, I created a V1.0 "release" of the console software on github.

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.  

• A Universal Turing Machine - Where Mark corrects a few problems with the UTM presented in the book.
• Implementation Details for Hopcroft & Ullman's Universal Turing Machine -  Good example of encoding a state machine as input.
• Correct State Table for Hopcroft & Ullman's Universal Turing Machine - Definition for a 40-state / 12-symbol UTM.

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. 

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.

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.

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.

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.