3 ms·

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

by sltkr 14y ago

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.

viraptor 14y ago
> 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.
- lmkg 14y ago
  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!
  - tprice7 14y ago
    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).
- lastseen 14y ago
  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.

by sltkr 14y ago

viraptor 14y ago

> 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.

lmkg 14y ago
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!
- tprice7 14y ago
  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).
lastseen 14y ago
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.