Good news, everyone! I literally jumped out of my seat and punched the air when I saw this story. It’s as if this site was set up specifically to report on this exact piece of news.

But before I explain why I’m so excited, here’s a quick summary of some terms you need to know:

• Conway’s Game of Life is a computational toy which takes place on a grid of squares which are either “alive” or “dead”. At each turn of the game, squares flip between the alive or dead states depending on how many of their neighbours are alive.
• A cellular automaton, or CA, is the generalisation of this idea to an arbitrary tiling of space and set of rules for flipping between states. The important restriction is that the evolution of a square’s state only depends on its immediate neighbours, not on some function of the entire world.
• A glider is a pattern on a CA which seems to move across the world, never looping back on itself.

You might remember Ready, the reaction-diffusion system simulator that we posted about a few weeks ago. Reaction-diffusions are sort of the continuous-valued generalisation of cellular automata, so people have been using Ready’s very versatile framework to play about with some fruity variants of cellular automata, including ones operating on Penrose tilings.

Just under a fortnight ago the question came up on the Ready mailing list of whether it was possible to construct a glider on a Penrose tiling automaton. After some humming and hawing, the answer is yes! Adam Goucher was the first to get there with a five-state automaton, but that’s since been optimised to the four-state automaton you see gliding across the top of this post. To avoid confusion, I’ll repeat that they have created a glider on a very specific cellular automaton, not in the Game of Life applied to a Penrose tiling.

The story was picked up first by Hacker News and then by Jacob Aron at New Scientist, who has written a happily maths-free narrative of what happened.

Robert Munafo has written up a very concise and clear proof that the glider really is a glider. The idea is to start with a “head” cell and an adjacent “tail”. The neighbouring cells can then be labelled depending on how they touch either cell, and the glider should move into the cell touching the head at a single edge but not touching the tail at all.

The way this is implemented as a cellular automaton is by using four states (three “living” states and a “dead” state), with the glider alternating between two basic patterns on each turn. On the first turn, the head and the tail are in states 1 and 2, respectively. Then the cells touching both the head and the tail change to state 3, as does the tail. Now the cell into which the glider is going to move is touching the head and at least 2 cells in state 3, so that becomes state 1, the old head becomes state 2, and all the cells in state 3 die back to state 0. Now the glider is in the same pattern as it was to begin with — a head and a tail touching at an edge — but moved one cell along.

The only niggle is to show that this pattern never loops back on itself, but Robert Munafo gives a pretty convincing argument against that happening — the glider always moves away from its initial position. I need to correct an error in the New Scientist piece here — the glider doesn’t move in what you would normally call a straight line: it’s only been proved that it always stays on the same side of the edge shared by the first head and tail cells, so it might wander about to the left or right indefinitely, depending on how the rhombi that make up the Penrose tiling are connected to each other.

The automaton has already been included in the Ready package, so all you need to do to see it in action is to download Ready and select penrose_goucher_glider.vtu from the list of patterns ((I also had to install the OpenCL library for my graphics card. For AMD, I needed the APP SDK)).

I love cellular automata and I love aperiodic tilings. This is so cool!