Turing Machine Demonstrator Mark 3 (TMD-3)

Manufactured By: Michael Gardi

Designed By: Michael Gardi

Release Date: 2023

It's been about three years since I built my existing Turing Machine Demonstrators. The goal for TMD-1 was to build a machine that was simple to program and easy to understand. TMD-2 was designed to increase the capabilities of the first version while maintaining it's simplicity. Both versions were designed to demonstrate the idea of a Turing machine with as much clarity as possible.

TMD-3 is a refinement of the existing machines with a new approach to implementing the "tile interface".

TMD-1 was the first time that I had ever used a hall effect sensor, so maybe I can be forgiven for missing the fact that there are actually two types. The SS451As sensors that I used for TMD-1 are just digital switches, ON in the presence of a magnetic field and OFF when no magnetic field is in proximity.  The other type of hall effect sensor, that I just recently became aware of, measures the strength of a magnetic field, not just the presence. These parts are analog based, and a good example is the SS49E Linear Hall Effect Sensor. Game changer! It occurred to me that by somehow varying the strength of a magnetic field within a tile I could determine the difference between many tile values with just a single sensor.

I create a PCB to hold the 16 SS49E sensors required for a single state. In addition each state board has a 16-channel CD4067BE Analog Multiplexer to manage the 16 sensors. Since the Raspberry Pi I’m using to control the demonstrator does not have native ADC support, the state board PCB will also have an 8-channel 10-bit MCP3008 A/D converter chip defined. Only one of the state boards will actually be populated with the chip. Six of these PCBs were populated with sensors then wired together to form the state table for TMD-3.

To read the entire state transition table containing 96 SS49E sensors, the Raspberry Pi requires only 8 GPIO lines. Four of these will be mapped to the channel select lines for the CD4067BE multiplexers. An additional four lines are required to control the MCP3008 A/D converter chip via its SPI interface to read the sensor values.

The software iterates through the multiplexers’ 16 channels. For each channel it will read in turn the sensor values of the 6 multiplexer outputs.

TMD-3 has the following characteristics:

• One tape with 100,000 cells and a single head.

• The alphabet used will have five symbols: {0, 1, 2, 3, 4/b}. 0 will be the blank symbol and b is an endmarker symbol that can be read from the tape but not written.

• There will be six states: {A, B, C, D, E, F}. A will be the start state plus there is a special HALT state H.

If you are interested in more details about Turing machines in general the Wikipedia entry is very good. I have also written a small booklet, TMD-3 Quick Start Guide. It describes the operation of TMD-3 and helps the user run their first "program".