Contents Oh My Gosh, It’s Covered in Rule 30s!

Oh My Gosh, It’s Covered in Rule 30s!

A British Train Station

A week ago a new train station, named “Cambridge North”, opened in Cambridge, UK. Normally such an event would be far outside my sphere of awareness. (I think I last took a train to Cambridge in 1975.) But last week people started sending me pictures of the new train station, wondering if I could identify the pattern on it:

Cambridge North train station

And, yes, it does indeed look a lot like patterns I’ve spent years studying—that come from simple programs in the computational universe. My first—and still favorite—examples of simple programs are one-dimensional cellular automata like this:

One-dimensional cellular automata

The system evolves line by line from the top, determining the color of each cell according to the rule underneath. This particular cellular automata I called “rule 182”, because the bit pattern in the rule corresponds to the number 182 in binary. There are altogether 256 possible cellular automata like this, and this is what all of them do:

256 possible cellular automata

Many of them show fairly simple behavior. But the huge surprise I got when I first ran all these cellular automata in the early 1980s is that even though all the rules are very simple to state, some of them generate very complex behavior. The first in the list that does that—and still my favorite example—is rule 30:

Rule 30

If one runs it for 400 steps one gets this:

After 400 steps

And, yes, it’s remarkable that starting from one black cell at the top, and just repeatedly following a simple rule, it’s possible to get all this complexity. I think it’s actually an example of a hugely important phenomenon, that’s central to how complexity gets made in nature, as well as to how we can get a new level of technology. And in fact, I think it’s important enough that I spent more than a decade writing a 1200-page book (that just celebrated its 15th anniversary) based on it.

And for years I’ve actually had rule 30 on my business cards:

Business cards

But back to the Cambridge North train station. Its pattern is obviously not completely random. But if it was made by a rule, what kind of rule? Could it be a cellular automaton?

I zoomed in on a photograph of the pattern:

Enlarged pattern

Suddenly, something seemed awfully familiar: the triangles, the stripes, the L shapes. Wait a minute… it couldn’t actually be my favorite rule of all time, rule 30?

Clearly the pattern is tipped 45° from how I’d usually display a cellular automaton. And there are black triangles in the photograph, not white ones like in rule 30. But if one black-white inverts the rule (so it’s now rule 135), one gets this:

Black-white inversion of the pattern

And, yes, it’s the same kind of pattern as in the photograph! But if it’s rule 30 (or rule 135) what’s its initial condition? Rule 30 can actually be used as a cryptosystem—because it can be hard (maybe even NP complete) to reconstruct its initial condition.

But, OK, if it’s my favorite rule, I wondered if maybe it’s also my favorite initial condition—a single black cell. And, yes, it is! The train station pattern comes exactly from the (inverted) right-hand edge of my favorite rule 30 pattern!

Edge of rule 30

Here’s the Wolfram Language code. First run the cellular automaton, then rotate the pattern:

Rotate[ArrayPlot[CellularAutomaton[135, {{1},0},40],Mesh->True],-45 Degree]

It’s a little trickier to pull out precisely the section of the pattern that’s used. Here’s the code (the PlotRange is what determines the part of the pattern that’s shown):

Graphics[Rotate[First[ArrayPlot[CellularAutomaton[135, {{1},0},80],Mesh->True]],-45 Degree], PlotRange->{{83,104},{-12,60}}]

OK, so where is this pattern actually used at the train station? Everywhere!

Cambridge North collage

It’s made of perforated aluminum. You can actually look through it, reminiscent of an old latticed window. From inside, the pattern is left-right reversed—so if it’s rule 135 from outside, it’s rule 149 from inside. And at night, the pattern is black-white inverted, because there’s light coming from inside—so from the outside it’s “rule 135 by day, and rule 30 at night”.

What are some facts about the rule 30 pattern? It’s extremely hard to rigorously prove things about it (and that’s interesting in itself—and closely related to the fundamental phenomenon of computational irreducibility). But, for example—like, say, the digits of π—many aspects of it seem random. And, for instance, black and white squares appear to occur with equal frequency—meaning that at the train station the panels let in about 50% of the outside light.

