Subject: Experiments with a somewhat "Life-like" hexagonal CA (long)
By Paul Callahan (3 Dec 97)
Introduction
------------
Occasionally the question comes up of whether there is a 2-state CA that
runs on a hexagonal grid and works something like Conway's Game of Life.
I've never seen any detailed discussion of a particular rule, though
I had heard rumors that there is one with gliders. I decided to look for
such a rule, partly to satisfy my own curiosity and partly to
test the generality of some software tools I've been working on.
(After working on this for a while, I found out that some rules had
been found by Robert Andreen with some similar properties).
After settling on one rule, which I'll describe below, I was able to
duplicate many of the properties associated with Life, including the
ones needed to embed digital logic. A number of growth-rate results and
oscillator-construction methods should also transfer to this rule.
In fact, I was surprised at the variety of interesting patterns and
reactions, some of which actually lead to simpler constructions than
in Life. The rule is tamer than Life in that small patterns
usually stabilize very fast.
I'm fairly certain that there is no totalistic rule on a hex grid that supports
the variety of interesting reactions found in Life, because if there were
it would be better known. In any case, I checked briefly and
found nothing promising. In particular B3/S23 (birth on three live neighbors,
survival on 2 or 3, like Life) settles down very fast and doesn't seem
likely to have spaceships. Birth on 2 neighbors is useful, because an
axis-parallel front of 3 neighbors cannot occur in a hex grid. However,
always having birth on 2 neighbors seems likely to cause uncontrolled growth.
The Rule
--------
With that in mind, I started playing around with rules based on
different-shaped neighborhoods, but insisting on symmetry. Taking symmetries
into account, there are three ways each of getting 2, 3, and 4 neighbors,
for a total of 13 different neighborhoods. I tried a lot of variations, but
the one I settled on only distinguishes between different ways of getting two
neighbors. For these, one can use the organic chemists' naming convention
for benzene-ring disubstitutions: ortho, meta, and para. Rich Schroeppel and
Achim Flammenkamp suggested this, and it may be a useful mnemonic for some
people. It has the disadvantage that there is no standard extension to
subsets of 3 or 4 neighbors. Fortunately, we don't need this for the rule
used here. So let's call these neighborhoods 2o, 2m, and 2p
as follows:
O O O . O .
2o: . x . 2m: . x O 2p: . x .
. . . . . O
Extending the birth/survival convention used above, the rule is B2o/S2m34.
That is, we always have survival but not birth on 3 or 4 neighbors. On
two neighbors we have birth but not survival if the neighbors are adjacent (2o),
and survival but not birth if there is one empty neighbor cell in between (2m).
If they are opposite each other (2p), there is no birth or survival (which
is also the case for 0, 1, 5, or 6 neighbors).
I settled on these rules in order to get a glider. It uses the only really
small mechanism I'm aware of. I consider it crucial that gliders show
up spontaneously from random starting states.
. . O .
. . . O
O . . O
. . . O
. . . O
The spark on the left appears every other generation. This is a period-4
glider with two distinct shapes, much like the glider in Life.
(Robert Andreen, and probably others as well, have looked at rules that
support this glider.)
Variations
----------
You can vary the rule for 2p. If you have birth but not survival, the
same glider works (other factors made this variation less interesting
to me). If you have birth and survival on 2p and death on 4 (this
can be relaxed somewhat) you get two distinct sparky gliders
that propagate at the same speed but higher periods (6 and 8).
The following discussion, however, will be limited to B2o/S2m34.
This rule is interesting because it doesn't seem to grow explosively
but it does have a number of natural high-period oscillators. It also has
a fairly common (i.e. observable in nature) infinite-growth pattern.
Initial finds
-------------
Patterns usually settle down much faster than in Life. The kinds of
things that remain are either little and isolated, or clumped into honey-comb
patterns. The latter are very stable, and seem to act as anchors
for oscillators (mostly low-period blinkers on the fringes, but
interesting high-period sparkers as well). There are a number of
reactions--similar to the "kickback" in Life--in which two gliders collide
to produce a new glider on a different path. Unlike Life, one glider
can also destroy another without being affected.
The first thing I really liked about this rule was the following period-48
spaceship (it flips after 24 moves and moves down one position).
O . O . . . .
. O O . . . .
. O O O . O .
. . O O . . O
. . . O . . .
It's fairly easy to observe by trying random starting states, though
not nearly as common as the glider. It's very sparky, and I subsequently
found a number of glider reflections as well as a glider duplication
reaction. I'll explain these in a later section.
Infinite growth is an easier question to answer here than in Life,
because there is a stalk that leaves a trail of double honey-combs behind it.
It shows up often enough to notice--maybe as often as the replicator in
HighLife--but not so much as to dominate the dynamics of random patterns.
This one is propagating down.
O . O O . . . . . . .
. O O . O . . . . . .
O O . O O . . . . . .
. . O O . O . . . . .
. . O . O O . . . . .
. . . O O . O . . . .
. . . O . O O . . . .
. . . O O O . O . . .
. . . . . . O O . . .
. . . . . . O . O . .
. . . . . . O O O . .
. . . . . . . . O O O
This structure (and others like it) are extremely stable. I can think
of some intuitive reasons for why this is so, but I haven't considered
the issue carefully. The practical implication is that unlike analogous
Life patterns, there is no clear way to "ignite" the trail left
behind by this pattern. So far, I have not found any kind of damage
that propagates far along these stalks.
Note: gliders cannot propagate down (270 degrees) but are limited
to 0, 60, 120, 180, 240 degrees. Clearly, this affects the kinds of
constructions we can build out of spaceship/glider interactions.
Some natural oscillators and a period-15 spaceship
--------------------------------------------------
There were a lot of oscillators that appeared in random testing, so I ran
a program to test 10x10 (rhombic) random starting states for new ones. I'll
summarize all the periods later. One very useful early find has period 42.
This is its smallest state.
. O O . . .
. O . O . .
O O O O . .
O . . . O .
. O O O O O
. . . O . .
. . . O . .
This can reflect gliders by 180 degrees and 120 degrees. Two can be combined
to make a 60-degree reflector. Loops of recirculating glider
streams can be built out of these.
High-period oscillators in this rule have a different feel from
Life oscillators. One of the weirdest ones is period 66 and seems
to extend and retract a tentacle (which is big and temporarily looks
like a permanent, stable part of the oscillator).
Compact form:
. . O O .
O O O . O .
O . O . O .
. O O . O O .
. O . O O . O . O .
. . . . . O O . O O O .
. . . . . . . O O .
40 steps later with "tentacle" extended to the left.
. . . . O .
. . O . . O . O O .
O O O . . . O O . O .
. . O . . . . O . O .
. . O . . . . O . O O .
. . . O O . O O O O . O . O .
. . . . . O O . O . O O . O O O .
. . . . . . . . . . . . O O .
. . . . . . . . . . . . . O .
There are many other natural oscillators, which I'll list later on. One
especially nice one is this period-42:
. . O O .
. O O O .
. . . O .
O O O O .
O O .
Unlike the period-42 oscillator shown earlier, this one rotates 60 degrees
every 7 steps. So far, its spark does not seem as versatile as that
of the earlier one, but there is probably a use for it.
Finally, there is another spaceship that comes up in random searching, though
it is much less common than the period-48. It's symmetric and moves in
glider directions one position every 15 steps:
. O . O . . . . .
. . O O O . . . .
O O O . O . . . .
. . O . O . . . .
. . . O O . . . .
. . . . . . . . .
. . . . O O . . .
. . . . O . O . .
. . . O O O . O .
. . . . . . O O O
. . . . . . O . O
The one shown above moves to the left.
Larger constructions: A Glider Gun
----------------------------------
Three of the period-42 oscillators can be combined to make a glider gun.
I found this by first pairing up oscillators and testing the results. This
didn't yield a glider gun, but it yielded a pair with a larger
spark, to which I added the third:
. . . . . . . . . . . . O O .
. . . . . . . . . . . . O .
. . . . . . . . . . . . O . . . . O O .
. . O . . . . . . . . . O . . . . . O O . O .
. O O . O . . . . . . . . . . O . . O . O O .
O O . O O O . . . . . . . . . . . . . O O . O O .
. . O . O . O . . . . . . . . . . . . . O . O .
. . O O . O O O O . . . O O . . . . . . O . O O .
. . O . O O . O . . . . . O O O . . . . O O O . O .
. . . . . . . . . . . . . O . O . . . . . . O .
. . . . . . . . . . . . O O O O .
. . . . . . . . . . . . O . . . O .
. . . . . . . . . . . . . O O O O O .
. . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . O .
It seems likely that almost all of the complex constructions that work
in Life can be realized under these rules, the main difference being the
relatively rarity of sustained explosions (certainly nothing on the
order of the R-pentomino of Life, let alone the less common Methusalehs
such as rabbits or the acorn). In fact, a very common result of a glider
colliding with anything is to kill the glider without damaging the object
it hits. For example, this very common 3-cell period-2 oscillator
. O
O O .
acts as an eater much of the time. A honey-comb wall (as produced
by the stalk) can also eat gliders.
Representation of Patterns
--------------------------
So far, pictures have sufficed to give an idea of this rule, but
I hope at least a few people will try to run these patterns on their
own CA programs. The format for electronic distribution is unfortunately
less standardized than Life or other 2-state CAs on a cartesian grid.
The obvious way to emulate a hexagonal grid is to use the Moore neighborhood
omitting two opposite diagonal corners, which is what I did. But
we have to agree on which corners. I chose the northeast and southwest
corners for removal. So the embedding is given by the following
transformation:
ABC A B C
DEF -> D E F
GHI G H I
The cell E has cells A, B, D, F, H, and I, but not C or G, as its neighbors.
Following this convention, all the patterns I will post here can be run
on a sufficiently general Moore-neighborhood CA simulator. In fact, the
patterns above can all be converted back to a rectangular grid just by
deleting the white space. The actual spacing in the cartesian grid is given
by the dots. I will adhere to this convention for all pictures. For
larger patterns, I will use run-length encoding as described in David Bell's
recent posting. These patterns encode cells on a cartesian grid with the
neighborhood defined above. At the risk of annoying people who are against
posting code, but at least guaranteeing that anyone with a copy of this
article can decode the patterns, here is a short perl program to convert
these patterns to a list of cell coordinates:
#!/usr/local/bin/perl4
$x=0; $y=0;
findpat:
while(<>) {
last findpat if (/x *= *[0-9]+ *, *y *= *[0-9]+/);
}
main:
while(<>) {
while ( /([0-9]*)([bo\$])(.*)/ ) {
if ($1 eq "") { $count = 1; }
else { $count = $1; }
if ($2 eq "b") { $x+=$count; }
elsif ($2 eq "\$") { $x=0; $y+=$count; }
else {
for ($i=0; $i<$count; $i++) {
print $x++, " ", $y, "\n";
}
}
$_ = $3;
}
last main if (/\!/);
}
Again, we have to agree on conventions. The cells are listed by
horizontal (x), then vertical (y) coordinate. Vertical increases from
top to bottom. For example, the cells A, C, and I above would be listed
as "0 0", "2 0", and "0 2", respectively.
Glider Reflections
------------------
There are many ways of reflecting gliders both from stationary oscillators
and moving spaceships. I won't try to list the 180-degree reflections
exhaustively, since there are so many. I will include some of them in
the larger patterns. So far, I have found one way of turning a glider
60 degrees and four ways of turning one 120 degrees. I haven't tried all
the high-period oscillators, so there may be others as well. It's
especially interesting that the period-48 spaceship can reflect gliders,
because gliders move fast enough that they can circulate around a flotilla
of moving objects in this way. Here are the three non-180-degree spaceship
reflections:
Glider is reflected 60 degrees, traveling up:
. . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . O . . O .
O O O O . . . . . . . . . . O .
O . . O . . . . . . . . . . . O .
. O O O .
. O O .
Glider is reflected 120 degrees, traveling to the right:
. . O .
O .
. O .
. . O .
. . . O O .
.
.
. O O .
. . O .
. . . O .
. . . O . O .
. . . . O . O .
. . O O O . O .
. O O O O . O O .
. . . . O . O .
. . . . O .
Glider is reflected 120 degrees, traveling up:
. . . . . . . . O .
. . . . . . O .
. . . . . . . O .
. . . . . . . . O .
. . . . . . . . . O O .
.
.
.
O O .
. O .
. . O .
. . O .
. . O .
. O O O O O .
. . . . O .
. . . . O .
In the above three examples, the spaceship is traveling down. Thus,
the two distinct 120-degree reflections are not interchangeable.
Here are two more 120 degree reflections with stationary oscillators.
In both cases, the reflected glider travels to the right.
Period-20:
. . O .
O .
. O .
. . O .
. . . O O .
.
.
.
.
. . . . O O O .
. . . . . . O O .
. . . . . . O . O .
. . . . . . . O O .
. . . . . . . O . O .
. . . . . . . . O O .
. . . . . . . . O .
. . . . . . . . . O .
. . . . . . . . . O .
. . . . . . . O O O O .
. . . . . . . . . O . O .
. . . . . . . . . . O .
Period-42:
. . O .
O .
. O .
. . O .
. . . O O .
.
.
.
. . . . O .
. . . . . O O .
. . . . O O O O .
. . . . . . O O O .
. . . . . . O . O .
. . . . . . . O O O O .
. . . . . . . O . . . O .
. . . . . . . O O O O O .
. . . . . . . . . . O .
. . . . . . . . . . . O .
Finally, these can be used to send gliders in a loop. First, here's one
based on period-42 reflectors:
x = 89, y = 89
29bo$30b2o$5bo22b3ob3o$4bobo23bobo2bo$5b4o21bob4o7bobo$4b2o3bo20b3obob
o5bob2obo$6b4o23b2o8b2ob2o$5b2obobo22bo9bobobo$7b5o32b3obo$10bo30bo3bo
b2o$38b4o3b3o$47bo$2b2o5bo19bo$2bob2o4bo19bo$b2obo5bo17bo2bo$2ob3o4bo
21bo$2bobobo3bo21bo$2b2ob2o$2bob2obo$5bo8$12b4o$16bo41bo11bo$61bo9bobo
$14bo46bo7b5o$61bo8bo3bo$60b2o9b4o$70b2obobo$72b3obo$75b2o$75bo2$72bo$
73bo$4b2o68bo$2b3ob3o66b2o$4bobobo72bo$3b2ob4o70b2obo$5b2obo71bob2o$5b
ob2o70b4ob2o$7bo72bobobo$12b2o66b3ob3o$14bo68b2o$15bo$16bo2$13bo$12b2o
$12bob3o$13bobob2o$14b4o9b2o$14bo3bo8bo$15b5o7bo46bo$15bobo9bo$18bo11b
o41bo$73b4o8$83bo$81bob2obo$82b2ob2o$56bo21bo3bobobo$56bo21bo4b3ob2o$
57bo2bo17bo5bob2o$58bo19bo4b2obo$59bo19bo5b2o$41bo$41b3o3b4o$40b2obo3b
o30bo$40bob3o32b5o$41bobobo9bo22bobob2o$41b2ob2o8b2o23b4o$41bob2obo5bo
bob3o20bo3b2o$43bobo7b4obo21b4o$53bo2bobo23bobo$54b3ob3o22bo$57b2o$59b
o!
Here's one that was considerably harder to set up, but shows that a
glider can be sent in a loop around a moving spaceship flotilla:
x = 270, y = 51
17bo$17bobobo$17bo3b2o$20b2o$20bo$3bobo14b2o$3b4o13bob2o$4bo2bo12bo2bo
$5bobo15bo$5b4o$5bo2$o$obobo13bo$o3b2o12b3o$3b2o13bo2bo$3bo13b3ob2o$3b
2o15b2o$3bob2o14b2o$3bo2bo$6bo74bo$81bo$81bo2bo$81bo$82bo5$31b3o7b3o$
30b2o2bo5b3o2b2o219bo$31bo11bo222bobo$31b3o10bob2o220bo$31bobo10bo220b
2o$34bo232bobo$268b2o$268b2o$268bo5$12bo3$16b4o$15b2o$15b5o2$20bo$20bo
bo!
I found only two reflections by the period-15 spaceship, and both
are 180-degrees. These are not as useful as they would be if the
glider was traveling in the same direction as the spaceship. Maybe
someone else can think of a use:
. O .
O . O O O O .
. O O . O O O . . . . O .
. . O . . . O . . O .
. . O . . . O O . . O .
. . . . . . . . . . . O .
. . . O . . . O O . . . O O .
. . . . O . . . O .
. . . . O O . O O O .
. . . . O . O O O O .
. . . . . . O .
. . O .
. . O O O .
O O O . O O .
. . O . . O O .
. . . O . O O . . . . . O .
. . . . . . . . . . O .
. . . . O . O O . . . O .
. . . . O . . O O . . . O .
. . . O O O . O O . . . . O O .
. . . . . . O O O .
. . . . . . . O .
Glider duplication
------------------
While doing collision enumerations to find reflections, I stumbled across
a very surprising reaction between a glider and a spaceship:
O .
. . . O .
. . . O .
. . . O .
. . O O .
.
.
. O O .
. O O .
. O . O .
O O . . O .
. O O O O O O .
. . . O . O .
. . . . O .
What happens here is that the glider interferes with the spaceship without
destroying either of them. The result is a large spark that is very
similar to an escaping glider, but has an extra cell that soon causes it
to vanish. I've seen nothing similar in Life, where it's very hard to get any
effect out of a glider without destroying it in the process. In fact, there
are several ways of placing a second spaceship so that the spark becomes
an escaping glider, resulting in a glider duplication that leaves one
glider undisturbed. With this, we can convert the moving glider loop
into a rake, albeit a large one with a slow growth constant:
x = 270, y = 51
17bo$17bobobo$17bo3b2o$20b2o$20bo$3bobo14b2o$3b4o13bob2o$4bo2bo12bo2bo
$5bobo15bo$5b4o$5bo$50bo3bo$o50b2o2bo$obobo13bo33bobobo$o3b2o12b3o30b
3o2b2o$3b2o13bo2bo32b3o$3bo13b3ob2o$3b2o15b2o$3bob2o14b2o$3bo2bo$6bo
74bo$81bo$81bo2bo$81bo$60bo21bo$60bo5bo$62bo2bo$63b3o$63b2o$31b3o7b3o
19b3o$30b2o2bo5b3o2b2o16bo2bo199bo$31bo11bo21bob2o197bobo$31b3o10bob2o
20bo199bo$31bobo10bo220b2o$34bo232bobo$268b2o$268b2o$268bo5$12bo3$16b
4o$15b2o$15b5o2$20bo$20bobo!
Glider duplications also exist for some stationary oscillators. It's
likely that they are quite common and would be an important part of
the toolkit for anyone building designing large patterns in this rule.
Period-42:
. . . . . . . . . . . . O . O .
. . . . O . . . . . . . . O O . O .
. . . . . . . . . . . O O O . O O .
. . . . . . . . O . . . O . O . O .
. . . . . O O O O . . . O O O O . O .
. . . . . . . . . . . . . . O . O O O .
. . . . . . . . . . . . . . . . . O .
O O . O O O .
O . O O O O O O .
. O . O . O O .
O O O . O O . O .
. . . O O .
. . . . O .
Period-20:
. . O . . . . . . . O .
. . . . . O . . O O O O .
. . . . . O . . . O O . O O O .
. . . . . O . . . . . O O . O .
. O . . O O . . . . . . . O O .
O . O . . . . . . . . . . . . O O .
. . . O . . . . . . . . . . . . . O O O .
. O . O . . . . . . . . . . . . . . O .
. . O . O . . . . . . . . . . . . . O O O .
. . . O O . . . . . . . . . . . . . O .
. . . O . O .
. . . . O O .
. . . . . . O .
. . . . . . O .
. . . . . . . O . O .
. . . . . . O O O O .
. . . . . . . . . O .
. . . . . . . . . . O .
Here's a period-210 gun built by inserting a p42 glider duplication into
a period-210 glider relay consisting of two 180-degree reflectors:
x = 69, y = 26
49bo$50bo$48b5o$49bo3bo$50b4o$50bobobo$51bob3o$50b2obo$52bo10b2o$2bo
50b2o6b3ob3o$b2o45b4o2bo2bo4bobobo$2b2o44bo9bo4b3obo$3ob2o50bo2bo3bo2b
3o$bob4o53bobo2b2o$2bobobo53bob4o$2b2ob3o58bo$2bob2o$56bo$54bobo$53b4o
$54bobobo$55b6o$54b2o3bo$56b4o$56bobo$58bo!
The period-20 duplication can be used to make a compact high-period gun by
sending a period-42 stream through it. The duplication only occurs once
every 420 steps, and in other cases, the glider either passes through or
gets destroyed without hurting the period-20 oscillators. Shown below is a
period-840 gun that illustrates two other reactions as well, namely the
3-cell glider eater, used here to get rid of gliders that pass through,
and a period-8 oscillator that thins period-4n streams down to period-8n
streams:
. . . . O .
. . . O . O .
. . . . O O O O .
. . . . . O .
. . . . . O .
. . . . . . O .
. . . . O O O .
. . . . . O . O .
. . . . . O O O . . . . . O O .
O O . . . . . O O . . . . O .
. O . . . . . . O . . . . . . . . . . . . . . O .
. O O . . . . . . . . . . . . . . . . . . O O O .
. . O . . . . . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . . . . . . O O .
. . . . . . . . . . . . . . . . . . . . . . O O . O .
. . O . . . . . . . . . . . . . . . . . . O O .
. . O . . . . . . . . . . . . . . . . . O O . O .
. . O . . O . . . . . . . . . . . . . . O . O O O .
. . O . . . . . . . . . . . . . . . . . . O O .
. . . O . . . . . . . . O O . . . . . . . . O .
. . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . O .
. . . . . . . . . . O O . . O .
. . . . . . . . . O O O .
. . . . . . . . O O . O . . . . . . . . . . . O . . . O O .
. . . . . . . . O . O O O . . . . . . . . . . . O O O O . O .
. . . . . . . . . O . O . . . . . . . . . . . O O O . O . O .
. . . . . . . . . O O . O O . . . O O O . . . . . . O O . O O .
. . . . . . . . . O . O O . . . . . . O O O . . . . . . O O . O .
. . . . . . . . . . . O . . . . . . . O . O . . . . . . . O .
. . . . . . . . . . . . . . . . . . . . O O O O O .
. . . . . . . . . . . . . . . . . . . O O . . . O .
. . . . . . . . . . . . . . . . . . . . . O O O O O .
. . . . . . . . . . . . . . . . . . . . . O . O .
. . . . . . . . . . . . . . . . . . . . . . . . O .
The glider to the left is the one that escapes. It is just below the
period-8 filter. The one headed 60 degrees above horizontal passes
through the duplication device, triggering the duplication.
Spaceship factories
-------------------
Spaceships are a lot more interesting when they can be produced on demand.
Just as in Life, there are ways to synthesize these from gliders.
Here's a three-glider synthesis of the period-48 spaceship:
. . . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . . O . O .
O O . . . . . . . . . . O O O O . . . . O . O .
. . O . . . . . . . . . O . . . . . . . . O .
. . . O .
. . . . O . . . . . . . . . . . O .
. . O .
There is also a two-glider collision that can be sparked in various
ways to produce this spaceship. This results in a more compact
spaceship factory:
x = 36, y = 93
10bo$11bo$11b4o$11bobo$14bo$14bo$15b3o$8bo6bobo$2bo5bo7b3o$3o6bo15bo$
2bo21b3o$b3o21bob3o$4b2o12bo7bobo$6b2o9bo7b3ob2o$5b2ob2obo14bob2o$7b2o
b2o14b3obo$7bobo2b2o14bo$9b3o$11bo2$30bo$17bo13b2o$5bo9bo13b3ob2o$4b5o
7bo6b4o2bobobo$5bobobo7bo5bo6b2ob3o$6b4o8b2o10bob2o$6bo3bo16bo$6b5o13b
2o$9bobo12bobo$10bo14b4o$25bo3bo$25b5o$28bo$29bo6$15b4o$19bo2$17bo22$b
o$obo3bo$b4ob2o$2bo2b2ob3o$2bo4b2obo$9b3o13b2o$11b2o11b2ob3o$22b3obobo
$23bo2b2ob2o$17bo5b4ob2o$8b2o7bo6b5o$8bo8bo2bo5bo$17bo$18bo$25b2o$26bo
bo$17b3o5bo3b2obo$16b2o13b2o$11bo3b2o3bo3bo4b3ob2o$11bo2b2ob3o4b2o2b2o
bobo$10b5ob2o8bo3b2ob2o$13bo11bob2obob2obo$14bo8b3obo5bo$24bobobo$25b
4o$25bo3bo$26b5o$28bo$29bo!
I haven't looked for a synthesis of the period-15 spaceship. Since it
is symmetric, the most likely approach would be to try to synthesize
half of it and fit the two halves together.
One use of these spaceship factories would be a "standing breeder"
like the one built in Life by Dean Hickerson. That is, it should be
possible to generate a set of spaceship streams through which a glider stream
can be sent on a zig-zag path. If this path intersects a stream of
glider duplication flotillas, then each such reaction point would
be a source of linear growth, resulting in quadratic growth overall.
The standing breeder could also be used to realize other growth rates,
since it converts any f(n)-growth stream of gliders into an O(n f(n)) breeder.
I haven't built such a pattern--so far, anyway. There is a simpler way to
get quadratic growth, which I'll explain in the next section.
Quadratic Growth: The Stalk Breeder
-----------------------------------
The stalk is common enough that it seemed likely that there was a
simple way to synthesize it. As with the period-48 spaceship, there
are several. Here's one using 3 gliders:
O .
. . . O .
. . . O .
. . . O .
. . O O .
.
.
.
.
.
. . . . . O .
. . . . O . O .
. . . . . O . O .
. . . . . . . O .
. . . . . . . . O . . . . O .
. . . . . . . . . . . . . O .
. . . . . . . . . . . . . O . . O .
. . . . . . . . . . . . . O .
. . . . . . . . . . . . . . O .
Since the stalk is a linear growth pattern, a reasonable way to get
quadratic growth would be to reproduce this collision again and again
using a moving pattern. I've already presented a rake that should work
for this purpose. The problem is not quite this simple, because one must
make sure that the rake does not collide with the growing stalks, something
that would almost certainly happen with any three-rake construction to
reproduce the above synthesis. A different stalk synthesis turns out to be
more useful for building a breeder:
. . . . . . . . . . O .
. . . . . . . . . . O .
. . O . . . . . . . . O . . O .
. . . O O . . . . . . . O .
. . . . . . . . . . . . . O .
.
.
O O .
. . O .
. . . O .
. . . . O .
. . O .
This combines two gliders with the 3-cell period-2 oscillator that
we've seen already as an eater. The synthesis is dirtier than the
first, but eventually results in a stalk. The glider duplication
reaction can be modified to produce the 3-cell eater instead of a glider,
giving us a puffer for these objects. The glider entering from the right
is not coming in a direction that we can produce with the rake given earlier,
so we need to add two extra spaceships as reflectors.
That's all there is to this pattern, though it takes up a lot of space:
x = 413, y = 328
396b2o$397bo$398bo$398bobo$399bobo$397b3obo$396b4ob2o$399bobo$15bo383b
o2$15b2o$17bo$17bo2bo$16bobobo$16b3obo$16bobobo$16bobo$19bo6$391bo$
392b2o$394bo$393bobo$394bo31$2o$o$o$bobo$b5o$3bo$4bo22$273bo2$274b2o$
274bo$274bobo$274bobo$275b3o$276bobo$276bo23$131bo$131bobo$133bo$132b
2o$132bo42$214bo$214bo$206bo8bo2bo$207b2o7bo$217bo3$204b2o$206bo$207bo
$208bo$206bo4$373bo2$373b2o$375bo$374bobo$375bobo$375b3o$375bobo$378bo
11$372b3o$373bob2o12bo$372b2o2bo$373b4o12b2o$376bo14bo$377bo12bobo$
391bobo$391b3o$391bobo$230b4o160bo$231bo2bo$232b3o$219b2o13b2o$221bo$
222bo$220bobo$219b5o$222bo$222bo4$365b2o$366bo$367bo19b2o$367bo20bo$
367bo20bo$366b5o16bobo$369bo17bobo$369bo18bob3o$262bo125b2ob4o$390bobo
$240bo21b2o129bo$264bo$241b2o20bobo112bo$241bo22bobo110bobo$239bo2bo
21b3o112bo$240bobobo19bobo109b2o2bo$241bob3o21bo109b3o$242bobobo131bob
2o11bo$245bobo118bo11bo13b4o$245bo120bobo24bob2o$367bo25b4o$269bo97bo
2b2o25bo$269bo99b3o$266bo2bo98b2obo$267bo104bo$266b4o$268bobo$253b4o
12bobo2bo$253bo2bo18bo$254b3o19bo2bo97b2o$254b2o23bo98bo$278b4o97bo$
278bobo98bo$278bobo98bo$217bobo158b5o$218b2o161bo$216bob3o160bo$203b2o
11bo2b2o58bo$204b2o14bo$204bobo72b2o$204bo2b2o72bo$203b6o71bobo$205bob
o73bobo$207bo73b3o$281bobo$284bo$408b2o$410bo$411bo$409bobo$408b5o$
411bo$411bo2$266bo$267b2o$269bo$269bo$247b3o19bo$248bob2o15b3o$228b2o
17b2o2bo15bobo$230bo17b4o18bo$231bo19bo$229bobo20bo$228b5o$231bo$231bo
$248b2o$249bo$248bobo$247bo2bo2bo$240bo7bo2b4o$240bobo6bo2bo2bo$239bo
2bo10bo10b2o$239bo14bo10bo$239b4o5bo16bobo$240bo2bo7bo11bo2bo2bo$240bo
10bo11b4o2bo$251bo11bo2bo2bo$250b2o14bo$266bo7$264b3o$265bob2o$264b2o
2bo$265b4o$268bo$269bo9$250bo$251b2o$251b3o$250bo$251bo2bo$251b6o$254b
o$255bo!
There is probably a much smaller quadratic growth pattern. A more
compact puffer would be a big step in this direction.
Other guns
----------
The period-20 oscillator actually yields a compact period-20 gun. Two
combined produce a spark that is almost a glider: all that is
needed to fix it is the 3-cell eater:
. . . . . . . . O O .
. . . . . . . . O .
.
. . . . . O O O O O O .
. . . . . O .
. . O . . . . . O .
. O O O O O .
. . O . O O . . . . . . . . O .
. . . O O . . . . . . . . O O O . . . . O .
. . O O . . . . . . . . . O O . O O . . O .
O O O . . . . . . . . . . . . O O . O O O O .
. . O . . . . . . . . . . . . . . O . . O . O .
. O O O . . . . . . . . . . . . . . . . . O .
. . . . O .
If we use a period-25 spark instead of the 3-cell eater, we can increase
the period to 100. Combining this with the period-8 filter, we get
a small period-200 gun:
. . . . . O .
. . . . . . O O O .
. . . . . . . O .
. . . . . . . O O O .
. . . O . . O O .
. . O O . O O .
O . O . O O .
. O O O . O O .
. . . . O O . O . . . . . . . . . . . O .
. . . . . . O O O O . . . . . . . O O O .
. . . . . . . . O . . . . . . . . . . O .
. . . . . . . . . O . . . . . . . . . O O .
. . . . . . . . . . . . . . . . . . O O . O .
. . . . . . . . . . . . . . . . . O O .
. . . . . . . . . . . . . . . . O O . O O .
. . . . . O . . . . . . . . O O O . O O .
. . . . . . O . . . . . . . . . O O O . O .
. . . . . . O . O . . . . . . . O . . O .
. . . . . . . O . O .
. . . . . . . . O . . . . . O O .
. . . . . . . O . . . . . O O O .
. . . . . . . . . . . . . O O O .
. . . . . . . . O . . . . . O . O .
. . . . . . . . O O . . . . . O O .
. . . . . . . . O . O . . . . O . O .
. . . . . . . . . . . . . . . O O O .
. . . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . . O . O .
. . . . . . . . . . . . . . . . . . O O O O .
. . . . . . . . . . . . . . . . . . . . . O .
. . . . . . . . . . . . . . . . . . . . . . O .
There is a period-43 oscillation that shows up occasionally, though it
is not nearly as common as period-42 or period-20. Technically, it's part of
a period-86 oscillator, because the patterns that realize this period have
some period-2 cells. These can also be used to build a glider gun, which
is interesting since it produces an odd-period (in fact prime-period)
glider stream as output:
. . . . . . . . . . . O O .
O O . . . . . . . . . . . O . O .
. . O . O . . . . . . . . O O O .
. . O O O . . . . . . . . O . O .
. . O . O . . . . . . . . . O O O O .
. . . O O O . . . . . . . . O . . O .
. . O O . . O . . . . . . . O O O O O .
. . . . O O O . . . . . . . . O O .
. . . . O O . O . . . . . . . . O .
. . . . O . O O .
. . O . . O . O .
. O O O . . O O .
O . . . . . O .
.
.
.
.
.
.
.
.
. . . . . . . . . . . . . . . . . . O . . O .
. . . . . . . . . . . . . . . . . . . O O O .
. . . . . . . . . . . . . . . . . . . . O . O O O .
. . . . . . . . . . . . . . . . . . . . O . O . O . O .
. . . . . . . . . . . . . . . . . . . . O O O O O O O .
. . . . . . . . . . . . . . . . . . . . . O . . O .
. . . . . . . . . . . . . . . . . . . . . . . . . O .
Finally, we can build high-period guns using glider/glider interactions.
What's interesting here is that we can generate the stream "A and not B"
without affecting the stream "B" because (unlike Life) there are lot
of ways for a glider to delete another without being destroyed.
To illustrate this, here's a gun I built before I found the
glider duplication reaction:
x = 86, y = 49
o$o10bo$bo9bobo$9b5o$10bo3bo$11b4o$11bobobo$11b5o6bo$13bo7b2obo$20b2ob
2o$18bo3bobo$19bo2b2obo$18b3obob2o$20b2ob2o$24bo2$7bo$7bo18bo$8bo2bo
15b2o$9bo17b2o$10bo16bob2o$26b4obo$29bobo$29bob3o$29b3o$31bo$15bo9b2o$
15b2obo6bo$13b3ob4o4bo$15bobobo5bo20bo31b2o$14b2ob3o8bo16bobo31b2obo$
16b2obo26bobo30bob2o$16b2o2b2o26bo31b2ob2o$20b2o27bo31bobo$22bo58bob2o
$81b3obo$23bo14b2o43bo$23b3o12bo$22b2obo13bob2o$22bob5o10b3obo$23bobo
2bo4bo5bobobo$23b2obo2bo4b2o4b2ob2o$23bob3o4b3obo5b2obo$26bo4b2obobo5b
obo$33b4o$33bo3bo$33b5o$36bobo$36bo!
It works by sending a stream through a glider relay, which leaves
a hole in the stream wherever it interacts with the glider in the relay.
A second gun inverts this stream, resulting in a high period stream. The
gun as such is made obsolete by direct glider duplication, but there are
undoubtedly many uses for the one-sided glider deletion reaction.
Among other things, it could be useful for building the sort of
pseudorandom gun that has been realized in Life by Dean Hickerson
and others.
Miscellaneous oscillators
-------------------------
Many different oscillators turned up in a random survey of 10x10 (rhombic)
starting states on an otherwise empty infinite grid. Most of these consisted
of an oscillating part stabilized by an anchor organized into honey-combs.
Like the period-43 mentioned in the preceding section, these often have
a low-period fringe that multiplies the total oscillation by 2, 3, or 5,
without affecting the interesting part, which I call the principal oscillation.
I'm going to list oscillators here by principal oscillation. Sometimes it
may be possible to eliminate the discrepancy between overall period and
principal oscillation, but I haven't tried to. It is also likely that
many of the stabilizing anchors below can be reduced in size. This is not
an exhaustive list of known oscillators, and I've left out common low-period
patterns that are easy to generate. Oscillators that have appeared
already in this article will not be repeated.
Period 7:
. . . O .
. . O O .
. O O . O O . O .
. . . O . O O O .
O . O O . O . . O O .
. O O . O . . . O .
O O . O O O O . . O .
. . O O . . . O . O .
. . O . O . O O . . O .
. . O O O . O O . O O O .
. . . . . O O . O O .
. . . . . . . O O .
O .
O .
. O O .
. . O O O .
. O O . . O O . O .
. O . . . . O O O .
. . O . . . . . O .
. . . . . . . . . O .
. . . . . . . . O O .
. . . . . . . . O .
. . . . . . . . . O . O .
. . . . . . . . O O O O .
. . . . . . . . . . . O .
. . . . . . . . . . . . O .
Period 9:
. . O O .
O O O . O .
. O . O O .
. O O O . O .
. . . . O O .
. . . . O .
. . . O O O .
. . . O . . O .
. . O O O . O .
. . O . O . . O .
. . . O O . O O .
. . . . . O O .
. . . . . . O .
Period 11:
. . O .
. O O .
. . O O . O .
O O O . O . O .
. . O . O . . O O .
. . O O O O O O . O O O .
. . O . . . O O . . O .
. . . . . . . . O O O .
. . . . . . . . . . O .
. . . . . . . . . . . O .
O O . O .
O . . O O .
. . O O . O .
O O O . O O .
. O . O O . O .
. . O O . O O .
. . . . O O .
Period 14:
. O O O .
O O . O .
O . . . O O .
O O . O O .
. . O O . O O .
. . O . O O .
. . . . O .
Period 17:
. . O .
. . O .
O O O O O O .
. . O . O O .
. . . O O .
.
. . . O O . . O .
. . O O . O O .
. . O . . O . O .
. . . O O . O O .
. . . . . O O . O O .
. . . . . . . O O .
. . . . . . . O .
Period 18:
. O . O .
. . O O O .
. O O . O .
O O . O O . O O O . O .
O . O O . O . O . O O O O .
. O O . O O O O O . O O .
. . . O O . O . O O O . O .
. . . O . O . . . . O .
Period 19:
. O . . . O .
O O . . O O O . O .
O . O O . O . O O O .
. O O . O O O O O . O .
. O . O O . . O . O O .
. . . O . O . O O O . O O .
. . . . . . . O O . O O O .
. . . . . . . . O O O . . O .
. . . . . . . . . . O .
Period 22:
. O .
. . O .
O O O O O .
. . O . O .
. . O O O O O .
. . . O . O . O O .
. . . . . . O O O O .
. . . . . . O O .
.
. . . . . . . . . . O .
. . . . . . . . . . . O O .
Period 26:
. O .
. O . O .
O O O O O .
. O . O . O O .
. O . . O O . O .
. . . O O . . O .
. . . . . O O O O O .
. . . . . . . O . O .
. . . . . O O O O O O .
. . O O . O . O . O . O .
. . . . O . O O . O .
. . . . . . . . O O O .
. . . . . . . . O . . O .
. . . . . . . . . . . O .
Period 29:
. . . O .
. . . O O .
. . O O . O O .
O O O . . . . O O O .
. O . O . . . O . O .
. . O O O O . . O O O .
O O O O . . O O O .
O O . . O O O O .
. O O O . O . O .
. . O . . O .
.
. . . . . . O .
Period 46:
. . . O .
. . . O O O .
. O O O . O .
O . O . O O O O O .
. O O O O O . . O .
. . O . O . O . . O .
. O O O O O O .
. . . . O .
. . . . O .
General Comments and Conclusion
-------------------------------
After working with this rule for several weeks, I was surprised at the
variety of interesting objects and reactions that existed in it. It's
a fairly simple rule, though admittedly more complicated than Conway's Life.
However, like Life, it is far simpler than the phenomena it supports.
I think it's interesting, among other things, for demonstrating that
there is a 2-state hexagonal CA with at least some Life-like properties.
I had been skeptical of this, since I had never seen a discussion of one.
There are some properties missing from this rule that make Life interesting.
Unlike Life, patterns die down very rapidly unless they stabilize into
honey-comb structures. The result of a collision between gliders and
stable objects is similarly tame, with the most common results being an
eater reaction or mutual annihilation. On the other hand, this can actually
be beneficial for designing patterns to realize some logical function
or growth rate.
Unlike Life, this rule does not seem to support finite still-life patterns.
The honeycomb structure is stable and can present an arbitrarily long
stable boundary, but corners always result in cell-producing neighborhoods
that usually result in low-period oscillations. The stability of the
honey-comb lattice is also very unlike Life, in which a small
change to a dense lattice almost always propagates very fast, destroying
it. It may be worth doing some systematic tests on random mutations of
a lattice background.
--
Paul Callahan Life Web Page: http://www.cs.jhu.edu/~callahan/lifepage.html
email: ppc997@aber.ac.uk