gliders are impossible in Penrose tiling?  Andrew Trevorrow  7/23/12 7:56 PM  In penrose.vtu we have the comment: "No gliders have yet been found".
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. Imagine a glider phase with some configuration of 3 tiles called ABC. (It doesn't really matter how big, small or complicated ABC might be.) The problem is that all other ABC configurations in the tiling are aperiodic, so even if a pattern could move from one ABC to another nearby ABC, the chances of it then moving to more distant ABC "islands" become increasingly unlikely, given that the intervening tiles between the ABC configurations aren't periodic. But I'm notoriously bad at this sort of abstract thinking, so maybe I've missed something? (If the aperiodic tiling is on some sort of bounded 3D surface then yes, a pattern could move from one ABC island to another and back to the original, but in a bounded surface there is strictly speaking no gliders, just oscillators.) Andrew 
Re: gliders are impossible in Penrose tiling?  Robert Munafo  7/23/12 9:13 PM  For penrose.vtu as it currently exists (a deterministic Lifelike
cellular automaton) I agree that a "glider" in the Life sense (something that travels indefinitely in a straight line) can't be done. However you might be able to do a "glider" that travels in a circle around the (unique) point of 5fold rotational symmetry. There are lots of shapes in GrayScott (in the Uskate parameters) that travel indefinitely on a curved path and I think of these as "gliders". Also, if you run reactiondiffusion on a Penrose mesh, then just like any other type of mesh, most normal reactiondiffusion patterns should be possible. Here is a Java applet that simulates GrayScott on four kinds of meshes, (regular rectangular and hex, and two kinds of random): http://groups.csail.mit.edu/mac/projects/amorphous/jsim/sim/GrayScott.html I was able to get my "Uskate" to run on hex and random meshes, although it didn't last forever because the simulation was a bit too crude (just like when we were having trouble getting the Uskate to work in Ready). I probably could have gotten it to work by adjusting ru,rv,dt and using a finer grid (more "processors"). > really possible. [...]  Robert Munafo  mrob.com Follow me at: gplus.to/mrob  fb.com/mrob27  twitter.com/mrob_27  mrob27.wordpress.com  youtube.com/user/mrob143  rilybot.blogspot.com 
Re: gliders are impossible in Penrose tiling?  Andrew Trevorrow  7/23/12 11:59 PM  Robert:
Yep, I was only thinking about a discrete CA. > around the (unique) point of 5fold rotational symmetry. ... Strictly speaking that would be an oscillator, regardless of how big the circle. But yes, it would be interesting to discover such a pattern. Clearly travel in a straight line is impossible, but at one point I was thinking it might be possible for a pattern to travel in an increasingly larger spiral about a symmetry point, until I thought about it a bit more. Andrew 
Re: gliders are impossible in Penrose tiling?  Tim Hutton  7/24/12 12:51 AM  I thought that. But read their papers! I agree it seems unlikely. 
Re: gliders are impossible in Penrose tiling?  Andrew Trevorrow  7/24/12 4:17 AM  Tim:
> I thought that. But read their papers! ... I've read their chapter (again) in the Adamatzky book, which seems identical to the online version (http://wwwusers.cs.york.ac.uk/susan/bib/ss/nonstd/penroselife.pdf) but I can't find anything remotely like a convincing argument that gliders are possible. On page 37 of the pdf they say: Quiescence detection is straightforward: we detect when the behaviour of the CA becomes periodic (this would not work if ever a propagating structure like a regular Life glider were to form, but this has never been the case so far). That doesn't even make much sense given they are working with a finite tiling and thus any glider would hit the edge and either disappear or stabilize. On page 51: We have found no propagating features analogous to gliders, but the existence of "fuses" burning along chains makes us optimistic that such structures may be discovered. That's it. I fail to see any connection between a burning fuse (which requires a previously created pattern of live cells) and a glider propagating by itself in a sea of dead cells. But again, maybe I'm missing something. Or is there another paper somewhere with a more detailed argument? Andrew 
Re: gliders are impossible in Penrose tiling?  Tim Hutton  7/24/12 5:02 AM  Thanks for pulling out that quote about fuses and gliders  that bit
about them being 'optimistic' was all I was referring to. Presumably their point is that if stable fuses can be made along a wiggly track of arbitrary length then a glider could conceivably take the same route? We could probably engineer one in an Nstate CA. In B3/S23 I agree it is unlikely. I think Robert's point about uskate on an aperiodic tiling is interesting. Any floatingpoint CA can be approximated to arbitrary accuracy by a discrete CA with a large number of states so therefore it *is* possible to have a uskate style glider in a discrete CA on a Penrose grid, even with only the Moore neighborhood.  Tim Hutton  http://www.sq3.org.uk  http://profiles.google.com/tim.hutton/ 
Re: gliders are impossible in Penrose tiling?  Andrew Trevorrow  7/24/12 4:53 PM  Tim:
I don't see any cause for such optimism. A fuse is purely destructive, but a glider requires destruction and creation in equal measure. Totally different mechanisms. I'll happily pay $100 to the person who can do that! Robert didn't actually get his uskate working on an aperiodic tiling. It was a random tiling (which is not quite the same thing), and even there it didn't last. Robert assumed this was because the simulation was too crude but I suspect the uskate will eventually stop working on an *infinite* aperiodic tiling, regardless of how fine the mesh. Anyway, enough waffling from me. It's an interesting subject though, and I'd love to be proven wrong! Andrew 
Re: gliders are impossible in Penrose tiling?  Tim Hutton  7/25/12 5:44 AM  On 25 July 2012 00:53, Andrew Trevorrow <and...@trevorrow.com> wrote:Challenge accepted! :) No, I don't know. Maybe. The only idea I had was that since the local neighborhood along the wiggly path is restricted to a known sequence of tiles we could craft a CA that could encode the shape of those neighborhoods in its states, and propagate that information along the path. But I could be quite wrong about this. When Ready is a little bit more mature it would be nice to throw this challenge open to the community. "Can you construct a glider in an Nstate (where N<1000) discrete CA that will travel an arbitrary distance on a Penrose P3 tiling, with the Moore neighborhood (vertexneighbors)?" "Can you prove that no glider exists capable of travelling an arbitrary distance on the B3/S23 2state CA on a Penrose P3 tiling, with the Moore neighborhood (vertexneighbors)?" Attached Robert's uskate working on a Penrose P3 tiling. It eventually hits the side and dies because there's no wraparound in this world but I think it proves the point. When we zoom out far enough the grid becomes irrelevant, as long as it satisfies basic conditions such as being connected in all directions. It would work on a random grid too. (I should add random grids as an option in Ready's File > New Pattern.) Of course I can't *prove* that it will keep going forever but I don't see why not. This is implemented in floats (32bit) and so would work with 32bit integers too  as a 4.3 billion state discrete CA. And certainly can be reduced below that. But probably nowhere near the N=1000 limit suggested in the challenge above, I should think, without a different approach. 
Re: gliders are impossible in Penrose tiling?  Andrew Trevorrow  7/25/12 4:10 PM  Tim:
> this world but I think it proves the point. ... Yep, impressive! I can already see my $100 slipping away... Andrew 
Re: gliders are impossible in Penrose tiling?  Andrew Trevorrow  7/25/12 5:18 PM  That was quick. Adam P. Goucher has won the $100 prize with a glider
in a 5state CA on a Penrose tiling! All this happened in some offlist emails. Adam's initial email:  I have created a glider on the Penrose rhomb tiling: Let the four neighbours of a rhombus be (in clockwise order) N, E, S, W. If we continue in the direction N > S, we will move on a wiggly path which does not loop (due to the opposite sides of a rhombus being parallel). To enforce a glider moving in this direction, let the set of von Neumann neighbours be V and the set of Moore neighbours be M. V is a subset of M. I'll write the rule table in the form c {V} {M} > c', where c and c' are the current and next states of the centre cell: 1 {any} {any} > 3 0 {at least one 1} {at least one 2} > 4 2 {any} {any} > 4 4 {any} {any} > 0 0 {at least one 3} {any} > 1 3 {any} {any} > 2 We don't care about any other rules, since these are the only ones necessary to govern the motion of the following glider: Generation #0: * 0 * 0 1 0 * 2 * Generation #1: * 0 * 4 3 4 * 4 * Generation #2: * 1 * 0 2 0 * 0 * (* indicates a variable number of tiles, possibly zero)  Tim pointed out that Ready only passes a list of Moore neighbors in no particular order or anything to distinguish them, but that didn't bother Adam:  Oh, I didn't realise. Okay, here's a modified glider for the Moore neighbourhood: 1 {any} > 3 2 {any} > 4 0 {at least one 1 and at least one 2} > 4 0 {at least one 3 and at least two 4s} > 1 3 {any} > 2 4 {any} > 0 Again, we start with the configuration comprising a '1' and '2' on adjacent (von Neumann metric) rhombi. If this glider works as intended, then it has an *aperiodic* population count!  Tim then implemented the glider in the attached file. $100 well spent! Andrew 
Re: gliders are impossible in Penrose tiling?  Robert Munafo  7/25/12 7:59 PM  The reason I assert that Uskates work on random grids is because they
are highly immune to noise. See this video: http://www.youtube.com/v/_sir7yMLvIo?rel=0 "This movie demonstrates the immunity of the "Ushaped moving pattern" to systematic random noise. At each frame (which is 73.5 dimensionless time units) the U and V values at each grid point are altered by a random amount. Beginning at about 3 seconds into the movie, the noise begins at a magnitude of 1.0e3. Each 10 seconds (11000 dimensionless time units in the simulation) this noise amplitude is doubled. Near the end of the movie the noise is so strong that the Ushaped patterns begin to be destroyed. The noise amplitude is brought back down to 1.0e3 for a few seconds to show that the remaining Ushape is capable of recovering." (from http://mrob.com/pub/comp/xmorphia/auxmovies2.html which includes several other demonstations of Uskate world phenomena and some of my other tests; see also http://mrob.com/pub/comp/xmorphia/uskateworld.html . The first page of aux. videos, http://mrob.com/pub/comp/xmorphia/auxmovies.html is a little less relevant.) The only reason I've ever seen them die out on a regular grid, is because the simulation is too coarse. This was why the first Uskate attempts weren't working in Ready.  Robert

