Page 136 -

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

108 Masterpiece 3 • The LEGO Turning Machine

and to understand the particular time period in which it was invented. Later, we will
examine the machine’s original architecture and the way its creator, the English mathe-
matician Alan Turing, designed it to study computational problems.
In 1931, an Austrian mathematician named Kurt Godel demonstrated the revolu-
tionary theory of the incompleteness of mathematics.This theory truly changed the sci-
ence of mathematics. Mathematicians usually write theories (proposals for what might be)
and then try to prove that the theories are correct using previously proven theories.The
attempt to write theories down and prove that they are correct is considered a formal
process. In extreme synthesis, Godel showed that with every formalization of arithmetics,
there are truths that cannot be proved within the same formal system; that is, there is
always something that can not be proved right or wrong within the rules of its system.
But at that time, a big question remained unanswered: could there exist, at least in theory,
a defined process or method to decide whether a mathematical proposition was provable?
At the beginning of the century, the Prussian mathematician David Hilbert included this
question in a list of 23 mathematical problems that were still undecided, and challenged
mathematicians to try and solve them.
Alan Mathison Turing (1912-1954) is considered one of the most important scientists
of the twentieth century, and a pioneer, if not the founder, of what we call AI today.
Turing was a mathematician who spent a large part of his life studying a wide variety of
disciplines including logic, probability, arithmetic, biology, and cryptography.Turing fol-
lowed a very innovative approach to the problem on Hilbert’s list, working not inside, but
outside the formal system.Turing provided a new definition of “method” by analyzing
what a person can do mechanically, and expressing this analysis on a theoretical machine
that could perform basic operations.Turing’s machine used a simple paper tape to store
data and uses the concept of state changes, like that of a human being who changes their
state of mind during an evolving mental process.
The Turing approach to the problem was really very innovative and revolutionary. He
laid the foundation of the modern theory of computation and computability. He proved
that determining the decidability of mathematical propositions is equivalent to asking,
“What sorts of sequences of a finite number of symbols can be recognized by an abstract
device?” Having defined the new concept of definite method, that which we now call
algorithm, he could also try to answer Hilbert’s question: does a defined process or
method exist to determine whether a mathematical proposition is provable.A system that
is able to perform the same operations as the Turing Machine is called Turing complete. It’s
interesting to see that there is no hierarchy of power in this computational system. If a
system is Turing complete, in fact, it can do anything definable in terms of an algorithm.
It’s funny to think that a simple single-taped Turing Machine is as powerful as the expen-
sive state-of-the-art computer that you just bought… and even more powerful if you
think that, theoretically having an infinite tape, can handle infinite numbers!