Gliders in 4-neighbor semitotalistic 2D cellular automata
Ilmari Karonen
neighborhood is rather poorer than that for the 8-neighbor Moore
neighborhood, both in terms of size (there are only 512 essentially
different rules) and of asymptotic behavior.
Given that it's rather simple to prove that any 4-neighbor rule which
allows patterns of active cells to grow or move without bound must
result in any such pattern exploding quadratically, it seems difficult
to see how such rules could sustain gliders. In fact, they can't, not
unless one cheats a little.
The cheat is to consider rules which feature cell birth on 0 active
neighbors (and death on 4). In such rules, the background does not stay
inactive, but will alternate between inactive and active on successive
generations. If the rule is further chosen so that active cells can
(and must) expand on an inactive background but inactive cells can't do
so on an active background (or vice versa), then non-explosive growth
becomes possible.
There are further constraints which reduce the number of rules even
theoretically capable of supporting gliders down to just 32, and likely
even further. Of those rules, most still explode or don't grow at all.
Nonetheless, I've found at least two in which glider-like behavior is
possible and even emerges spontaneously.
In the 4-neighbor rule B024/S1 (that is, birth on 0, 2 or 4 active
neighbors, survival on 1) the following period 4 orthogonal c/2 glider
occasionally emerges (hash marks are active cells, periods inactive):
#..
#.#
Most starting patterns will explode in this rule, but the average growth
rate is not quite c/2, so gliders that form spontaneously can escape.
The rule also supports the following extended form of the glider:
..#..
#.#.#
The closely related rule B04/S1 is also interesting. It, too, typically
produces quadratic growth, but the growth rate is much lower. However,
if a pattern is allowed to grow, the following diagonal puffer will
often spontaneously emerge at its edge:
#.##.
..#..
.....
....#
This puffer moves much faster than patterns normally grow, so it will
rapidly escape its parent, leaving behind it a narrow, tapering "spike"
sticking out of the growing mass. It seems entirely possible that the
trail of this puffer could be stabilized, perhaps producing a diagonal
spaceship.
Ps. There is, of course, another way to extend the definition of a
glider in such a way as to potentially allow them in 4-neighbor rules.
That is to consider non-uniform backgrounds, i.e. ones consisting of
various stable (or even oscillating) periodic tilings of the grid. I've
yet to find any gliders on such backgrounds, although I find it likely
that they should exist.
--
Ilmari Karonen
George Maydwell
wrote:
>The set of outer totalistic CA rules in the 4-neighbor von Neumann
>neighborhood is rather poorer than that for the 8-neighbor Moore
>neighborhood, both in terms of size (there are only 512 essentially
>different rules) and of asymptotic behavior.
>
>Given that it's rather simple to prove that any 4-neighbor rule which
>allows patterns of active cells to grow or move without bound must
>result in any such pattern exploding quadratically, it seems difficult
>to see how such rules could sustain gliders. In fact, they can't, not
>unless one cheats a little.
>
>The cheat is to consider rules which feature cell birth on 0 active
>neighbors (and death on 4). In such rules, the background does not stay
>inactive, but will alternate between inactive and active on successive
>generations. If the rule is further chosen so that active cells can
>(and must) expand on an inactive background but inactive cells can't do
>so on an active background (or vice versa), then non-explosive growth
>becomes possible.
Neat. I never thought I'd see gliders in a four cell universe. Your
cheat leads to flashy demonstrations, as the quick and dirty java
simulations I've thrown together and referenced below demonstrate.
>
>There are further constraints which reduce the number of rules even
>theoretically capable of supporting gliders down to just 32, and likely
>even further. Of those rules, most still explode or don't grow at all.
>Nonetheless, I've found at least two in which glider-like behavior is
>possible and even emerges spontaneously.
>
>In the 4-neighbor rule B024/S1 (that is, birth on 0, 2 or 4 active
>neighbors, survival on 1) the following period 4 orthogonal c/2 glider
>occasionally emerges (hash marks are active cells, periods inactive):
>
> #..
> #.#
>
>Most starting patterns will explode in this rule, but the average growth
>rate is not quite c/2, so gliders that form spontaneously can escape.
>The rule also supports the following extended form of the glider:
>
> ..#..
> #.#.#
>
>The closely related rule B04/S1 is also interesting. It, too, typically
>produces quadratic growth, but the growth rate is much lower. However,
>if a pattern is allowed to grow, the following diagonal puffer will
>often spontaneously emerge at its edge:
>
> #.##.
> ..#..
> .....
> ....#
>
This is really neat too! Unlike other puffers which I have seen, this
one apparently explodes into an irregular shape. Let it run long
enough in a large enough universe (1600x1250) and it looks like a
wierd mutant turnip waiting to be garbage collected:
www.collidoscope.com/modernca/b04s1turnip.html
>This puffer moves much faster than patterns normally grow, so it will
>rapidly escape its parent, leaving behind it a narrow, tapering "spike"
>sticking out of the growing mass. It seems entirely possible that the
>trail of this puffer could be stabilized, perhaps producing a diagonal
>spaceship.
>
Here's a smaller (800x500) simulation which usually demonstrates
puffer emergence:
www.collidoscope.com/modernca/b04s1escape.html
>Ps. There is, of course, another way to extend the definition of a
>glider in such a way as to potentially allow them in 4-neighbor rules.
>That is to consider non-uniform backgrounds, i.e. ones consisting of
>various stable (or even oscillating) periodic tilings of the grid. I've
>yet to find any gliders on such backgrounds, although I find it likely
>that they should exist.
George Maydwell
--
Modern Cellular Automata: www.collidoscope.com/modernca
Collidoscope Hexagonal Screensaver: www.collidoscope.com
Brian Prentice
puffer running under MCell, you can download a DLL and example
patterns from here:
http://linuxenvy.com/cgi-bin/bprentice/DirIndex?MCell/WG4.zip
Frank Buss
The link doesn't work. I've downloaded it from this link:
http://linuxenvy.com/bprentice/MCell/WG4.zip
But you don't need a new DLL, because you can use "General binary". This
is your P001.mcl example (survival: 1, birth: 0 and 4):
#MCell 4.20
#GAME General binary
#RULE C0,NN,Sabbab3ab7a,Bb14ab
#BOARD 200x200
#CCOLORS 2
#L A.AA$..A$$4.A
and this is your S001.mcl example (survival: 1, birth: 0, 2 and 4):
#MCell 4.20
#GAME General binary
#RULE C0,NN,Sabbab3ab7a,Bbaababbaabbabaab
#BOARD 200x200
#CCOLORS 2
#L A29.A$A.A25.A.A.A
But it's easier with your DLL to configure the totalistic rules.
--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de