Still-life glider reflector found
Paul Callahan
This result is about a month old, and very specific to Conway's Game of Life.
However, it answers a long-standing open question and thus seemed to be
of general interest to the CA community. Please see Alan Hensel's glossary
(http://www.cs.jhu.edu/~callahan/picgloss/picgloss.html) for any notation
specific to the Game of Life.
There are many patterns known that interact non-destructively with a glider
in such a way to convert it to another glider along a different path.
If the glider changes direction, such a pattern is called a reflector, and
can be used to circulate gliders along a closed path. Until recently,
all such patterns were oscillators of period greater than 1, resulting in
timing constraints that restrict the path "length" (specifically, the
number of generations for a complete circuit) to a multiple of the reflector's
period. Thus, a natural question, apparently proposed very early, was
whether there exists a still life (i.e. period 1 oscillator) that reflects a
glider. The existence issue was settled in the affirmative using arguments
based on the existence of a universal constructor, but the question of
finding an explicit (and reasonably small) pattern remained open.
The following pattern is a collaboration of work by David Buckingham,
Dean Hickerson, and myself. Several months ago, I became interested again
in one reflector mechanism that had been proposed but never realized, in
which a glider collides with a block to become the pi heptomino, which is then
"perturbed" non-destructively by other still-lifes (usually eaters or
blocks) to reconstruct the block and a glider (or some active pattern that
can be perturbed into a glider).
An automated search resulted in mixed success. I found exactly one
configuration that could reconstruct the block, and it could even be
perturbed to release gliders in several different ways. Unfortunately,
a beehive (a common six cell still life) was also created close to the
block, and its position made it impossible to eliminate with conventional
methods using still lifes (anything placed to destroy it would
be damaged by earlier activity). It seems that exact restorations of
even very common still lifes are quite rare. Many reactions will restore
a block, but this is the only one that left the new block in the same
location.
Further attempts at search did not turn up any more promising reflector
components. However, one variation on this imperfect reflector
was a way of producing an r pentomino, an explosive 5-cell pattern that can
be perturbed in numerous ways.
Around this time, I received a copy of David Buckingham's 8 still-life
"b heptomino turns," a remarkable set of constructions that make it possible
to route a b heptomino (actually a related pattern, called Herschel) through a
variety of paths, often emitting spontaneous gliders. With
these constructions, one can build oscillators and true glider guns of
any period greater than 61. This was itself a long-standing open question
that might have been resolved by the construction of a still life reflector.
Buckingham's components also made it possible to repair the imperfect
reflector.
It is well known (though not to me at the time) that one could perturb an
r pentomino into a Herschel. Thus, the imperfect reflector could be used
to perturb a glider into a Herschel. This Herschel could be sent through
stages of Buckingham's components, producing an arbitrary excess
of gliders along a variety of different paths. All that was needed to
complete the construction was a way to send just one glider along a
path to destroy the unwanted beehive.
The rest is just a matter of careful optimization. I'm slightly embarrassed
to admit that my first working version of this pattern required nearly
5000 generations to erase the beehive and become ready to reflect a
new glider. I refined it several times. Most recently, Dean Hickerson found
a custom perturbation of Herschel into several gliders, allowing the
reflector to accept another glider after 747 turns. There is probably
potential to reduce the bound still further, though the limit of
this method will still require hundreds of turns to function. Fortunately,
this is well within the limits of comfortable viewing in an efficient
life implementation on a fast machine.
I intend to feature this pattern (and hopefully, a discussion of Buckingham's
components) on my life web page in the near future. Alan Hensel has already
presented this pattern in his Life applet: http://users.vnet.net/alanh/life/
To run it, press "Open" and select "SLR.LIF"
For those without a Java compatible browser, I will attach a copy of this
pattern in a form that can be read by many Life programs. The commentary
is by Alan Hensel.
NOTE: I apologize in advance to anyone who objects to the attachment of
so many lines of non-prose content. The byte count of this attachment
is quite small, smaller than the above text. I consider it appropriate in
the sense of being useful for reaching those with highly restricted net
access who may nevertheless be interested in the result. If you disagree
with me as to its appropriateness, please contact me in e-mail, and we
can discuss the matter there instead of cluttering the group with even
less appropriate meta-discussion.
Paul Callahan (call...@inf.ethz.ch)
Web Page: http://wwwjn.inf.ethz.ch/paul/
--- cut here ---
#Life 1.05
#D Still-Life Reflector, smallest known
#D
#D Converts one glider into 5 for any input stream
#D with a period of 747 or greater, unless pipelining
#D techniques are employed. Notice that the main
#D piece is just the few eaters and blocks in the
#D upper right corner of the device; the rest of it
#D is a combination of David Buckingham's b-heptomino
#D turning reactions, just to delete a pesky beehive.
#D
#D B-heptomino mechanism: First, an r-pentomino
#D appears at gen 242. This is converted in 28 gens
#D to a B-heptomino, which undergoes a 59-generation
#D translation into a Herschel, which is flipped and
#D translated in a 77 gen reaction, followed by two
#D 90-degree turns in 64 gens each, two more 77 gen
#D translations, and a conversion into a glider to
#D destroy the beehive.
#D
#D By Paul Callahan and Dean Hickerson, Nov 8, 1996.
#N
#S 13
#P -65 -4
..*
*.*
.**
#P -56 24
..**
.*.*
.*
**
#P -47 31
..**
.*.*
.*
**
#P -36 21
**
**
#P -43 9
**
**
#P -34 35
**
**
#P -32 39
**
**
#P -17 15
**
*.*
.*
#P -8 11
**
.*
*
**
#P -5 20
**
**
#P 11 10
*
***
...*
..**
#P 26 13
**
**
#P 26 30
**
*
.***
...*
#P 32 20
..**
.*.*
.*
**
#P 46 27
**
**
#P 51 22
**
**
#P 53 26
**
**
#P 57 20
**
**
#P 23 2
...**
....*
.***....**
*......*.*
.*...***
..*.*...*
...**..**
#P 57 -9
**
**
#P 62 -4
**
**
#P 55 -15
**
**
#P 61 -11
**
**
#P 39 -18
...*
.***
*
**
#P 26 -15
**
**
#P 14 -5
**
*
.***
...*
#P -1 -25
*
***
...*
..**
#P 1 -6
**
**
#P -3 0
**
*
.***
...*
#P -10 -18
..**
..*
*.*
**
#P -19 3
**
*
.***
...*
#P -31 -11
**
**