A Turing Machine
Project submitted to Parallax by Mike Davey
In Alan Turing’s 1937 paper on computable numbers, he presented a thought experiment. Turing describes a machine that has an infinitely long tape upon which it writes, reads and alters symbols. He further shows that a machine with the correct minimal set of operation can calculate anything that is computable, no matter the complexity. This thought experiment is the underpinning of today’s digital computers. My goal in building this project was to create a machine that embodied the classic look and feel of the machine presented in Turing’s paper.
A single Propeller chip is the sole controller of my machine. It handles the user interface, reads transition tables from an SD card, controls the read-write head, reports on the current machine status, and handles the supply and take-up roll stands for the tape.
The heart of the turing machine is the read-write head. The read-write head transports the tape and positions cells of the tape appropriately. It can read a cell determining what, if any, symbol is written there. The machine works on, and knows about, only one cell at a time. The tape in my machine is a 1000’ roll of white 35mm film leader. The characters, ones and zeros, are written by the machine with a black dry erase marker. The tape is transported through the machine with a stepper motor. This transport motion is also used to write in the X axis. To move the marker in the Y axis a digital servo is used. A second servo raises and lowers the marker as needed during writing.
The reading of the tape is done with a TSL-1401 line scanner camera. Because there are only three possible characters to read, the recognition system can be very simple. To read the tape the line scanner only needs to capture an image 1/8” wide at the center of the cell, where the vertical line of the “1” would be, and at one edge, where a vertical line of the “0” would be. Based on these two small areas the Propeller chip can recognize if the cell contains a one, a zero or is blank. After a cell is read the transition rules are then used to: alter that cell if needed, move on to a cell to the left or right of the current one, and select which transition state is to be used next.
Erasing a cell is done with a small felt covered cylinder rotated by a DC motor. The cell is moved under the eraser, the eraser cylinder is lowered with a servo and the tape is moved back and forth under the eraser as it rotates. Each area of the tape can be written to and erased from hundreds of times.
The display and user interface for the machine consists of a 4x20-character serial LCD display, three 4- character 7-segment LED displays and three status LEDs. Human input to the machine is through a 5- position switch. Transition rules are written as text files on a computer and saved on an SD card. The SD card is inserted into the Turing machine and program files are selected from the card’s directory.
As the machine works, excess tape is played out or reeled in by two roll stands on either side of the read-write head. Two of the Propeller’s cogs are used to read IR range sensors and control the gearhead motors that keep the tape neat.
While a classic Turing machine may seem to have no practical purpose, nothing holds people’s interest like a visual moving machine. And if that machine is doing calculations it makes it easier to explain how today’s computers use very simple steps to perform very complicated operations.
Contact Mike Davey
Downloads & Resources:
A Turing Machine Website (Off Site)
Full Report - Turing (.pdf)
Source Files (.zip)