Re: gliders are impossible in Penrose tiling?  Robert Munafo  7/25/12 9:01 PM  On 7/24/12, Tim Hutton <tim.h...@gmail.com> wrote:
> [...] Any floatingpoint CA can be approximated to arbitrary > accuracy by a discrete CA with a large number of states so thereforeAre you talking about using the discrete system to simulate a continuous system? Even with normal square grids I don't see how this helps. In Conway's Life, we can simulate Life in Life using "metapixels". However, simulating a glider with metapixels is NOT equivalent to a real glider. The metapixels have to be infinite in extent, and therefore do not comprise a pattern that is finite in size surrounded by some empty space. Since it's not finite in size surrounded by empty space, it's not a glider. More abstractly, we can simulate a Conway's Life in another (larger) Life pattern by implementing a Turingequivalent computer, then programming that computer to run a Life simulation. We can arrange for the computer to move while it is simulating the glider, thereby making it superficially resemble a glider, but still in some way its state must be able to expand indefinitely. (Even if the computer is merely storing the current X and Y coordinates of the simulated glider, these X and Y values will themselves grow without limit, taking roughly log(t) bits at time t, which grows arbitrarily large.) Since the computer will hold an unbounded number of bits of information, it will be of unbounded size, and is therefore not a glider. 
Re: gliders are impossible in Penrose tiling?  Robert Munafo  7/25/12 9:26 PM  On 7/25/12, Tim Hutton <tim.h...@gmail.com> wrote:Wow, I really like the texture (: There's an odd sort of shimmering on the leading edge (which I think would be easier to see if you save a series of PNG's and then make it into a video). I guess this shimmering is because of the fact that the long thin diamonds help propagate the diffusion more quickly, and sometimes the rhombs are aligned in the direction the Uskate is moving, other times not. As with the random grids, systematic noise, etc. I suspect the Uskate would be more stable if you used an even finer grid. Or as you put it "as you zoom out" the grid becomes irrelevant. 32bit floats also have 4.3 billion states, n'estce pas? No integers needed. Also, using OpenGL I discovered that GrayScott works just fine with 16bit floats. I wasn't able to get Uskates working though, because I was using Apple's Quartz Composer which seems to have some odd roundoff bugs or something. I wasn't trying too hard either (: 
Re: gliders are impossible in Penrose tiling?  Robert Munafo  7/25/12 9:48 PM  On 7/25/12, Andrew Trevorrow <and...@trevorrow.com> wrote:> in a 5state CA on a Penrose tiling! [...] When I read the comments about the "infinite fuse hypothesis" of Owens and Stepney, I was visualizing something like this, although I didn't try to figure it out. But I think perhaps this is the kind of thing Owens and Stepney had in mind, even though their paper seems to be all about twostate systems and S23/B3. If an infinite fuse is possible, then perhaps there is a pattern that is like a fuse running in reverse (growing forever, what we calla puffer train). And if both of those are possible, then why not gliders? Goucher's glider is much like what you'd get if you tried to make something grow indefinitely in a single direction, but make the tail die out as it goes along. Perhaps we can ask Owens or Stepney. The paper's not that old... 
Re: gliders are impossible in Penrose tiling?  Tim Hutton  7/26/12 4:21 AM  As a minor modification, the number of states can be reduced to 4. Attached.

Re: gliders are impossible in Penrose tiling?  Tim Hutton  7/26/12 4:44 AM  Sorry, that version had a bug. Attached a fixed version, and an animated gif.

Re: gliders are impossible in Penrose tiling?  Tim Hutton  7/27/12 6:04 AM  Some discussion of it going on here: http://news.ycombinator.com/item?id=4298515
nraynaud brings up the connection between the 5D projection method and the five directions of travel of the glider. This page talks about the ribbons: http://www.ams.org/samplings/featurecolumn/fcarcribbons It's a bit beyond me but I guess this means that the gliders are travelling along the orthogonal axes in the 5D space? Were you aware of this connection Adam? 
Re: gliders are impossible in Penrose tiling?  Robert Munafo  7/27/12 5:26 PM  I added a brief description of why the glider is possible on any place
filled with quadrilaterals, although a greater restriction is required to ensure it doesn't follow a looping path: http://mrob.com/pub/math/quadgridglider.html I don't see any way to join ycombinator . . . do I have to attempt an anonymous comment first?

Re: gliders are impossible in Penrose tiling?  Tim Hutton  7/28/12 12:09 AM 
Yes, good stuff.
Hit submit at the top. It's not very clear. 
Re: gliders are impossible in Penrose tiling?  Adam P. Goucher  7/28/12 3:50 AM  > I added a brief description of why the glider is possible on any placeYes, I designed the glider based on four postulates: A) Every cell is a quadrilateral; B) The graph is planar; C) Every vertex is shared by at least three cells; D) Continuing in the same direction does not result in a closed loop. Any planar arrangement of parallelograms is a sufficient (but not necessary) condition for the postulates to be true. > http://mrob.com/pub/math/quadgridglider.html This was similar to the thought processes I went through in designing the glider. I had seen the headtail approach on a square grid, but of course generalising it required more work. Sincerely, Adam P. Goucher 
Re: gliders are impossible in Penrose tiling?  Robert Munafo  7/28/12 4:24 PM  Thank you  I missed postulate C, but will add it now (:

Penrose glider article in New Scientist  Adam P. Goucher  8/4/12 2:49 PM  http://www.newscientist.com/article/dn22134firstglidersnavigateeverchangingpenroseuniverse.html
Hopefully this will reinvigorate interest in cellular automata on Penrose tilings. I believe that the only preReady research is that of Nick Owens and Susan Stepney, which was reported in their engaging chapter in Game of Life Cellular Automata (Andrew Adamatzky). I wouldn't be surprised if there exists a glider in a twostate Moore neighbourhood rule on the Penrose tiling. There's probably no small example akin to GoL's glider in the OwensStepney rule, since they would have already found it by now. However, we have a vast rulespace to explore, and who knows what lurks in this obscure corner of abstract Platonic reality? Sincerely, Adam P. Goucher 
Re: gliders are impossible in Penrose tiling?  Andrew Trevorrow  9/4/12 1:37 AM  katsuno...@gmail.com wrote:
> How do you think about this?
> This rule is S/B2/C4.
Whoa! It seems gliders in a Penrose tiling are as common as
dirt. :)
Please let me know your name (is it Katsunobu Imai?) so I can
give
you proper credit.
Attached is a Ready file that implements the same CA.
Andrew

