gliders are impossible in Penrose tiling?

Showing 1-38 of 38 messages
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 Life-like
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 5-fold rotational symmetry. There are
lots of shapes in Gray-Scott (in the U-skate parameters) that travel
indefinitely on a curved path and I think of these as "gliders".

Also, if you run reaction-diffusion on a Penrose mesh, then just like
any other type of mesh, most normal reaction-diffusion patterns should
be possible.

Here is a Java applet that simulates Gray-Scott 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 "U-skate" 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 U-skate to
work in Ready). I probably could have gotten it to work by adjusting
ru,rv,dt and using a finer grid (more "processors").

On 7/23/12, Andrew Trevorrow <and...@trevorrow.com> wrote:
> 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. [...]

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

> For penrose.vtu as it currently exists (a deterministic Life-like
> cellular automaton) I agree that a "glider" in the Life sense
> (something that travels indefinitely in a straight line) can't be
> done.

Yep, I was only thinking about a discrete CA.

> However you might be able to do a "glider" that travels in a circle
> around the (unique) point of 5-fold 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://www-users.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 N-state CA. In B3/S23 I
agree it is unlikely.

I think Robert's point about u-skate on an aperiodic tiling is
interesting. Any floating-point 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 u-skate 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:

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

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.

> We could probably engineer one in an N-state CA.

I'll happily pay $100 to the person who can do that!

> I think Robert's point about u-skate on an aperiodic tiling is
> interesting. Any floating-point 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 u-skate style glider in a discrete CA on a
> Penrose grid, even with only the Moore neighborhood.

Robert didn't actually get his u-skate 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 u-skate 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:
> Tim:
>
>> 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?
>
> 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.
>
>> We could probably engineer one in an N-state CA.
>
> I'll happily pay $100 to the person who can do that!

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
N-state (where N<1000) discrete CA that will travel an arbitrary
distance on a Penrose P3 tiling, with the Moore neighborhood
(vertex-neighbors)?" "Can you prove that no glider exists capable of
travelling an arbitrary distance on the B3/S23 2-state CA on a Penrose
P3 tiling, with the Moore neighborhood (vertex-neighbors)?"

>
>> I think Robert's point about u-skate on an aperiodic tiling is
>> interesting. Any floating-point 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 u-skate style glider in a discrete CA on a
>> Penrose grid, even with only the Moore neighborhood.
>
> Robert didn't actually get his u-skate 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 u-skate 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!

Attached Robert's u-skate working on a Penrose P3 tiling. It
eventually hits the side and dies because there's no wrap-around 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 (32-bit) and so would work with 32-bit
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:

> Attached Robert's u-skate working on a Penrose P3 tiling. It
> eventually hits the side and dies because there's no wrap-around in
> 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 5-state CA on a Penrose tiling!

