(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.