Spaceships in Conway's Life (Part 1)

[David I. Bell]

Spaceships in Conway's Life (Part 1)
by David I. Bell
db...@pdact.pd.necisa.oz.au
12 Aug 1992

This is the first of a series of articles on recent results in Conway's
Game of Life. There are many aspects of Life that are interesting and
have recent developments, such as glider guns, spaceships, puffer trains,
large period oscillators, and the construction of objects with desired
properties.

I am restricting this set of articles to spaceships because of two reasons.
Firstly, since the earliest days of Life around 1970, no truly new spaceships
had been discovered until just about three years ago, and therefore this area
is very new and exciting. And secondly, I have had a part in developing
this area, and therefore know first hand about some of the results. But I
will touch on several of the other areas as I go.

Almost all of the new spaceship results I will be describing were found by
one of three people. Possibly others have independently discovered some of
these things, and if so, we certainly should share credit with them. But
until I know otherwise, the credit for the discoveries belongs to the people
I mention. These people are Dean Hickerson, David Bell (myself), and
Hartmut Holzwart (listed in order of involvement).

Most of the new spaceships were found by computer search. The size and
complexity of most of the discoveries are such that they would not be
expected to turn up by running random patterns, or by manually trying a
set of possibilities. However, some of the "fine tuning" of the results
are the work of human thinking and manipulating pieces of the found results.

Firstly, I should define some terminology. A spaceship is a finite pattern
of live cells in Life that after a certain number of generations reappears,
but translated in some direction by a nonzero distance. Translation is
measured by the shortest king-wise connected path between two cells. So two
cells adjacent to each other are one cell apart, whether or not the cells
are adjacent orthogonally or diagonally. The process of translating after
a certain number of generations is called moving or traveling.

The number of generations before the pattern reappears (but translated)
is called the period of the spaceship. (This is analogous to the period of
stationary oscillators.) Many spaceships appear to be the same pattern
after a number of generations, but on closer examination are not really
the same. Instead of being merely translated, they are also reflected (or
flipped) as in a mirror. After twice that number of generations, the
spaceship does reappear in its original form, with just a translation.
The period always measures this full number of generations. Spaceships
which show their mirror image after half their period are called glide-
reflection spaceships.

Spaceships can travel orthogonally (straight left-right or up-down), or
diagonally. All known diagonal spaceships travel the same distance left-
right as they do up-down. There is no reason why a spaceship could not
travel (for example) two units across and one unit up for its translation.
However no example of such a spaceship is known. Theoretically, we could
build ships with any translation by using a universal computer/constructor.
But they would be very large and slow.

The translated distance divided by the period is the speed of the spaceship.
Since the maximum speed of propagation of a signal in Life is one cell per
generation, this speed is known as c (the speed of light). This speed is
also the fastest possible growth of any finite object for a finite number
of generations (think of a long line of ON cells). However, growth (or
even just movement) of a finite object for an infinite time cannot occur
at this speed. It was proven in the early days of Life that the maximum
possible speed of any spaceship is c/2 for orthogonal spaceships, and c/4
for purely diagonal spaceships. More generally, if a spaceship moves A
cells across and B cells up, then its period must be at least 2 * (A + B).
This means (for example) that an orthogonal spaceship might move by one cell
in two generations, or two cells in four generations, or three cells in six
generations, and so on. But no spaceship (for example) can move by one cell
in one generation, or two cells in three generations, or three cells in four
generations.

Whenever I list spaceships or puffers, I will follow some standard rules.
Since most known spaceships move orthogonally, that movement will not be
explicitly mentioned. They will always be drawn so as to move from right
to left. The few diagonal spaceships will be marked as such, and will
move in the indicated direction.

To begin with and to be complete, I will list the original spaceships.
These are the glider, the lightweight spaceship (LWSS), middleweight
spaceship (MWSS), and the heavyweight spaceship (HWSS). These were all
found very soon after Life was invented by Conway. They are:

[glider (diagonal to lower left, glide-reflective, period 4, speed c/4)]
.O.
O..
OOO

[LWSS (glide-reflective, period 4, speed c/2)]
.O..O
O....
O...O
OOOO.

[MWSS (glide-reflective, period 4, speed c/2)]
...O..
.O...O
O.....
O....O
OOOOO.