All this happened in some off-list 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 U-skates 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 "U-shaped 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.0e-3. 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 U-shaped patterns
begin to be destroyed. The noise amplitude is brought back down to
1.0e-3 for a few seconds to show that the remaining U-shape is capable
of recovering."
  (from http://mrob.com/pub/comp/xmorphia/aux-movies-2.html which
includes several other demonstations of U-skate world phenomena and
some of my other tests; see also
http://mrob.com/pub/comp/xmorphia/uskate-world.html . The first page
of aux. videos, http://mrob.com/pub/comp/xmorphia/aux-movies.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 U-skate
attempts weren't working in Ready.

- Robert

Tim and Andrew wrote:
>>> I think Robert's point about u-skate on an aperiodic tiling is
>>> interesting. Any floating-point 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 u-skate style glider in a discrete CA on a
>>> Penrose grid, even with only the Moore neighborhood.
>>
>> Robert didn't actually get his u-skate 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 u-skate will eventually stop working
>> on an *infinite* aperiodic tiling, regardless of how fine the mesh.

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 floating-point 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 u-skate style glider in a discrete CA on a
> Penrose grid, even with only the Moore neighborhood.

Are 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 Turing-equivalent 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:
> Attached Robert's u-skate working on a Penrose P3 tiling. It
> eventually hits the side and dies because there's no wrap-around 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.

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 U-skate is
moving, other times not.

As with the random grids, systematic noise, etc. I suspect the U-skate
would be more stable if you used an even finer grid. Or as you put it
"as you zoom out" the grid becomes irrelevant.

> This is implemented in floats (32-bit) and so would work with 32-bit
> 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.

32-bit floats also have 4.3 billion states, n'est-ce pas? No integers needed.

Also, using OpenGL I discovered that Gray-Scott works just fine with
16-bit floats. I wasn't able to get U-skates 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:
> That was quick.  Adam P. Goucher has won the $100 prize with a glider
> in a 5-state 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 two-state 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.

On 26 July 2012 01:18, Andrew Trevorrow <and...@trevorrow.com> wrote:
> That was quick.  Adam P. Goucher has won the $100 prize with a glider
> in a 5-state CA on a Penrose tiling!
>
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/feature-column/fcarc-ribbons

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/quad-grid-glider.html

I don't see any way to join ycombinator . . . do I have to attempt an
anonymous comment first?

On 7/27/12, Tim Hutton <tim.h...@gmail.com> wrote:
> Some discussion of it going on here:
> http://news.ycombinator.com/item?id=4298515

Re: gliders are impossible in Penrose tiling? Tim Hutton 7/28/12 12:09 AM


On Jul 28, 2012 1:26 AM, "Robert Munafo" <mro...@gmail.com> wrote:
>
> 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/quad-grid-glider.html

Yes, good stuff.

>
> I don't see any way to join ycombinator . . . do I have to attempt an
> anonymous comment first?

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 place
> filled with quadrilaterals, although a greater restriction is required
> to ensure it doesn't follow a looping path:

Yes, 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/quad-grid-glider.html

This was similar to the thought processes I went through in designing
the glider. I had seen the head-tail 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 (-:

On 7/28/12, Adam P. Goucher <apgo...@gmx.com> wrote:
> Yes, 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.

Penrose glider article in New Scientist Adam P. Goucher 8/4/12 2:49 PM
http://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html

Hopefully this will re-invigorate interest in cellular automata on Penrose
tilings. I believe that the only pre-Ready 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 two-state Moore
neighbourhood rule on the Penrose tiling. There's probably no small
example akin to GoL's glider in the Owens-Stepney rule, since they
would have already found it by now. However, we have a vast
rule-space 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? katsunobu.imai 9/3/12 8:19 AM
Hi, 

These gliders are very impressive. Then I tried to find some other 
glider-like patterns. 

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 N-state CA. In B3/S23 I
agree it is unlikely.

 Generations CAs such as "Brian's Brain" seems to be candidates. 
In the case of normal CA, almost all patterns can be gliders in Brian's 
Brain. 

How do you think about this? 
This rule is S/B2/C4.
Re: gliders are impossible in Penrose tiling? Andrew Trevorrow 9/4/12 1:37 AM

> 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 self-replicating worms:
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/i/Imai:Katsunobu.html
Recently he published a paper on universal computation on a Penrose CA:
http://www.newscientist.com/article/dn22222-turing-machine-gives-order-to-chaotic-penrose-universe.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:

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.

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 life-like or generations CA. 

Attached is a Ready file that implements the same 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

On 2012/09/04, at 21:11, Katsunobu Imai <katsuno...@gmail.com> wrote:
>
> But in the case of Kite and Dart, it seems to be quite difficult for me
> to find a glider in the case of life-like or generations CA.

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? katsunobu.imai 11/22/12 5:03 AM
Hi again, 

Recently Tsukamoto & Miyazaki reduced the number of states to 3. 

Because the construction is quite similar to the Goucher's glider, the same 
rule seems to be also effective in the case of kite & dart. 


2012年7月26日木曜日 20時21分27秒 UTC+9 Tim Hutton:
As a minor modification, the number of states can be reduced to 4. Attached.

On 26 July 2012 01:18, Andrew Trevorrow <and...@trevorrow.com> wrote:
> That was quick.  Adam P. Goucher has won the $100 prize with a glider
> in a 5-state CA on a Penrose tiling!
>
> All this happened in some off-list 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



--
Tim Hutton - http://www.sq3.org.uk - http://profiles.google.com/tim.hutton/
Re: gliders are impossible in Penrose tiling? Tim Hutton 11/22/12 5:55 AM
And a glider gun! Very nice.
Re: gliders are impossible in Penrose tiling? katsunobu.imai 11/22/12 7:48 PM

On 2012/11/22, at 22:54, Tim Hutton <tim.h...@gmail.com> wrote:

> And a glider gun! Very nice.

Yes.

I have no idea of the possibility of a 2-state 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 3-state penrose ant here:
https://ayvlasov.wordpress.com/2012/09/27/penroses-ants/
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/qu-ants/

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 (kite-and-dart) 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

On Friday, November 23, 2012 6:38:36 PM UTC+4, Adam P. Goucher wrote:
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.
 
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* (kite-and-dart), 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/are-you-ready/

There are more details in the paper (attached). I've also sent this
to someone who asked for a copy of the paper.



Sincerely,


Adam P. Goucher

http://cp4space.wordpress.com



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



Yes, I'd like to see any glider having an almost straight orbit 
on a kite and dart PT. 

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
More topics »