Page 141 -

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

The LEGO Turning Machine • Masterpiece 3 113

It’s very interesting to understand how the state transitions table (the program) works,
and examine the machine’s behavior step-by-step. Do you think that you’ll be able to
modify the table to let the machine return back to its original cell after adding the two
numbers? I can assure you, it’s not difficult.A quick tip: you actually have to change State
2 and add another state to let the machine go left until it finds a blank.
As you can see, now that we’ve gone a bit more in depth, this device is really more
like a computer program (a sort of software) rather than a computer (hardware), its key
part being the programming algorithm defined in the action table.

Inventing…
The UTM: Universal Turing Machine

In his works, Turing described a new, powerful concept applied to his machine. If
an algorithm of a particular procedure can be coded with standard instruction
(that can be read by a Turing Machine), then the work of interpreting the instruc-
tions itself is a mechanical process, and can be run by a particular Turing machine
called the Universal Turing Machine (UTM). This is basically the concept of a
modern computer: one machine that can be used for many different tasks, if pro-
grammed with the appropriate algorithm. The UTM, like modern computers, uses
the idea of storing instructions in the same way in which data and numbers are
stored. That was a revolutionary concept in 1936, many years before the first
practical application of a digital computer.

The Differences between our LEGO Turing
Machine and an Authentic Turing Machine

Building a real machine like the one that Alan Turing theoretically conceived is impos-
sible, even without the limits of the Lego MINDSTORMS system. In March 2002,
Aatish Bhatia published some pictures of his “LEGO Pseudo-Turing Machine” on the
Web (www.generation5.org/aisolutions/ab_legoturing.shtml).This was the first attempt
to build such a device with LEGO, although it remains an interesting experiment, it
lacked a fundamental functionality that defines a Turing Machine: the possibility to write
on tape. In that moment, I thought that it would be great if someone could push the
experiment a bit further. I did some tests, and after many trials and errors, I triumphed! I
built a limited but working device that has all the characteristics to be considered a true
LEGO Turing Machine.
The first problem you encounter (and a large problem at that) is that the tape should
be infinite. However, in actuality the tape does not need to be infinite, just indefinite,
meaning that you build a finite device that can always be expanded for your needs.
LEGO is the perfect tool to achieve this. It has the wonderful feature of being modular