Math Mutation 46: The World's Simplest Computer
Just last month, a new theorem was proven that defines, in a
theoretical sense, the simplest possible computer. Now this isn't an
engineering question-- this was a proof from the domain of automata
theory, part of theoretical computer science. Surprisingly, the
author is a 20-year old undergraduate student at the University of
Birmingham, in the UK, named Alex Smith, who created his proof in
response to a prize competition by the Wolfram Institute. Actually,
he was initially trying to disprove the theorem, thinking that this
automaton was way too simple to truly be a universal computer, but
ended up accidentally proving it instead!
So what is this simplest computer? Here's how it works. You have
an infinitely long input/output tape, divided into squares. Each
square can be one of three colors, let's say red, green, and blue.
There is also a reader which, at any given moment, points to one of
the squares, and contains a light bulb which can be on or off. The
entire operation of this computer consists of a table of six rules:
for each possible color of the current square and current state of the
light bulb, the rules describe whether the machine changes the color
of the current square, turns the light bulb on or off, and moves to
the left or the right. For example, the first rule is that if the
current square is red, and the bulb is on, change the square to green,
turn off the bulb, and move the reader to the right. I won't bore you
with a detailed retelling of the rules, but you can find them at the
references in the show notes. According to Smith's proof, by properly
coloring the input tape and choosing the starting light bulb state,
this is enough to emulate the functioning of any possible computing
device.
So we know it's universal. But why do we say this is the simplest
possible computer? Well, it's part of a general class of devices
known as Turing Machines, which are similar in design but can contain
an arbitrary number of colors in each square, and an arbitrary amount
of memory in the reader device rather than just a 2-state light
bulb. Turing Machines are generally used as the definition of
computation, and it is known that they are computationally universal.
But there is a limit to how simple a Turing Machine can be and remain
universal: it is known that one with just two colors on the tape and
just two reader states is NOT universal. So Smith's theorem, since it
augments a known non-universal machine with just one more tape color
and makes it universal, must be describing the simplest possible
universal Turing Machine.
Of course, the next question is: what does this mean? Well, as I
mentioned, it's really a result of theoretical interest. While the
Turing Machine described can emulate any computer in existence, it
can't do it especially efficiently, and thus is not of practical use
in designing real computers. In other words, it's not going to result
in extra gigahertz of CPU speed on your desk-- sorry about that. The
contest to prove it was created by the somewhat controversial Stephen
Wolfram, who I mentioned in an earlier podcast, and who believes
simple models of computation like this will result in revolutionary
advances in biology, chemistry, and physics, which we have not quite
seen yet. Wolfram does point out the intriguing possibility that such
simple models of computation might turn out to be a key enabler one
day for useful biology-based computers-- after all, our DNA is based
on simple encodings using four types of molecules, so the idea might
not be that farfetched.
But regardless of whether you think Wolfram will ultimately
win a Nobel Prize or end up in the loony bin, I think the fact that
such a simple model is capable of universal computation does say
something profound about the nature of computing. I would like to
congratulate Alex Smith on his achievement.
And this has been your math mutation for today.
References:
Press
Release
Wolfram
Institute page on the new theorem
Turing
Machines at Wikipedia