This looks fascinating; any chance someone can easily explain the significance of the terms and the image? Seems daunting to look everything up and try to understand as a layman.
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.
> 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 suspect the main difficulty is not in finding the glider pattern, but in proving that it is in fact a glider. This is not brute-forceable with an aperiodic tiling, pretty much by the definition of an aperiodic tiling.
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!
If you restrict the vertices you are looking at to the ones within some fixed distance from a central vertex, there are only finitely many cases. This could make brute-forcing possible. (I do agree, though, that this is non-trivial and it looks like that was mainly what you were getting at).
It's not just a matter of the grid, it's also a matter of the rule that is carried out on that grid.
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.
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.
No word on that - not very many people want to drop two large on a laptop and then peel back every layer. But I'd say if we see it even once more that's a sign that it's probably a constant. Glad you liked the article.
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:
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.
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.
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.
How exactly did they go about proving that it continues to glide forever, despite the lack of periodicity? Is there some finite combination of subsequent tile groups in aperiodic tilings, such that you just have to show that all of them involve a transition another part of the glider cycle?
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.
That's just plain stupid and annoying. I didn't notice yet since I've abandoned my Google Account a few months back and am therefore not signed into Google at all.
However, why do they do that? Hasn't it occurred to them that not everybody with a Gmail Account wants to be on G+?
Edit: Awesome, thanks everyone! <3 HN