Page 175 -

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

The LEGO Turning Machine • Masterpiece 3 147

1. Load the program into the RCX.
2. “Write” two numbers by hand on the tape, separated by an empty cell.
3. Place the head on the first symbol on the left.

4. Start the program by pressing the Run button. Remember not to move the tape
if the motor is in the “Off” state.
See if everything’s working or if it needs some debugging.The machine should go
through the all steps shown in Table 3.2, and at the end, the tape should look like Figure
3.4, showing the result of the addition.

A More Complex Behavior

What we’ve seen so far is how to program our LEGO Turing machine to perform quite
a simple task: adding two numbers. It’s time now to see how to write a more complex
program.
Let’s consider the problem of making a Turing machine that, given an initial sequence
of N symbols that represent an integer as already seen in the previous example, leaves the
tape with the result of the operation “N div 2.” Div is the operator that stands for an
integer division (Table 3.3 shows some examples of inputs and outputs).

Table 3.3 Input and Outputs for the “N div 2” Example

Sequence Result

oo o
ooo o
oooo oo
ooooo oo

There is more than one way to program a Turing machine, and you can always
approach the problem from different points of view. In this case, I’ve chosen this strategy:

1. Start scanning the sequence, from left to right.
2. If the sequence contains a single symbol (o), the head erases it and stops.

3. If at least two symbols are present, both are erased and a new symbol is written
on the right.
4. Return to the leftmost symbol and start again from Step 1.

Let’s try and write a state transition table for the task just described.As you can see in
Table 3.4, the programming is far more complex than the first example we discussed at
the beginning of the chapter. Even simple problems on the Turing machine often require
a solution that’s not so simple and intuitive at all.