[HWSS (glide-reflective, period 4, speed c/2)]
...OO..
.O....O
O......
O.....O
OOOOOO.

The glider is the most basic spaceship. Since it is so small, it appears
spontaneously from random objects. Collisions between gliders produce
many useful things. For example, two gliders can produce another glider,
and three gliders can produce a LWSS or MWSS or a HWSS. Gliders can be
produced indefinitely by many kinds of "glider guns". The first glider gun
was found by Bill Gosper in 1970, and was the first example of a Life object
whose population grew arbitrarily large.

The three orthogonal spaceships are very useful because of the presence of
their "sparks". Sparks are cells at the edge of an object which die off,
and which can perturb other objects without destroying the object which
generates the spark. The commonest use of sparks from these spaceships is
to perturb an "engine" to produce puffer trains, or to modify stationary
objects when the spaceships pass by.

The three orthogonal spaceships above show an obvious pattern, and the
casual Life-player might wonder why the pattern cannot be continued to
make even larger spaceships. This will not work directly because the
sparks do not die off anymore for larger ships, but wreck the ship.

The following for example, doesn't work because the spark at the top
is actually a blinker, and doesn't die. Without the blinker, this object
is known as an OWSS (overweight spaceship). This name is also given to
even larger objects following the same pattern.

[non-working OWSS]
...OOO..
.O.....O
O.......
O......O
OOOOOOO.

It was discovered rather early that an OWSS can survive if it is "escorted"
by other smaller spaceships. The escorting spaceships are positioned to
prevent the formation of the deadly non-sparks. The following is an extreme
example of this. This shows the largest overweight spaceship which can be
safely escorted by only two other spaceships.

[OWSS escorted by two HWSS (period 4, speed c/2)]
....OOOO.......
...OOOOOO......
..OO.OOOO......
...OO..........
...............
...........OO..
.O............O
O..............
O.............O
OOOOOOOOOOOOOO.
...............
...............
....OOOO.......
...OOOOOO......
..OO.OOOO......
...OO..........

There are many other combinations of spaceships that will support one or
more OWSS. Some OWSS can be supported by a convoy of two spaceships on
each side. But for very long OWSS, no convoy of small spaceships can work
to stabilize it. However, it is possible to support an arbitrarily long
OWSS by nesting different sized OWSS side by side to stabilize them all,
with final small spaceships on the outside.

The next topic related to spaceships is called a tagalong. A tagalong is
something which follows behind one or more spaceships, and needs the
spaceships in order to survive. Generally, tagalongs are attached to the
sparks of a spaceship so that they don't destroy the spaceship. But some
tagalongs attach right to the base ship itself, and some even need some
modification of the base ships in order to work. A tagalong along with its
base ship can be considered as a large spaceship.

One of the first tagalongs was found a couple of years into the history of
Life. This is the Schick engine, found by Paul Schick in 1972. It uses
the sparks from two adjacent LWSS to keep the engine going.

[Schick engine tagalong (period 12, speed c/2)]
OOOO.....
O...O....
O........
.O..O..OO
......OOO
.O..O..OO
O........
O...O....
OOOO.....

This tagalong is very useful, because it splits into two separate parts.
The back part dies off on its own. But it can be perturbed by adjacent
LWSS, MWSS, or HWSS in many ways to produce output which remains. It
then becomes a puffer train. For example, adding one LWSS gives:

[Simple puffer train producing pairs of beehives (period 24, speed c/2)]
...........OO.
..........OOOO
.........OO.OO
..........OO..
OOOO..........
O...O.........
O.............
.O..O..OO.....
......OOO.....
.O..O..OO.....
O.............
O...O.........
OOOO..........

If a second LWSS is also placed at the bottom of the above object
symmetrically to the top LWSS, then the puffer produces a stream of
blinkers with period 12.

A tagalong can be changed into a puffer engine by perturbations as in
the above example. The reverse can also happen. A puffer engine can
be tamed and turned into a tagalong. This can generally be done by
using passing spaceships to destroy all of the puffer output. Such an
object will then be a large spaceship. I will give two examples.

The first example uses a well known puffer engine, the B heptomino. The
first two puffers in Life were found by Bill Gosper and are both based on
the B heptomino. The one given here is the second one he found, where a
single engine is perturbed by two LWSS to become a very dirty puffer. It
takes over 4600 generations for this puffer to settle down. It then
produces a large collection of objects with period 140.

