First glider discovered in a cellular automata on an aperiodic tiling

The penrose tiling goes on for ever, but never repeats the pattern, a bit like a geometric version of an irrational number, so to make a propagating 'glider' out of simple rules similar to conway's game of life played out on that form of grid, would seem to be very difficult at first glance. So this is very very cool.

gliders - http://en.wikipedia.org/wiki/Glider_%28Conway%27s_Life%29

penrose tiles - http://en.wikipedia.org/wiki/Penrose_tiles

A 'glider' is a self-propagating pattern generated in Conway's Game of Life. It's a basic simulation of complex behavior using a grid governed by simple rules made to suggest isolation, reproduction, and overpopulation. These simple rules produce some incredibly complex patterns, some of which can be likened to creatures. The 'glider' is a very basic one that travels in a relatively straight line and can be used to activate or transmit information between other patterns.

One actually showed up drilled into the side of a new retina Macbook Pro; I wrote it up for TechCrunch (with suitable woolgathering): http://techcrunch.com/2012/06/23/laocoon/

This Game of Life uses a totally different grid style, which changes the patterns that emerge and the math involved. This guy has created a glider for a rhomboidal grid environment, and that's... pretty cool.

I hope you're at least familiar with Conway's Game of Life? If not, go look that up first. ;-)

Standard Life uses a rectangular grid with a Moore-neighbourhood: cells are squares and all cells that share either an edge or a corner are neighbours. In such an environment, and under convenient propagation rules, patterns exist that translate themselves in a couple of generations. In Life, these are called “gliders” if they move diagonally, and “spaceships” if they move orthogonally. (Again, go lookup these things if you're not aware of them.)

In a rectangular grid it's easy to see that a glider in empty space moves indefinitely, because after a couple of iterations, the state is equivalent to the start state (up to translation). But that's not true in an aperiodic tiling, like a Penrose tiling, because the topography of the surrounding space changes all the time. (If you aren't familiar with aperiodic tilings, go look up e.g. Penrose tiling on Wikipedia.)

So now for the novelty. In the linked discussion, Andrew Trevorrow notes:

> I was trying to picture what a glider path would look like on an aperiodic tiling, but came to the conclusion that such a thing isn't really possible.

So it's not obvious that a glider-like pattern (a pattern that translates itself without growing or leaving crud behind) could exist on any aperiodic tiling. The significance of this discovery is that it shows that, contrary to intuition, they do exist.

You've heard of Conway's Game of Life, a cellular automata (CA) on a square grid. There the glider travels over a nice repeating grid.

Now imagine that the grid itself is changing underneath the glider - it will just fall apart. That's what we saw when we looked at Penrose's famous non-repeating grids - it looks impossible to have a glider that would work. A bit like trying to rollerblade over rubble.

See earlier in the linked thread for a link to the paper by Nick Owens and Susan Stepney that started us thinking in this direction.

I am a layman, so I can’t actually answer your question properly, and others have given very excellent answers already. But if it interests you, here is why this is “surprising” to me, and in math, the most excellent feeling is often one of being surprised by a result and then figuring out why things are not the way you expected them to be.

I may be misusing the word, but it starts with “symmetry.” Symmetry is the general case of something remaining the same after being put through some sort of transformation. So a square is symmetrical when transformed by reflection along either of two axes. This generalizes in other ways. We are pretty sure that gravity works the same way on Earth as on the Sun, and the same on the Sun as on other starts in our galaxy, and the same way here as it does on galaxies far far away. So gravity is the same when transformed by being moved across any arbitrary distance in space.

Conway’s Game of Life has translational symmetry. If you take any cell and look at its neighbours, they are always arranged in the same grid, they look like each other. So you can say that if you take any point and “translate” it by moving it somewhere else, it will behave the same way. The same goes for any pattern or formation of cells: You can move them somewhere else and they will look the same way and behave the same way.

Thus, a glider that “moves” across the Life universe is constantly moving from one place that looks like everywhere else to another place that looks like everywhere else. Although you may not guess exactly what a glider or spaceship or puffer train or any other ‘moving’ formation looks like, you can guess that there is no special impediment to their existence, because if something were to move from place A to place B, it would automatically repeat all over again and move to point C and then D and so on because point B looks just like A and C looks just like B.

So yes, you have to solve how to move from A to B in such a way that you don’t leave any debris around so that the universe from the vantage of point B looks just like the universe from the vantage of point A. But then the thing will just keep going forever.

But what about a universe with Penrose tiling? Well, this is different. The defining characteristic of Penrose tiling is that it lacks translational symmetry:

https://en.wikipedia.org/wiki/Penrose_tiling

By definition, no two places in a Penrose-tiled universe look just like each other. If you have place A and place B, and they are different places, the exact arrangement of neighbours is going to be different. In a Penrose-tiled universe, you can figure out exactly where you are by looking at your neighbourhood.

For this reason, if we take some point A and construct a formation that replicates itself while moving to point B, we cannot assume that it will now replicate itself and move to point C, because we know that the neighbourhood around B is not the same as the neighbourhood around A. The pattern must somehow be specially crafted to deal with any and every possible arrangement of tiles within its neighbourhood.

Furthermore, if it is to ‘glide’ and not circle like a boomerang, it must be crafted not to turn in any arbitrary way, because it is deterministic, and if it ever returns to a place it has been, it will be trapped in a loop forever.

Obviously it is possible, you are looking at such a thing. But given the basic problem that no two places look like each other in a Penrose-tiled universe, it is very surprising to me that any glider exists, much less a small and simple one.

More importantly, the fact that a simple glider exists suggest that there is some translational symmetry going on even though the exact neighbourhood of cells is different everywhere you look in the Penrose-tiled universe. That’s interesting.

Watch the cyan tile carefully in the animation. It always propagates to adjacent rhombi across edges, all of which are parallel.

Yes, I think that's right. This page talks about De Bruijn's pentagrids method, which uses the same rhombi ribbons as the glider travels on as the axes of the 5D space: http://www.ams.org/samplings/feature-column/fcarc-ribbons

Five possible directions for the glider to travel in = Five dimensions of space.

(Is that right?)

I can read it without being signed in to Google.

You have to sign in because you're signed in to a Google account but not Google+. If you were either signed in to Google+, or not signed into Google at all, you would see the article without a sign-in prompt.