The Turing Tapes

The recent movie “The Imitation Game” gave [Alan Turing] some well-deserved fame among non-computer types (although the historical accuracy of that movie is poor, at best; there have been several comparisons between the movie and reality). However, for people in the computer industry, Turing was famous for more than just helping to crack Enigma. His theoretical work on computing led to the Turing machine, which is still an important concept for reasoning about computers in a mathematical way. He also laid the foundation for the stored program computer that we take for granted today.

What’s a Turing Machine?

A Turing machine is deceptively simple and, like many mathematical models, highly impractical. Leading off the inpracticalities, the machine includes an infinite paper tape. There is a head that can read and write any symbol to the tape at some position, and the tape can move to the left or the right. Keep in mind that the head can write a symbol over another symbol, so that’s another practical difficulty, although not an insurmountable one. The other issue is that the symbol can be anything: a letter, a number, a jolly wrencher, or a bunch of dots. Again, not impossible, but difficult to do with practical hardware implementations.

Put that aside for a minute, though. The machine also has a current state and a finite table of actions that will dictate the operation of the machine. Each row in the table contains a current state and a current symbol. A row that matches the current state and current symbol will direct the action of the machine. The rest of the row contains a symbol to print on the tape (which could be the same as the current symbol), if the tape should move left or right by one step, and a new state (which could, of course, be the same as the current state).

You might wonder how this constitutes a practical computer. Well, practical might be a bit much, but you can do arbitrary tasks, although sometimes it takes a lot to do even simple tasks. For example, here’s a really simple machine that prints 001 on the tape:

Current State Current Symbol Next Symbol Move Next State
A $ANY 0 Right B
B $ANY 0 Right C
C $ANY 1 Right $HALT

The machine starts in state A and ends at state $HALT. The $ANY keyword matches any symbol. Here’s a more interesting example that inverts a binary number:

Current State Current Symbol Next Symbol Move Next State
A 0 1 Right A
A 1 0 Right A

In this case, there is only one state. Any 0 becomes a 1 and any 1 becomes a 0. The first symbol that isn’t either a 0 or a 1 stops the operation.

In the Wild

Even though you can’t build a real machine with an infinite tape and all the other impracticalities of a true Turing Machine, it doesn’t stop people like [Mike Davey] from building practical ones that are good enough. You can see a video of this machine below.