Re: gliders are impossible in Penrose tiling?  Tim Hutton  9/4/12 2:12 AM  Katsunobu Imai is famous to me for his 1996 work on selfreplicating worms:
http://www.informatik.unitrier.de/~ley/db/indices/atree/i/Imai:Katsunobu.html Recently he published a paper on universal computation on a Penrose CA: http://www.newscientist.com/article/dn22222turingmachinegivesordertochaoticpenroseuniverse.html 
Re: gliders are impossible in Penrose tiling?  katsunobu.imai  9/4/12 5:11 AM  On 2012/09/04, at 17:37, Andrew Trevorrow <and...@trevorrow.com> wrote:
Yes, thank you. But in the case of Kite and Dart, it seems to be quite difficult for me to find a glider in the case of lifelike or generations CA.
Thank you. Just looking at evolutions from random configurations repeatedly, it seems reasonable that there exists any glider gun. Katsunobu 
Re: gliders are impossible in Penrose tiling?  katsunobu.imai  9/4/12 7:19 AM  In this case, once I tried to find any possibility of employing some line symmetric patterns to build a glider. Then the movement of resulting patterns must be on a line in a certain interval. http://www.youtube.com/watch?v=6aOwNIs_ENo This rule is also B2/S/C4. Bus no meaningful result, so far. 
Re: gliders are impossible in Penrose tiling?  Tim Hutton  11/22/12 5:55 AM  And a glider gun! Very nice. On 22 November 2012 13:03, <katsuno...@gmail.com> wrote:
 Tim Hutton  http://www.sq3.org.uk  http://profiles.google.com/tim.hutton/ 
