Page 140 -

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

112 Masterpiece 3 • The LEGO Turning Machine

The machine should start at the first symbol on the left, add the two integers, and
stop after showing the required answer.Table 3.1 shows how a state transition table could
be done.

Table 3.1 A Transitions Table for Adding Two Integers

Input Output

State Read Symbol Operation Move Direction Next State
0 o Right
0 <Empty> Write: o Right 1
1 o Right
1 <Empty> Left 2
2 o Erase Stop

This way we have created a machine that is capable of adding any two integers, no
matter what their size (provided that you have an infinite long tape). Input is determined
by the combination of the current state (indicated as a number) and symbol. In this case,
only two “symbols” are used: a cell can be empty or full. Note that when a cell of the
table is empty it means that there is no action to take, meaning that a symbol is not re-
written if already there. In the same way, if the next state is not specified, it means that
there’s no need to change it, and the machine simply stays in the current one. It is very
interesting to see how the entire process works, by examining the tape in each step (see
Table 3.2). I’ve indicated the current position of the machine’s head with a gray cell.

Table 3.2 Steps for Adding Two Integers
State Tape

0
0
0

0
1
1

1
1
1

2
Stop