If one looks at sequences of n cells, it seems that all 2n configurations will occur on average with equal frequency. But not everything is random. And so, for example, if one looks at 3×2 blocks of cells, only 24 of the 32 possible ones ever occur. (Maybe some people waiting for trains will figure out which blocks are missing…)

When we look at the pattern, our visual system particularly picks out the black triangles. And, yes, it seems as if triangles of any size can ultimately occur, albeit with frequency decreasing exponentially with size.

If one looks carefully at the right-hand edge of the rule 30 pattern, one can see that it repeats. However, the repetition period seems to increase exponentially as one goes in from the edge.

At the train station, there are lots of identical panels. But rule 30 is actually an inexhaustible source of new patterns. So what would happen if one just continued the evolution, and rendered it on successive panels? Here’s the result. It’s a pity about the hint of periodicity on the right-hand edge, and the big triangle on panel 5 (which might be a safety problem at the train station).

Successive panels

Fifteen more steps in from the edge, there’s no hint of that anymore:

Fifteen more steps

What about other initial conditions? If the initial conditions repeat, then so will the pattern. But otherwise, so far as one can tell, the pattern will look essentially the same as with a single-cell initial condition.

One can try other rules too. Here are a few from the same simplest 256-rule set as rule 30:

Simple 256-rule set

Moving deeper from the edge the results look a little different (for aficionados, rule 89 is a transformed version of rule 45, rule 182 of rule 90, and rule 193 of rule 110):

Moving deeper from the edge

And starting from random initial conditions, rather than a single black cell, things again look different:

Starting from random initial conditions

And here are a few more rules, started from random initial conditions:

A few more rules

Here’s a website (made in a couple of minutes with a tiny piece of Wolfram Language code) that lets you experiment (including with larger rule numbers, based on longer-range rules). (And if you want to explore more systematically, here’s a Wolfram Notebook to try.)

Cellular automaton panel explorer

It’s amazing what’s out there in the computational universe of possible programs. There’s an infinite range of possible patterns. But it’s cool that the Cambridge North train station uses my all-time favorite discovery in the computational universe—rule 30! And it looks great!

The Bigger Picture

There’s something curiously timeless about algorithmically generated forms. A dodecahedron from ancient Egypt still looks crisp and modern today. As do periodic tilings—or nested forms—even from centuries ago:

Periodic tilings and nested forms

But can one generate richer forms algorithmically? Before I discovered rule 30, I’d always assumed that any form generated from simple rules would always somehow end up being obviously simple. But rule 30 was a big shock to my intuition—and from it I realized that actually in the computational universe of all possible rules, it’s actually very easy to get rich and complex behavior, even from simple underlying rules.

And what’s more, the patterns that are generated often have remarkable visual interest. Here are a few produced by cellular automata (now with 3 possible colors for each cell, rather than 2):

Three-color cellular automata

There’s an amazing diversity of forms. And, yes, they’re often complicated. But because they’re based on simple underlying rules, they always have a certain logic to them: in a sense each of them tells a definite “algorithmic story”.

One thing that’s notable about forms we see in the computational universe is that they often look a lot like forms we see in nature. And I don’t think that’s a coincidence. Instead, I think what’s going on is that rules in the computational universe capture the essence of laws that govern lots of systems in nature—whether in physics, biology or wherever. And maybe there’s a certain familiarity or comfort associated with forms in the computational universe that comes from their similarity to forms we’re used to in nature.

But is what we get from the computational universe art? When we pick out something like rule 30 for a particular purpose, what we’re doing is conceptually a bit like photography: we’re not creating the underlying forms, but we are selecting the ones we choose to use.

In the computational universe, though, we can be more systematic. Given some aesthetic criterion, we can automatically search through perhaps even millions or billions of possible rules to find optimal ones: in a sense automatically “discovering art” in the computational universe.

We did an experiment on this for music back in 2007: WolframTones. And what’s remarkable is that even by sampling fairly small numbers of rules (cellular automata, as it happens), we’re able to produce all sorts of interesting short pieces of music—that often seem remarkably “creative” and “inventive”.

