Edit: Awesome, thanks everyone! <3 HN
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.
Do you know why wasn't it found so far? Looking at one of the stages, it consists of only two cells. That's something that should be picked up by anyone trying to run a brute-force search for gliders in well under a minute. It's a bit hard to accept for me that it's been an unknown thing for anyone who asked the question. Even the smallest glider on the standard grid is larger in all of the steps. Here you have to consider placing it in a number of places too, but... is this the first time different grid was really considered?
I feel like I'm missing some bigger picture here.
Let's say you have a pattern P, and you want to check if it's a glider. In Conway's Life, this is straightforward and mechanical: iterate the future states of P, and check if any of them are P but translated some distance. But on a Penrose board, this is not possible: if you translate the pattern, the board is different. You cannot assume that because P translated successfully once, it will translate again (i.e. you cannot "induct").
Furthermore, because the tiling is aperiodic, even brute-forcing the possible patterns is troublesome. Every pattern must specify its origin! On Conway's life, there is only 1 possible 1-tile starting pattern, and only 2 non-trivial 2-tile patterns, because it doesn't matter where you are. Starting your pattern at (0,0) doesn't make it any different than starting at (12,-156). That's not the case on a Penrose board: there are an infinite number of 2-tile cases, one for every possible board location, because they're all different!
It looks like this is a 4+ state rule, meaning the rule space is massive. To brute force this you would need to not only brute force your way to that small configuration of cells, but you would need to do it for a huge number of different rules before settling on one (I can't say what percentage of this state space would support small gliders, but my intuition says it's relatively rare).
I think maybe you are looking at this from the perspective of studying the game of life, where the rule is already chosen.
One actually showed up drilled into the side of a new retina Macbook Pro; I wrote it up for TechCrunch (with suitable woolgathering):
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 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:
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.
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.
gliders - http://en.wikipedia.org/wiki/Glider_%28Conway%27s_Life%29
penrose tiles - http://en.wikipedia.org/wiki/Penrose_tiles
> Google "Conway's Game of Life"
PS. Also, somebody posted it on HN 3 weeks ago, but got no love: http://news.ycombinator.com/item?id=4224926
what would it mean for the glider's path in 5D (well, 6D with time) ?
Five possible directions for the glider to travel in = Five dimensions of space.
(Is that right?)
However, why do they do that? Hasn't it occurred to them that not everybody with a Gmail Account wants to be on G+?
Of course it's occurred to them. Why else would they be trying to force them?