(Statement written by Scott Aaronson)
It’s been understood for decades that, if you take a simple discrete
rule—say, a cellular automaton like Conway’s Game of Life—and iterate
it, you can very easily get the capacity for universal computation.
In other words, your cellular automaton becomes able to implement any
desired sequence of AND, OR, and NOT gates, store and retrieve bits in
a memory, and even (in principle) run Windows or Linux, albeit
probably very slowly, using a complicated contraption of thousands or
millions of cells to represent each bit of the desired computation.
But suppose we want more than mere computational universality.
Suppose we want “physical” universality: that is, the ability to
implement any transformation whatsoever on any finite region of the
cellular automaton’s state, by suitably initializing the complement of
that region. So for example, suppose that, given some 1000×1000
square of cells, we’d like to replace every “0” cell within that
square by a “1” cell, and vice versa. Then physical universality
would mean that we could do that, eventually, by some “machine” we
could build outside the 1000×1000 square.
You might wonder: are we really asking for more here than just
ordinary computational universality? We are. To see this, consider
Conway’s famous Game of Life. Even though Life has been proved to be
computationally universal, it’s not physically universal in the above
sense. The reason is simply that Life’s evolution rule is not
time-reversible. So if, for example, there were a lone “1” cell deep
inside the 1000×1000 square, surrounded by a sea of “0” cells, then
that “1” cell would immediately disappear without a trace, and no
amount of machinery outside the square could detect that it was ever
there.
Furthermore, even cellular automata that are both time-reversible and
computationally universal could fail to be physically universal.
Suppose, for example, that our CA allowed for the construction of
“impenetrable walls,” through which no signal could pass. And suppose
that our 1000×1000 region contained a hollow box built out of these
impenetrable walls. Then no amount of machinery that we built outside
the region could ever detect whether there was a particle bouncing
around inside the box.
So we face a genuinely new question: does there exist a physically
universal cellular automaton, or not?
This question was first asked in a lovely 2010 preprint by Dominik Janzing.
In his ITCS'2015 Best Student Paper, MIT graduate student Luke
Schaeffer answers Janzing’s question in the affirmative, by
constructing the first cellular automaton that’s been proved to be
physically universal.
Very briefly, Luke first defines a reversible, two-dimensional CA
involving particles that move diagonally across a square lattice, in
one of four possible directions (northeast, northwest, southeast, or
southwest). The number of particles is always conserved. The only
interesting behavior occurs when three of the particles “collide” in a
single 2×2 square, and Luke gives rules (symmetric under rotations and
reflections) that specify what happens then.
Given these rules, it’s possible to prove that any configuration
whatsoever of finitely many particles will “diffuse,” after not too
many time steps, into four unchanging clouds of particles, which
thereafter simply move away from each other in the four diagonal
directions for all eternity. This has the interesting consequence
that Luke’s CA, when initialized with finitely many particles, can't
be capable of universal computation in Turing’s sense.
On the other hand, using finitely many particles, one can also prove
that the CA can perform universal computation in the Boolean circuit
sense. In other words, we can implement AND, OR, and NOT gates, and
by chaining them together, can compute any Boolean function that we
like on any fixed number of input bits. And this “circuit
universality,” rather than Turing-machine universality, is all that’s
implied anyway by physical universality in Janzing’s sense.
While the “diffusion into four clouds” aspect of Luke’s CA might seem
annoying, it turns out to be useful for proving physical universality.
For it has the consequence that, no matter what the initial state was
inside the square we cared about, that state will before too long be
encoded into the states of four clouds headed away from the square.
So then, “all” we need to do is engineer some additional clouds of
particles, initially outside the square, that:
- intercept the four escaping clouds,
- “decode” the contents of those clouds into a sequence of bits,
- apply an arbitrary Boolean circuit to that bit sequence, and then
convert the output bits of the Boolean circuit into new clouds of
particles converging back onto the square.
So that's what Luke did. Just in case there’s any doubt about the
correctness of the end result, Luke actually implemented his
construction in the cellular-automaton simulator Golly, where you can
try it yourself.
But who cares that we now know that there exists a
physically-universal CA? Well, perhaps we'd like to make finer
distinctions, among various “candidate laws of physics,” than simply
saying that some laws are computationally universal and others aren’t.
For ironically, the very pervasiveness of computational universality
makes it of limited usefulness in distinguishing physical laws: almost
any sufficiently-interesting set of laws will turn out to be
computationally universal.
On the other hand, many of these laws will be computationally
universal only because of extremely convoluted constructions, which
fall apart if even the tiniest error is introduced. In other cases,
we’ll be able to build a universal computer, all right, but that
computer will be relatively impotent to obtain interesting input about
its physical environment, or to make its output affect the gross
features of the CA’s physical state. If you like, we’ll have a recipe
for creating a universe full of ivory-tower, eggheaded nerds, who can
search for counterexamples to Goldbach’s Conjecture but can’t build a
shelter to protect themselves from a hail of “1” bits, or even learn
whether such a hail is present or not.
Janzing’s notion of physical universality is directly addressing this
“egghead” problem, by asking whether we can build not merely a
universal computer but a particularly powerful kind of robot: one that
can effect a completely arbitrary transformation (given enough time,
of course) on any part of its physical environment. And the answer
turns out to be that, at least in a weird CA consisting of clouds of
diagonally-moving particles, we can indeed do that. The question of
whether we can also achieve physical universality in more "natural"
CAs remains ripe for exploration.