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
A	$ANY	$NOCHANGE	$NOCHANGE	$HALT

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.

Clearly, [Mike’s] machine is practically art. If you are less ambitious but very patient, you can try your hand at building one from Lego bricks.

Universal

You can construct lots of things with the right tape and table, and reasoning about them mathematically is easier than trying to reason about a full-blown computer — indeed that’s the point of the thought experiment. Here’s the kicker: it is possible to construct a universal Turing machine. That is, a machine that reads an arbitrary Turing machine description from a tape and simulates it. You can argue that such a machine forms the basis for the modern stored-program computer.

Your Turn

If you want to experiment with a Turing machine, you don’t have to resort to Lego bricks or a major hardware build. You can find simulators online. In addition, I put together some Excel spreadsheets that implement a Turing Machine that you can find on GitHub. Just be sure to enable macros after you load the spreadhsheet. You can see one of the spreadsheets below.

The top row lets you set the current state and the tape position (the highlighted block on the tape). You can also use the control buttons (there are two reset buttons to the right that you can’t see in the picture). You can edit the tape, of course, and the state table is at the bottom. You can use the Step button to run one cycle or the Execute button to run continuously. Be sure to save because if you press Execute and get caught in an endless loop, it is hard to stop (Control+Break should do it, but doesn’t always).

We recently looked at a pretty snazzy Turing build. You can see a video of that machine in action below.

Filed under: Curated, Featured, History, Original Art