From a practical point of view, automatic discovery in the computational universe is important because it allows for mass customization. It makes it easy to be “original” (and “creative”)—and to find something different every time, or to fit constraints that have never been seen before (say, a pattern in a complicated geometric region).

The Cambridge North train station uses a particular rule from the computational universe to make what amounts to an ornamental pattern. But one can also use rules from the computational universe for other things in architecture. And one can even imagine a building in which everything—from overall massing down to details of moldings—is completely determined by something close to a single rule.

One might assume that such a building would somehow be minimalist and sterile. But the remarkable fact is that this doesn’t have to be true—and that instead there are plenty of rich, almost “organic” forms to be “mined” from the computational universe.

Ever since I started writing about one-dimensional cellular automata back in the early 1980s, there’s been all sorts of interesting art done with them. Lots of different rules have been used. Sometimes they’ve been what I called “class 4” rules that have a particularly organic look. But often it’s been other rules—and rule 30 has certainly made its share of appearances—whether it’s on floors, shirts, tea cosies, kinetic installations, or, recently, mass-customized scarves (with the knitting machine actually running the cellular automaton):

CA art

But today we’re celebrating a new and different manifestation of rule 30. Formed from permanent aluminum panels, in an ancient university town, a marvellous corner of the computational universe adorns one of the most practical of structures: a small train station. My compliments to the architects. May what they’ve made give generations of rail travelers a little glimpse of the wonders of the computational universe. And maybe perhaps a few, echoing the last words attributed to the traveler in the movie 2001: A Space Odyssey, will exclaim “oh my gosh, it’s covered in rule 30s!”


(Thanks to Wolfram Summer School alum Alyssa Adams for sending us the photos of Cambridge North.)

This post has been updated to include an image of Cambridge North at night, courtesy of Quintin Doyle, Senior Architectural Designer, Atkins.

9 comments

  1. Wow! You think they’d have invited you to the launch and put a plaque up to let the general public in on the reference. Perhaps we can rectify the latter?

  2. When the state of something, an entity, like a Cell in a CA is affected by the states of its surrounding entities, cells in a CA, there is bound to be complexity down the line if a sufficient amount of the history of evolution of the interactions is stored and if the simple rules governing the interactions allows it.

  3. The bit on thinking about art using existing patterns in nature as “photography” is a great insight. It actually clarifies feelings I have about sample-based music!

    Cheers to the Atkins Group, apparently the firm responsible for these designs.

  4. This is super cool 🙂

  5. Quintin Doyle, Senior Architectural Designer, Atkins, left us a comment at The Aperiodical confirming they indeed went for Rule 30 and discussing why.

    http://aperiodical.com/2017/05/right-answer-for-the-wrong-reason-cellular-automaton-on-the-new-cambridge-north-station/#comment-780944

    Peter.

  6. Mr. Wolfram–I am fascinated by these automata, but am struggling to see how they get build step-by-step. Can you explain with pictures or refer me to a website (I could not find any myself…) that show how the pattern builds step-by-step over time? Thank you and sorry for such a simple question.

  7. Mathematician Andrej Bauer has kindly sent in his own rule 30 sighting in the wild, at an outdoor art exhibition in Ljubljana, Slovenia.

    About the artwork:
    “Rule 30 – Moire”
    Artist Tomaž Šimnovec says, “In the Rule 30 – Moire project I investigated perception and creation of illusion, both semantically and visually. The particle nature of the Rule 30 pyramid transitions into its wave nature, which causes the perception of Moire patterns.”
    (translation provided by Andrej Bauer)

  8. They way CA has been treated to create sound in WolframTones is extremely limited and anthropocentric. Superposing the mathematically constrained qualities of western tonal practice (and a hugely simplified version at that) over the open-ness of CA reduces its granularity violently. Schoenberg would have some things to say! I know how to do it but I don’t have the gear. Also, have you looked for patterns along the line, rather than in its history? I’d expect you have but I can’t find information online (not sure what the search terms would be) and sadly, I’ve lost my copy of ANKOS!