Re: gliders are impossible in Penrose tiling?  katsunobu.imai  11/22/12 7:48 PM  Yes. I have no idea of the possibility of a 2state glider. Bur anyway it turned out that Penrose tiling has little disadvantage for the existence of gliders. Katsunobu 
Re: gliders are impossible in Penrose tiling?  Tim Hutton  11/23/12 1:01 AM  Katsunobu, Are you aware of Alexander Vlasov's work? (CC'ing him.) There's a 3state penrose ant here: https://ayvlasov.wordpress.com/2012/09/27/penrosesants/ It works a bit differently, using the relative ordering of the neighbors. I think it's the same rule as here: https://ayvlasov.wordpress.com/2012/07/23/quants/ Perhaps the challenge now is to find a glider that doesn't travel along a De Bruijn ribbon!  
Re: gliders are impossible in Penrose tiling?  Adam P. Goucher  11/23/12 6:38 AM  > Yes, I'd like to see any glider having an almost straight orbit
> on a kite and dart PT. The P3 (rhombus) and P2 (kiteanddart) Penrose tilings are mutually locally derivable, which means that any cellular automaton on one of those tilings can be emulated (in a reasonably simple way) in a cellular automaton on the other. So, the Goucher, Imai and Tsukamoto Miyazaki gliders can be implemented on the P3 tiling if we allow sufficiently many states. I prefer the gliders on the P3 tiling which trace out fractal Koch curves, because there is provably no analogue in cellular automata on periodic tessellations. I believe that my paper is published in the Journal of Cellular Automata this month. Sincerely, Adam P. Goucher http://cp4space.wordpress.com/ 
Re: gliders are impossible in Penrose tiling?  katsunobu.imai  11/24/12 6:29 AM  Yes, I agree with you.
P3 and P2 can be converted with each other, but, ... So far it is not so clear but I feel it may be possible to find a kind of straight orbit pattern which is possible with a few (not so many) states, even in P2 case. Even it may finally turn out that the orbit is directly related to a ribbon of P3, I believe it is reasonable to try to figure out a simpler construction of a straight line in P2. Regards, Katsunobu 
Re: gliders are impossible in Penrose tiling?  qubeat  11/24/12 7:08 AM 
Adam,
Do you mean curves formed by big rhombs?
Anyway, P3 tilings may be considered as projection of some 2D faces of 5D
hypercubes lattice. So we may model cellular automata on the P3 tilings via
the 5D periodic lattice. If I am counting properly, P3 lattice with n states may
be modeled via the 5D lattice with N=(n+1)^10 states, where 10 is number of
2D faces of each hypercube and +1 is extra state to mark faces outside
of 2D plane in 5D space (the plane forming P3 tiling via intersection with
5D cubes  nodes of the cubes are vertexes of P3 lattice, eg de Bruijn 1981).
Sincerely
Alexander Vlasov 
Re: gliders are impossible in Penrose tiling?  Adam P. Goucher  11/24/12 7:34 AM  Sorry, I meant the gliders on the *P2 tiling* (kiteanddart), which
can follow either closed loops or unbounded curves with Hausdorff dimension log(6)/log(phi^3). I'm not sure whether or not these are MLD (mutually locally derivable) with the ribbons of thick rhombi on the P3 tiling, but I wouldn't be surprised if they turn out to be. There's a brief summary near the end of this article: http://cp4space.wordpress.com/2012/08/24/areyouready/ There are more details in the paper (attached). I've also sent this to someone who asked for a copy of the paper.

Re: gliders are impossible in Penrose tiling?  Alexander Yu. Vlasov  11/23/12 5:09 AM  Hi,
To be precise, it is not the same  in version with rectangular lattice only total numbers of live cells in closest and diagonal positions are used. It does not work with Penrose tile and so it is necessary also to take into account if two closest live cells are opposite or not. Yet it is appropriate condition for Penrose tile, but I do not know how to implement that with Ready. Alexander Vlasov 
Re: gliders are impossible in Penrose tiling?  katsunobu.imai  11/23/12 4:42 AM  Hi Tim, Is it a second order reversible CA on Penrose tiling? It is interesting if a switch gate can be realized by the CA (or a slightly modified version.)
Katsunobu 
Re: gliders are impossible in Penrose tiling?  alex.yu...@gmail.com  3/28/14 1:49 PM  Hello, Software used for creation of second order glider on Penrose tiling (with source code) should be now available here: (either free registration or OpenID are needed) The rule with 2x2=4 states is called "Ants" (rule Ants6 with 6 states, less noise and sped=1/2 is also included) I also included Adam Goucher and Katsunobu Imai gliders rules (uncheck "reversible" before run). Alexander 