[Dirty puffer train based on B heptomino (eventual period 140, speed c/2)]
.....
.OO..
OO.OO
.OOOO
..OO.
.....
.....
....O
...OO
..OO.
...OO
.....
.....
.....
.....
.OO..
OO.OO
.OOOO
..OO.

By adding another LWSS, this dirty puffer is tamed and becomes a spaceship
with period 20. This object has a rather large spark which can then be
perturbed with other spaceships to produce simple useful outputs such as
gliders.

[Period 20 spaceship based on B heptomino (period 20, speed c/2)]
..........O..O........
.OO......O............
OO.OO....O...O........
.OOOO....OOOO.........
..OO..................
......................
...........O..........
....O...O....O........
...OO....O...O...OO.OO
..OO.....O........O..O
...OO.............OOO.
............O..O......
.............OO.......
......................
......................
.OO...................
OO.OO.................
.OOOO.................
..OO..................

The second example is based on a puffer discovered by Bob Wainwright
in 1984. The period of this puffer is only eight, which is the minimum
puffer period known. (There are several other different period 8 puffers
known.) The one shown here produces a row of blinkers.

[Period 8 puffer train producing blinkers (speed c/2)]
...O.....
.O...O...
O........
O....O...
OOOOO....
.........
.........
.........
.OO......
OO.OOO...
.OOOO....
..OO.....
.........
.....OO..
...O....O
..O......
..O.....O
..OOOOOO.

By using a passing HWSS, the blinkers can be deleted, producing a true
spaceship which can be made as large as desired by moving the trailing
HWSS back.

[Period 8 spaceship (speed c/2)]
...O.............
.O...O...........
O................
O....O.....OO....
OOOOO.....OO.OOOO
...........OOOOOO
............OOOO.
.................
.OO..............
OO.OOO...........
.OOOO...OOO.OOO..
..OO.............
.................
.....OO..........
...O....O........
..O..............
..O.....O........
..OOOOOO.........

By using different puffers, and deleting the output in many many different
ways, a very large number of spaceships can be produced. But they all
have a few things in common. All of these orthogonal spaceships use the
LWSS, MWSS, or HWSS as essential components. Therefore they must all have
a speed of c/2, and a period which is a multiple of four. The question
arises as to whether there are some spaceships which move at different
speeds, have other periods, or don't make use of the normal spaceships.
The answer is YES, and is why this area has been exciting in the last
few years.

Before proceeding to these new things, I will recap two tantalizing
early results which showed that possibly such ships might be found.

This first one was noticed by many people, and is the pi heptomino.
The following is generation 1 of the pi heptomino. It reappears 30
generations later, with a translation of 9, for a very obscure speed
of 3c/10.

[generation 1 of pi heptomino, a non-working spaceship]
..O
.OO
O..
.OO
..O

Unfortunately, it also produces a large amount of other debris which
then quickly destroys the object. That debris can be controlled by
carefully placed blocks in its path, or by placing many copies of the
pi heptomino side by side. But all such constructions must be carried
out to infinity to work forever. No one has figured out how to make a
finite object based on this work.

The second tantalizing result was discovered by Charles Corderman in 1971
while doing an exhaustive search of polyominoes. A small object was
discovered which translated itself diagonally by 8 cells, with some other
debris remaining. The debris doesn't interfere immediately with the object,
and so it translates itself again. Only after many such translations does
the debris catch up to the engine and destroy it. Corderman found that by
perturbing the debris in various ways, or by placing multiple copies of the
engine alongside each other, the engine can survive forever. However, in
none of these cases was it a spaceship. It was instead a puffer, and left
debris behind. The following is one of the simplest of these puffers, and
leaves just blocks behind.

[Switch Engine puffer train (diagonal to upper left, glide-reflective,
period 288, speed c/12)]
.O.O........................
O...........................
.O..O.......................
...OOO......................
............................
..........................OO
..........................O.

The above object is one of the smallest known objects whose population grows
arbitrarily large. (All of these are based on the switch engine and have
only 11 ON cells.) The only known diagonal puffer trains are all based on
the switch engine. But no one succeeded in taming the debris completely to
create a spaceship until Dean Hickerson did this in April, 1991. He did
this by placing a large number of switch engines together so as to eliminate
all debris. His original ship required 13 switch engines, but his smaller
one given here only uses 10 of them. The number of them needed can possibly
be reduced even further, but this isn't known.

