Page 138 -

243_masterpieces_03.qxd 4/18/03 7:01 PM Page 110

110 Masterpiece 3 • The LEGO Turning Machine

The device itself is always in one of a finite number of states.These states determine
what action the machine should perform via a special programming feature called a state
transition table (or action table).The state transition table tells the Turing Machine what to
do when it is in a certain state and encounters a specific symbol, similar to how your state
of mind tells you what to do in a certain situation to respond to specific external events.
The machine can perform four actions:

■ Go left one cell
■ Go right one cell

■ Write a symbol
■ Erase a symbol

In synthesis, you can think of the Turing Machine as a “black box” that is capable of
reading, writing, and erasing symbols on a long tape divided into cells. Note that while
the tape has to be infinite, the states and the symbol are finite.As you can easily see there
are no places other than the tape to store data, so for the most complex operations (like
multiplying two numbers) you need to put placeholders on the tape in addition to the
numbers themselves. In fact, you have to hold information about what is happening, what
is going to happen, and temporary data.Thus, for even very simple operations, the states
quickly grow to a large number.

NOTE

For more information on the architecture of the Turing Machine and its varia-
tions, please refer to the following Web sites:

■ www.unidex.com/turing/tm_intro.htm
■ www.personal.kent.edu/~brosmait/computability/architecture.html
■ www.webpearls.com/products/demos/pap/comap/chapter5/sec6/
node2.html
■ www.netaxs.com/people/nerp/automata/turing0.html

The State Transition Table

By convention, the machine starts in its first state at the first cell furthest to the left con-
taining a symbol. Then it scans the tape by moving to the right or left, and handles the
data by reading, writing, and erasing symbols.The table tells the machine the equivalent
of:“if you are in a certain state and see a certain symbol, do a specific action, move one
cell and change state.” Let’s see this process in a sequence.
1. The machine reads the contents of a cell, that is, the symbol written on the tape.
2. The machine uses the state transition table to map the current input
(state+symbol) to an output (various actions).