Spaceships in Conway's Life (Part 2a)
David I. Bell
by David I. Bell
db...@pdact.pd.necisa.oz.au
28 Aug 1992
This is the second in a series of articles concerning Conway's Game of Life.
In this article, I will describe the early history of the discovery of the
new classes of spaceships, and then survey the results for all the known
period 2 spaceships. All period 2 spaceships must be orthogonal, and must
travel at the speed of c/2. This follows from the speed restrictions
mentioned in my previous article.
In July of 1989 Dean Hickerson started writing a Life search program for his
Apple IIe. It was written in 6502 assembly language and Applesoft BASIC.
Dean's Life search program looks for patterns that repeat themselves after a
small number of generations, with or without translations. (Translations
are used when you want to find spaceships instead of oscillators.)
During a search, the program recursively attempts to set cells ON or OFF,
and for each cell that is set uses transition and implication rules in order
to detect contradictions in the current state of cells. This allows the
program to quickly stop and backtrack over impossible situations, and thus
reduce enormously the size of the search. This program was described in
the xlife 3.0 distribution.
Search programs typically attempt to set the cells in a column-by-column
order. Since a cell's fate in N generations is usually dependent on the
state of all cells within a distance of N, contradictions cannot usually
be detected until the state of the next N columns has been specified.
This means that looking for oscillators or spaceships is much harder for
larger periods. The current useful limit on search programs of this type
is for period 5. Some searches in small areas have been done for periods
6 and 7.
Another effect of the order of setting cells column-by-column is that objects
which have many rows are harder to find than those with fewer rows. (The
number of columns can be very large and has little effect on the search.)
The current search programs can usefully look for objects which have about
10 rows (20 rows if symmetry is used), but this limit can be raised somewhat
for low-period searches, such as up to 14 rows for period 2.
Since the useful number of rows being searched is limited, many of the
spaceships which are found are of one of two types. They are either wide
and short or are thin and long. These terms refer to the dimensions of the
spaceship with respect to the direction that it travels. Therefore a thin
and long spaceship looks like an "arrow", whereas a wide and short spaceship
looks like a "wave". However, for many smaller space ships where both
dimensions fit within the row limit and are of comparable size, they can
look like "blobs".
Using his program, and looking for short, wide spaceships, Dean Hickerson
found the first period 2 spaceships on July 28, 1989. These were the first
examples of a new class of spaceship. He does not remember which specific
spaceship was found first, but the following ship was among the first ones
found, and is the smallest known period 2 spaceship.
[Smallest known period 2 spaceship (speed c/2)]
.....O.O
....O..O
...OO...
..O.....
.OOOO...
O....O..
O..O....
O..O....
.O......
..OOOO.O
...O...O
....O...
....O.O.
........
...OOO..
...OO...
...OOO..
........
....O.O.
....O...
...O...O
..OOOO.O
.O......
O..O....
O..O....
O....O..
.OOOO...
..O.....
...OO...
....O..O
.....O.O
Within a few hours of finding the first period 2 ship, Dean had discovered
a grammar for constructing an infinite number of different short, wide,
period 2 spaceships. A grammar is an "alphabet" of "components", along
with rules for the possible sequences of connections between components.
Components are simply the identifiable pieces of a ship which reappear over
and over in different ships in different combinations. There are three
components in the above spaceship, as will be seen below.
The complete grammar describes the components, the allowed sequences of the
components, and the manner in which the components are joined together.
The following are the components of Dean's first grammar.
[A] [A'] [B] [B'] [C] [C']
.....O.O .......O X X X X
....O..O ....OOOO ... .O.. ..... .O...
...OO... ....OO.. OOO .O.O OOO.. .O.O.
..O..... ..O..... OO. O... OO... O....
.OOOO... ..OOOO.. OOO .O.O OO... O...O
O....O.. .O...... ... .O.. OOOOO .O..O
O..O.... OOO..O.. X X ..O.. .O.O.
O..O.... .OOO.... X X
.O...... ..O.....
..OOOO.O ...OOO.O
...O...O ...O..OO
....O... ....OOO.
....O.O. ......O.
X X
[D] [D'] [E] [E'] [F] [F']
X X X X X X
... .O.. ...O.O ....O ...O .O.O
OOO .O.O ..O..O ..OOO .OOO O..O
OO. O... ..O... .OOO. OOO. O...
OO. O... .O..O. O..O. .OOO O..O
OOO .O.O OOO... O.... ...O .O.O
... .O.. .OOO.. O..O. X X
X X ...O.. .O.O.
X X
[G] [G']
X X
.O.O.. ...O...
O..O.. .OOO...
O..... OOO....
O..... .OO....
.O..OO ..OO..O
..OOOO ...OO.O
...... .......
..OOOO ...OO.O
.O..OO ..OO..O
O..... .OO....
O..... OOO....
O..O.. .OOO...
.O.O.. ...O...
X X
The components occur in pairs identified by the same letter, but with or
without a quote mark (e.g., A and A'). Such pairs are related in that they
are the two phases of the same section of a period 2 spaceship. So that,
for example, if a period 2 spaceship contains component B in generation 0,
then in generation 1 it must contain component B' in the same position
within the ship.
Besides the listed components, there are other components which are their
mirror images. The mirroring is done by flipping the component across a
horizontal line. The mirrored component names are the same as for the
original components, except that they end with a trailing dash. So that,
for example, the mirror image of component A' is A'-. Mirror images for
symmetrical components such as B would be duplicates and so are not used.
The components that make up a spaceship are strung together like beads on
a string, stacked one above the other. A sequence of components specifies
the order of components, arranged from top to bottom. When doing this,
the components must be correctly aligned horizontally. The 'X' characters
in the component diagrams specify the proper alignment. When two components
are stacked together, they must be placed adjacent to each other so that
the 'X' characters are in the same column. The rows containing the 'X'
characters are not part of the components, and should be removed.
The following shows an example of stacking two components correctly.
[Section B F' of a period 2 spaceship]
X
....
OOO.
OO..
OOO.
....
.O.O
O..O
O...
O..O
.O.O
X
The final part of the grammar specifies the allowed sequences of components.
Only certain sequences of components can be used to make a valid spaceship.
The following rules specify these allowed sequences.
The sequence must begin with A or A'.
The sequence must end with A- or A'-.
Each pair of adjacent symbols must appear in one line of the following table,
with the first symbol found before the vertical bar, and the second symbol
found after the vertical bar.
A C' E- E' F' G | B C D
A' C E E'- F G' | B' C' D'
B C- D | A- C'- E E'- F' G
B' C'- D' | A'- C- E- E' F G'
The simplest example of a sequence which follows these rules is A B A-,
which represents the c/2 period 2 ship given above. Another example of a
spaceship created using these rules is A D E B' A'-, which represents
the following spaceship.
[One of many period 2 spaceships constructed by the above grammar (speed c/2)]
.......O.O
......O..O
.....OO...
....O.....
...OOOO...
..O....O..
..O..O....
..O..O....
...O......
....OOOO.O
.....O...O
......O...
......O.O.
..........
.....OOO..
.....OO...
.....OO...
.....OOO..
..........
......O.O.
.....O..O.
.....O....
....O..O..
...OOO....
....OOO...
......O...
....O.....
....O.O...
...O......
....O.O...
....O.....
......O...
....OOO...
...O..OO..
...OOO.O..
..O.......
.OOO......
OOO..O....
.O........
..OOOO....
..O.......
....OO....
....OOOO..
.......O..
Small tagalongs were soon found for several of these components. (These
tagalongs can also be attached to many of the other period 2 spaceships.)
The one for component C was found by Robert Wainwright, and the one for
component A was found by Bill Gosper.
[C component with tagalong] [A component with tagalong]
X ........O.
......... .....O.O.O
OOO...... ....O..O..
OO....... ...OO.....
OO....O.. ..O.......
OOOOO.O.O .OOOO.....
.O.....O. O....O....
X O..O......
O..O......
.O........
..OOOO.O..
...O...O..
....O.....
....O.O...
X
Dean Hickerson also looked for thin, long period 2 ships in those first
weeks. These spaceships are much harder to find, and so he only found one
basic ship before moving on to search for other things. This spaceship is
shown below.
[First long period 2 spaceship (speed c/2)]
.............O.......
...........OO........
........OOOO.O.......
........OO.......OO..
......O...OO.O...OOOO
......OOOO.O.O.O....O
...O.O......OO.......
..OOOOOO.OO.OO.OO....
.OO.....OO...O.......
OO....OO....O........
.OO....OOOO..........
.....................
.OO....OOOO..........
OO....OO....O........
.OO.....OO...O.......
..OOOOOO.OO.OO.OO....
...O.O......OO.......
......OOOO.O.O.O....O
......O...OO.O...OOOO
........OO.......OO..
........OOOO.O.......
...........OO........
.............O.......
At the end of September, 1989, Dean discovered an extensible tagalong for
the above ship that is now named a wicktrailer. This tagalong allows the
ship to be made as long as desired. Such a tagalong can be described as
having a period, which is the number of generations it takes before a unit
of the tagalong reappears in the same place.
[Period 2 ship with wicktrailer (period 20 extensible tagalong) (speed c/2)]
............................O.........O.........O..
.............O...........OOOO......OOOO......OOOO..
...........OO..........OOO.O.....OOO.O.....OOO.O...
........OOOO.O........OO...O....OO...O....OO...O...
........OO.......OO...O....OO...O....OO...O....OO..
......O...OO.O...OOOO.O.....OOO.O.....OOO.O.....OOO
......OOOO.O.O.O....OOOO......OOOO......OOOO......O
...O.O......OO.........O.........O.........O.......
..OOOOOO.OO.OO.OO..................................
.OO.....OO...O.....................................
OO....OO....O......................................
.OO....OOOO........................................
...................................................
.OO....OOOO........................................
OO....OO....O......................................
.OO.....OO...O.....................................
..OOOOOO.OO.OO.OO..................................
...O.O......OO.....................................
......OOOO.O.O.O....O..............................
......O...OO.O...OOOO..............................
........OO.......OO................................
........OOOO.O.....................................
...........OO......................................
.............O.....................................
The tagalong can be attached to the other "foot" of this ship in a similar
manner to produce a symmetrical ship of any length, or with two unequal
length wicks. The tagalong can also be attached to the "foot" of the
other period 2 ships on component A'. Doing this allows the construction
of a ship which is as wide and as long as desired.
There is a hidden motivation in looking for new ships and their tagalongs.
Besides the elegance of new ships, Dean was hunting for new puffer trains.
Puffer trains allow for the construction of interesting large Life objects,
including devices which perform logic operations or numeric calculations.
There are only a small number of basic types of puffer trains, and new
methods for making puffer trains would be useful. For every new spaceship
which is found, there is the possibility that it contains a new set of
"sparks" that has not been seen before. Such a new set of sparks might
allow a new type of puffer engine to work, or might be useful to catalyze
a reaction in a new manner. So far this has not been successful.
Another way that a new puffer train might be constructed is by perturbing an
extensible tagalong such as the one in the above ship. If the perturbation
results in a reaction that travels at a speed less than or equal to the
ship (c/2 in this case), and that reaction leaves debris behind, then a
puffer train results. Unfortunately, this process has so far not worked
with any extensible tagalong. The reaction either breaks off, or travels
faster than the ship and ends up destroying the ship. For example, deleting
one cell from the end of the wicktrailer, or adding one cell to it almost
always results in one of either two reactions which travel at 6c/7 or 11c/12
and catch up to the ship and destroy it.
After Dean found the above results, he went looking for other things, and
so the class of period 2 spaceships wasn't further developed for a while.
Meanwhile, I had heard of Dean's search program, read his notes about it,
and wrote my own program in C, and started making my own discoveries. I
sent a copy of the program to Hartmut Holzwart. He made some modifications
to it (such as speedups, new symmetries, and different search orders), and
then also started making many new discoveries. But it wasn't until June of
this year that we started looking for period 2 spaceships.
On June 7, 1992, I was experimenting with a new search feature, and found
three new components for period 2 ships. The most interesting component is
a repeatable diagonal component which bends the ship backwards with a slope
of 3/6. The other two larger components just provide a connection to an
already known ship component, and terminate the end of the new component.
The following shows a ship using all three components, with the diagonal
one repeated twice.
[Period 2 spaceship with repeatable "barber pole" component (speed c/2)]
........................O
......................OOO
.....................OO..
.....................O...
...................O.O...
.................OOO.....
................OO..O....
................O.O......
................OOO......
................O.OOO....
...............OO........
..............OO.O.......
.................O.O.....
.............O...........
.............OO.O........
.............O.O.........
............OO...........
...........OO.O..........
..............O..........
..........O..............
..........OO.O...........
..........O.O............
.........OO..............
........OO.O.............
...........O.............
.......O.................
.......OO.O..............
.......O.O...............
......OO.................
...OO.OOO................
...O....O................
...O.....................
....O..O.................
.....OO..................
......OO.................
...OOO.O.................
..O...OO.O.O.............
.O...O..O..O.............
.O..O.O.O................
.O........O..............
..O..OO...O..............
...OO.OOOOOO.............
....OO...O.O.............
....O.O..................
...O.....................
....O..O.................
....O.O..................
.........................
...OOO...................
...OO....................
...OOO...................
.........................
....O.O..................
....O....................
...O...O.................
..OOOO.O.................
.O.......................
O..O.....................
O..O.....................
O....O...................
.OOOO....................
..O......................
...OO....................
....O..O.................
.....O.O.................
The diagonal component can obviously be repeated arbitrarily often to make
an "arm" as long as desired. The same arm can also be constructed on the
other side of the ship to make it symmetrical, creating a bow shaped ship.
One interesting thing about a long string of these diagonal components is
that both phases appear identical to each other, but shifted. This makes
the arm act somewhat like a "barber pole" with a pattern appearing to move
up (or down) the arm as the ship moves.
A few days later I found a second repeatable diagonal component. This
component is actually a tagalong since it just attaches to a "foot" of an
intact period 2 ship. The slope of this tagalong is 8/13. This tagalong
is called the "glancing head" because it resembles a head with two eyes
looking sideways. The following shows two copies of this tagalong, one
attached to the base ship and the second to the first tagalong. Again,
this arm can be made as long as desired.
[Period 2 spaceship with repeatable "glancing head" tagalong (speed c/2)]
.......................O
.....................OOO
....................OO..
....................O...
..................O.O...
................OOO.....
...............OO..O....
..............O..O......
..............O..O......
..............O.........
...............O..O.....
................OO......
.................OO.....
...............O.O......
.............OOO.O......
............OO..........
............O...........
..........O.O...........
........OOO.............
.......OO..O............
......O..O..............
......O..O..............
......O.................
.......O..O.............
........OO..............
.........OO.............
.......O.O..............
....OOOO.O..............
....OO..................
..O.....................
..OOOO..................
.O......................
OOO..O..................
.OOO....................
..O.....................
...OOO.O................
...O..OO................
....OOO.................
......O.................
....O...................
....O.O.................
...O....................
....O.O.................
....O...................
......O.................
....OOO.................
...O..OO................
...OOO.O................
..O.....................
.OOO....................
OOO..O..................
.O......................
..OOOO..................
..O.....................
....OO..................
....OOOO................
.......O................
By using a piece of Dean Hickerson's wicktrailer, one foot can be turned
into two feet. This allows the construction of a "binary tree" spaceship,
which branches an arbitrary number of times. Here the wicktrailer tagalong
can be attached to any foot, and two copies of the glancing head tagalong
can be attached to the two feet of the wicktrailer. The following shows a
simple example of connecting these tagalongs together to make a branching
spaceship.
[Period 2 binary tree spaceship (speed c/2)]
.......................................O..
.....................................OOO..
....................................OO....
....................................O.....
..................................O.O.....
................................OOO.......
...............................OO..O......
..............................O..O........
..............................O..O........
..............................O...........
...............................O..O.......
................................OO........
.................................OO.......
...............................O.O........
............................OOOO.O........
.......O..................OOO.O...........
....OOOO.................OO...O...........
....OO...................O....OO..........
..O....................O.O.....OOO.O......
..OOOO...............OOO.........O.O......
.O..................OO..O..........OO.....
OOO..O.............O..O...........OO......
.OOO...............O..O..........O..O.....
..O................O............O.........
...OOO.O............O..O........O..O......
...O..OO.............OO.........O..O......
....OOO...............OO.........OO..O....
......O.............O.O...........OOO.....
....O.............OOO.O.............O.O...
....O.O..........OO...................O...
...O.............O....................OO..
....O.O........O.O.....................OOO
....O........OOO.........................O
......O.....OO..O.........................
....OOO....O..O...........................
...O..OO...O..O...........................
...OOO.O...O..............................
..O.........O..O..........................
.OOO.........OO...........................
OOO..O........OO..........................
.O..........O.O...........................
..OOOO....OOO.O................O..........
..O......OO..................OOO..........
....OO...O..................OO............
....OOOO.O..................O.............
.......OOOO.O.............O.O.............
..........O.O...........OOO...............
............OO.........OO..O..............
...........OO.........O..O................
..........O..O........O..O................
.........O............O...................
.........O..O..........O..O...............
.........O..O...........OO................
..........OO..O..........OO...............
...........OOO.........O.O................
.............O.O.....OOO.O................
...............O....OO....................
...............OO...O.....................
................OOO.O.....................
..................OOOO.O..................
.....................O.O..................
.......................OO.................
......................OO..................
.....................O..O.................
....................O.....................
....................O..O..................
....................O..O..................
.....................OO..O................
......................OOO.................
........................O.O...............
..........................O...............
..........................OO..............
...........................OOO............
.............................O............
Since each branch can be extended to be as long as necessary by using more
glancing head tagalongs, enough room can be created to build a fully populated
binary tree ship, containing 2^N nodes.
The wicktrailer is even more versatile than is shown above. A longer
section of the wicktrailer has even more feet. There is room for the
glancing head tagalong to be attached to each one of those feet, and for
more glancing head tagalongs to be attached to those tagalongs. Counting
each section of wicktrailer as a node, this means that not only can full
binary trees be constructed, but full N-ary trees can also be constructed,
for any N. The following illustrates the construction details that allow
such a spaceship to be made.
[Period 2 N-ary tree spaceship details (speed c/2)]
.............................O.........O.........O..........
...........................OOO.......OOO.......OOO..........
..........................OO........OO........OO............
..........................O.........O.........O.............
........................O.O.......O.O.......O.O.............
......................OOO.......OOO.......OOO...............
.....................OO..O.....OO..O.....OO..O..............
....................O..O......O..O......O..O................
....................O..O......O..O......O..O................
....................O.........O.........O...................
.....................O..O......O..O......O..O...............
......................OO........OO........OO................
.......................OO........OO........OO...............
.....................O.O.......O.O.......O.O................
..................OOOO.O....OOOO.O....OOOO.O....O...........
................OOO.O.....OOO.O.....OOO.O.....OOO...........
...............OO...O....OO...O....OO...O....OO.............
...............O....OO...O....OO...O....OO...O..............
.............O.O.....OOO.O.....OOO.O.....OOO.O..............
...........OOO.........OOOO.O....OOOO.O....OOOO.O...........
..........OO..O...........O.O.......O.O.......O.O...........
.........O..O...............OO........OO........OO..........
.........O..O..............OO........OO........OO...........
.........O................O..O......O..O......O..O..........
..........O..O...........O.........O.........O..............
...........OO............O..O......O..O......O..O...........
............OO...........O..O......O..O......O..O...........
..........O.O.............OO..O.....OO..O.....OO..O.........
.......OOOO.O..............OOO.......OOO.......OOO..........
....OOOO.O...................O.O.......O.O.......O.O........
....OO...O.....................O.........O.........O........
..O......OO....................OO........OO........OO.......
..OOOO....OOO.O.................OOO.......OOO.......OOO.....
.O..........O.O...................O.........O.........O.....
OOO..O........OO............................................
.OOO.........OO.............................................
..O.........O..O............................................
...OOO.O...O................................................
...O..OO...O..O.............................................
....OOO....O..O.............................................
......O.....OO..O...........O.........O.........O...........
....O........OOO.........OOOO......OOOO......OOOO...........
....O.O........O.O.....OOO.O.....OOO.O.....OOO.O............
...O.............O....OO...O....OO...O....OO...O............
....O.O..........OO...O....OO...O....OO...O....OO...........
....O.............OOO.O.....OOO.O.....OOO.O.....OOO.........
......O.............OOOO.O....OOOO.O....OOOO.O....O.........
....OOO................O.O.......O.O.......O.O..............
...O..OO.................OO........OO........OO.............
...OOO.O................OO........OO........OO..............
..O....................O..O......O..O......O..O.............
.OOO..................O.........O.........O.................
OOO..O................O..O......O..O......O..O..............
.O....................O..O......O..O......O..O..............
..OOOO.................OO..O.....OO..O.....OO..O............
..O.....................OOO.......OOO.......OOO.............
....OO....................O.O.......O.O.......O.O...........
....OOOO....................O.........O.........O...........
.......O....................OO........OO........OO..........
.............................OOO.O.....OOO.O.....OOO.O......
...............................O.O.......O.O.......O.O......
.................................OO........OO........OO.....
................................OO........OO........OO......
...............................O..O......O..O......O..O.....
..............................O.........O.........O.........
..............................O..O......O..O......O..O......
..............................O..O......O..O......O..O......
...............................OO..O.....OO..O.....OO..O....
................................OOO.......OOO.......OOO.....
..................................O.O.......O.O.......O.O...
....................................O.........O.........O...
....................................OO........OO........OO..
.....................................OOO.......OOO.......OOO
.......................................O.........O.........O
A side effect of this construction is that for any sized square, no
matter how large, there exists a period 2 spaceship whose cells occupy at
least some constant percentage of the area of the square (around 10%).
Later, another repeating diagonal tagalong was discovered, which also allows
N-ary tree ships to be built. Here the slope is 4/17, which is shallower
than the previous tagalong. This tagalong has the name "staring head",
and looks similar to the main component of the base ship. The following
illustrates this tagalong and how it may be connected.
[Period 2 spaceship demonstrating "staring head" tagalong (speed c/2)]
..........O.........O.............
.......OOOO......OOOO......O......
....OOOO.O.....OOO.O.....OOO......
....OO...O....OO...O....OO........
..O......OO...O....OO...O.........
..OOOO....OOO.O.....OOO.O.........
.O..........OOOO.O....OOOO.O......
OOO..O.........O.O.......O.O......
.OOO.............OO........OO.....
..O.............OO........OO......
...OOO.O.......O..O......O..O.....
...O..OO......O.........O.........
....OOO.......O.........O.........
......O.......OOO.......OOO.......
....O..........O..O......O..O.....
....O.O........OOO.......OOO......
...O..........O.........O.........
....O.O......OOO.......OOO........
....O.......OOO..O....OOO..O......
......O......O.........O..........
....OOO.......OOOO......OOOO......
...O..OO......O.........O.........
...OOO.O........OO........OO......
..O.............OOOO.O....OOOO.O..
.OOO...............O.O.......O.O..
OOO..O...............OO........OO.
.O..................OO........OO..
..OOOO.............O..O......O..O.
..O...............O.........O.....
....OO............O.........O.....
....OOOO.O........OOO.......OOO...
.......O.O.........O..O......O..O.
.........OO........OOO.......OOO..
........OO........O.........O.....
.......O..O......OOO.......OOO....
......O.........OOO..O....OOO..O..
......O..........O.........O......
......OOO.........OOOO......OOOO..
.......O..O.......O.........O.....
.......OOO..........OO........OO..
......O.............OOOO......OOOO
.....OOO...............O.........O
....OOO..O........................
.....O............................
......OOOO........................
......O...........................
........OO........................
........OOOO......................
...........O......................
--------------------- [Continued in next mail article] ----------------------
Tom Granvold
I need part 1 of the Spaceships on Conway's Life articles.
Part 2a and 2b arrived, but due to running out of I-nodes on our
system, I never saw part 1. I would appreciate it is someone could
email me part 1.
Thanks in advance,
Tom Granvold
------------------------------------------------------
Mail: 2400 Geng Rd., Palo Alto, Calif. 94303
UUCP: t...@clipper.ingr.com
------------------------------------------------------