Page 142 -

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

114 Masterpiece 3 • The LEGO Turning Machine

and easily modifiable, so you can always enlarge the tape for your needs. For most pro-
grams that you will be creating, a small tape is enough, so that you don’t need to have
thousands of pieces to build this model.
The second problem is that although the number of symbols a Turing Machine uses is
finite, but can be high.This is hard to build with LEGO pieces, so you have to consider
the constraints. We need to be able to create a mechanical device that can be set into dis-
crete states, and the states need to be uniquely readable by the LEGO device. It’s hard to
build a tape that can handle more than two or three symbols, and in this chapter we
describe a machine that has two possible symbols to keep things simple.This is not a real
problem, as even if you had a tape whose cells could remember hundreds of states, you
the human would be hard-pressed to write a program (state transition table) that would
ever utilize all the states. So, the two symbols (empty and full) are enough to build and
program many different tasks.

Building the LEGO Turing Machine

It’s time to begin the construction of the LEGO Turing Machine. We’ll build a device
that is as similar as possible to the original concept of the Turing machine.The scheme
will be a modular design: that is, splitting the project into sub-assemblies, each with a spe-
cific task.This approach is very useful as it allows you to separate the problem into
smaller ones, giving you the possibility to concentrate on a single task at a time. We will
start by creating a large support for the machine, and then we will build the tape, a
motor-driven direction control, and the “head” of the machine.The head is the most
important part, as it will read and write on the tape.

The Base

The Base sub-assembly serves as a container and connecting structure for the other parts
of the model. On this base, we have to build a support for the Tape sub-assembly (built
next) that should be free to move to the right or left without any constraints.The key
point is that you have to build a solid mounting, especially if you think that the Tape