The spaceship is just a little too wide to be seen in an 80 column width,
so the description below is compressed in the following manner. Each
dollar sign represents 10 empty cells. Just use an editor to replace
each dollar sign by 10 periods, and you will be able to reconstruct the
picture of the full object.

[Cordership (diagonal to upper right, symmetrical, period 96, speed c/12)]
$$$.....OO$$$$$
$$$.....O...OO$$$$......
$$$....O......O.......OOO$$$.....
$$$..OOOOO...O.....OOO$$$........
$$$.....O...O......OOO$$$........
$$$..O..O$.O$$$.........
$$....OO.......OO$$$$$..
$$....OO$$$$$$.
$$$$$$$$.......
$$$$$........O$$........
$$$$$........O$$........
$$$$$........O$$........
$$$$$......OO$$.........
$$$$$.....OOO$$.........
$......OO$$$........OO$$.........
$......OO$$$$$$.........
$$$$$$$$.......
$$$$$$$$.......
$$$$$$$$.......
$$$$$........O$$........
$$$$$.......O$$.........
$$$$$........O$$........
........OO$$$$$$$.......
........OO$$$......O$$$$
$$$$.....O.O$$$.........
$$$$....OO.OO$$$........
$$$$.......OO$$$........
$$$$.OO$$$$....
$$$$...O..OOO$......O.O.......OOO.........
$$$$.OO.O$$.O.....OOO$..
OO$$$$.O..O$$.....OOO$..
OO...O.......O$$.........O$$.........O$...
....O.O.....OOO$$.........OO$$$$.
...O..O..OOOO.OO$$$$$$$.
.........O..OOO$$$O$$$$.
......O..OO..O$$.........OO.OO$$$......O..
....O.O.OO$$$....O$$$.........O..
.....O$$$$.O$$$......O..
$$$$.....O$..O.OO$$OO...
$$$$.........O.O......O.OOO$........OOO...
$$$$$.O....O.O....O$........OO...
$$$$........O...O.O......OO$$....
$$$$$OO..O..O...O$$.....
$$$$$.O...OO.O$$........
$$$$$.......O.O$$.......
$$.......O$$.........O.O$$....O..
$$......OOO$$$$$....O.O.
$$.....OO.OO$$$$$..O..O.
$$......OOO$$$$$........
$$.......O$$$$$.........
$$.....O.O$$$$$.....O..O
$$....OOOO$$$$$...OOO.OO
$$....O$$$$$.....O..OO..
$$$$$$$$O..O...
$$....OO.OO$$$$$..O.O...
$$...O.....O$$$$$.......
$$....O...O$$$$$........
$$.......O...O.......O$$$$.......
$$$O.O.....OOO$$$$......
$$.........O..O..OOOO.OO$$$$.....
$$$.....O..OOO$$$$......
$$$..O..OO..O$$$.........OO......
$$$O.O.OO$$$$...OO......
$$$.O$$$$$.....
$$$$$$$$.......
$$$$$$$$.......
$$$$$$$$.......
$$$$$$$$.......
$$$$$$$$.......
$$$$$$$.OO$....
$$$$$$$.OO$....
$$$$$...O$$$...
$$$$$..OOO$$$..
$$$$$.OO.OO$$$.
$$$$$..OOO$$$..
$$$$$...O$$$...
$$$$$.O.O$$$...
$$$$$OOOO.........OO$$..
$$$$$O$..OO$$..
$$$$$$$$.......
$$$$$OO.OO$$$..
$$$$.........O.....O$$$.
$$$$$O...O$$$..
$$$$$...O$$$...
$$$$$$$$.......
$$$$$.....OO$$$
$$$$$.....OO$$$

The Cordership has lots of debris that dies away. Gliders can hit this
debris and do interesting things. In particular, gliders can be turned
by 90 or 180 degrees by hitting the debris appropriately. Dean Hickerson
has used this fact to create some interesting constructions, such as
reflecting gliders back and forth forever between two Corderships that are
slowly pulling apart.

The Corderships form one of several new classes of spaceships, ending a
period of about 20 years when no new classes were found. However, it was
not the first of these new classes. The next part of this series will begin
exploring these new classes in earnest, starting with the c/2 period 2
spaceships.

That next article should appear in about two weeks.