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.

## No comments:

## Post a Comment