Hacker News new | past | comments | ask | show | jobs | submit login

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




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: