Page 176 -

243_masterpieces_03.qxd 4/18/03 7:02 PM Page 148

148 Masterpiece 3 • The LEGO Turning Machine

Table 3.4 A Transitions Table for Solving “N div 2”

Input Output

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

State 0 is used to erase the first symbol on the tape, while State 1 erases the second
symbol, if present. If the sequence contains only one symbol, the machine stops in this
state on the empty cell. State 2 moves the head right until it finds an empty cell, which
marks the end of the input sequence. State 3 writes a new symbol on the right side, and
State 4 returns to the left passing the output sequence. State 5 checks for any other left
symbols remained, and sets the machine to start again from State 0, or stop.
In Table 3.5, we see an example of the steps required to solve the problem for a
sequence of four symbols.

Expanding the System

Once you have performed a few experiments with your LEGO Turing Machine, you
may want to go even further: expand its possibilities or modify the structure according to
your preferences. Many improvements can be made to the model.
First, we’ve just built a tape that is capable of handling two symbols at a time:A cell
can be empty or full.To allow the solution of more complex problems, like the very
complex task of multiplying two numbers, the possibility of having more symbols can be
very useful. In this case, a different solution must be found, like having pieces of different
colors read by a light sensor (three colors are easily read by the sensor, but more often
result in wrong recognitions).You can also stick to using a mechanical switch, with three
or four possible positions, but using two light or touch sensors.