Picture This: Rule 30
What did it mean? How could it do that? It was June 1st, 1984, when I first made this picture of what I called Rule 30. And the more I looked at the picture, the more surprising it seemed. How could a rule so simple (shown above) make something so complex? My intuition from science—and engineering—was that, to make something complex, one had to do complex things according to some kind of complex procedure. But yet, here was a very simple rule making what seemed to be immense complexity.
The more I studied it, the more I realized that this was something fundamentally different from what existing science normally talked about. And instead, it was a first clue towards a new kind of science.
That was all nearly 40 years ago. In the intervening decades, what began as one picture has indeed grown into a whole new kind of science, with new kinds of methods, new kinds of intuition, and a whole new kind of way of thinking about the world.
For me, seeing the picture of Rule 30 was my personal "Galileo moment." Nearly four centuries earlier—on January 2, 1610—Galileo had turned his telescope to the sky and seen "three little stars" lined up near Jupiter—which he soon realized were moons that orbit Jupiter much like planets orbit the Sun. It was a discovery nobody expected, but it was a clue towards a new, more abstract way to think about science. And from it grew what over the course of three centuries was to become the whole edifice of modern mathematical science.
My discovery of Rule 30 was the result of turning not an optical telescope at the astronomical universe, but instead a "computational telescope" at the computational universe—of observing not a pattern of light coming from a distant body, but instead a pattern of bits made by a simple program out in the computational universe of possible programs.
Galileo's discovery in 1610 was the direct result of the availability of new technology: an improved telescope that made it possible to resolve things like the moons of Jupiter. My discovery of Rule 30 was also the direct result of new technology: in this case, the availability of a high-resolution printer that let me easily see many steps in the behavior of Rule 30. As it turns out, I had actually produced small versions of the Rule 30 picture, and even published them in scientific papers a couple of years before June 1st, 1984. But what Rule 30 does just didn't fit into my previous way of thinking, so I never internalized what I was seeing. It was only through the “you-can't-ignore-this” force of the picture above—with its obvious complexity—that I came to internalize the "Rule 30 phenomenon."
It didn't take long before I began to see some of the significance of what was going on. And in particular, before I began to understand the phenomenon of computational irreducibility. But before talking about this, let me describe just what the Rule 30 picture is showing.
Let’s start with the top row of cells, all white except for a single black one in the middle. Then we go line by line down the page, at each step applying Rule 30 to each cell. The rule looks at a cell and its left and right neighbors, then determines the new color of the cell. It's like a very simple program that takes as input one configuration of colors, and outputs another. I called it "Rule 30" because if one treats the sequence of output cell values 00011110 in the rule (with black being 1 and white being 0) as a number in base 2, then when converted to ordinary base 10, one gets 30.
So there's a simple rule for generating the picture. You might think that, given such a simple rule, you should immediately be able to predict everything about what will happen. Indeed, most of the great achievements of the mathematical approach to science launched by Galileo's discovery have at their core the idea that we can derive a mathematical formula for how something in nature behaves, and then use this formula to predict what the thing will do. An idealized planet might make a million revolutions around an idealized star, but by using the mathematical formula for the two-body problem, we can immediately predict the outcome of those million revolutions.
But what about Rule 30? Can we predict the outcome of a million steps of its evolution? Clearly we can just run it—say on a computer—for a million steps, and see what happens. But the essence of computational irreducibility is that we can't expect to do much better than Rule 30. Unlike for our idealized planet, there is no "mathematical formula" for what will happen. There is no "reduced computation" that will let us predict what the system will do. Instead, we must think about the system as doing a certain irreducible amount of computation.
It's an important idea—it suggests that in a sense science defines its own limits. Yes, we can know what the underlying rule is. But we can't know its consequences except by doing an irreducible amount of computational work. And while this might seem bad, in terms of limiting our foresight about what will happen, it's also good at making the passage of time seem meaningful. Computational irreducibility means that we can't just solve for our future and know the outcome will be; we actually have to live out our years, in effect playing out the irreducible computation that is our lives.
Seeing the Rule 30 picture, I could have just said, "Unfortunately, the science I know doesn't really say anything about this" and ignored it. But I feel very fortunate to have realized that the challenge of Rule 30 was not an end, but a beginning: a beginning of what would define a whole new kind of science.
In ancient Greek times, science mostly just described the explicit structure of things. The great shift initiated by Galileo's discovery was the idea that one could also base science on mathematics, and describe things in nature by mathematical formulas. What began with Rule 30 is a newer and different paradigm for science, based not on mathematics and mathematical equations, but rather on computation and computational rules.
Some of what we see in nature can be readily described at just a structural level. For some, we can derive mathematical formulas. But a lot of what goes on in nature just seems too complex for that. Now that we have the computational paradigm, we can begin to see that the secret that nature has long harbored which allows it, seemingly so effortlessly, to create such complexity is just the same kind of thing we see in the picture of Rule 30—a manifestation of the fundamental phenomenon of computational irreducibility.
In a sense, the most striking thing about the Rule 30 picture is how much one gets out from the little one puts in. And thinking about this makes me wonder about our whole universe. Could it work like Rule 30? With only a very little being put in, but everything we experience eventually coming out? Starting 30 years ago, I began to formulate how such ideas might relate to fundamental physics and the construction of our universe.
About three years ago, all this began to come together. And, yes, it really does seem that there is a lower-level "machine code" from which the core results of physics emerge. The details aren't like Rule 30. But the concept that something like this might be possible arose entirely from that one great surprise of the Rule 30 picture.
Nowadays I talk about the ruliad—the entangled limit of all possible computations—and how physics, as well as mathematics, are the result of our human observation of this underlying formal structure. The science of ruliology is concerned with studying what particular rules do; in effect, exploring individual places in the ruliad, the space of all rules. Rule 30 was the first glimpse of the amazing structure that we are now beginning to understand as the ruliad.
In the end it all came from that one picture, my all-time favorite scientific discovery. A timeless image of the consequences of a particular, simple computational rule. A new way of thinking about science and much beyond: Rule 30. ♦
Subscribe to Broadcast