Spaceships in Conway's Life (Part 6a)
David I. Bell
by David I. Bell
db...@pdact.pd.necisa.oz.au
23 Oct 1992
This is the sixth and last in a series of articles concerning Conway's Game
of Life. In this article, I will show the only period 5 spaceship known,
discuss methods for creating spaceships with an arbitrarily large period,
and show a couple of objects which are not truly spaceships, but which
could be considered spaceship-like.
Period 5 spaceships could exist in one of three types. They could be
orthogonal and have a speed of c/5 or 2c/5, or they could be diagonal with
a speed of c/5. No period 5 spaceship with a speed of c/5 is known.
For a speed of 2c/5, only one basic period 5 spaceship is known. Dean
Hickerson found this on July 23, 1991. This spaceship is amazingly small,
which made its finding possible. If any other period 5 spaceships exist,
they appear to be too large to find using the current search programs.
Dean's period 5 spaceship is shown below.
[Only known basic period 5 spaceship (speed 2c/5)]
......O.O..
...O....O..
..OOO....O.
.O.O.......
OO..OO....O
.OO..OOOOO.
...........
...........
...........
.OO..OOOOO.
OO..OO....O
.O.O.......
..OOO....O.
...O....O..
......O.O..
This basic spaceship is unique because its speed is not the inverse of an
integer. All other known basic spaceships have a speed of c/2, c/3, c/4,
or c/12, which are all inverses of integers. Period 5 is the smallest period
where a non-integral inverse speed is possible.
Dean's spaceship has several nice sparks, to which tagalongs could be
expected to be attached. But only a small number of tagalongs have been
found for the spaceship, and these require two copies of the spaceship
to be placed side by side so that the edge sparks are adjacent. These
tagalongs are shown below.
[Three tagalongs for period 5 spaceship (speed 2c/5)]
.....OO..O... .....OO..O....... .....OO..O.........
.....OOO..... .....OOO......... .....OOO...........
.OOO.O....... .OOO.O........... .OOO.O.............
O.O.O.OOO.O.. O.O.O.OOO.O...... O.O.O.OOO.O........
O...OOOOOO... O...OOOOOO....... O...OOOOOO.........
O............ O................ O..................
.O.O......... .O.O............. .O.O...............
............. ................. ...................
.O.O......... .O.O............. .O.O...............
O............ O................ O..................
O...OOOOOO... O...OOOOOO....... O...OOOOOO.........
O.O.O.OOO.O.. O.O.O.OOO.O...... O.O.O.OOO.O........
.OOO.O....... .OOO.O........... .OOO.O.............
.....OOO..... .....OOO......... .....OOO...........
.....OO..O... .....OO..O....... .....OO..O.........
............. ...............OO ...................
..........OO. ..........OO...OO ..........OO....O.O
..........OOO ..........OOO.... ..........OOO..O...
..........OO. ..........OO...OO ..........OO...O..O
............. ...............OO ................O..
.....OO..O... .....OO..O....... .....OO..O.........
.....OOO..... .....OOO......... .....OOO...........
.OOO.O....... .OOO.O........... .OOO.O.............
O.O.O.OOO.O.. O.O.O.OOO.O...... O.O.O.OOO.O........
O...OOOOOO... O...OOOOOO....... O...OOOOOO.........
O............ O................ O..................
.O.O......... .O.O............. .O.O...............
............. ................. ...................
.O.O......... .O.O............. .O.O...............
O............ O................ O..................
O...OOOOOO... O...OOOOOO....... O...OOOOOO.........
O.O.O.OOO.O.. O.O.O.OOO.O...... O.O.O.OOO.O........
.OOO.O....... .OOO.O........... .OOO.O.............
.....OOO..... .....OOO......... .....OOO...........
.....OO..O... .....OO..O....... .....OO..O.........
The first tagalong at the left was found manually by Robert Wainwright.
The other two tagalongs shown are tagalongs for that tagalong. The one in
the middle was found by me using my search program. The one on the right
was also found manually by Robert Wainwright. The tagalong on the right will
appear if one of the blocks in the middle tagalong is removed.
Obviously the tagalongs above could be used to create a very wide spaceship
by joining many base spaceships together. But there is no known way to
make a longer spaceship.
Except for the Corderships, all known spaceships with a period larger than 5
are composite constructions that require the use of at least one low period
spaceship to support a tagalong or puffer engine. Because of the use of
low period spaceships, the speeds of all these higher period spaceships are
restricted to the same speeds as the base spaceships they use. So all
known spaceships have speeds of c/2, c/3, c/4, 2c/5, or c/12, no matter
what their period is.
The situation is even worse than the statement above, because except for a few
period 9 c/3 spaceships, and a few period 6 spaceships made from a period 6
tagalong to a period 2 spaceship, all known multiple-period spaceships are
based on the standard spaceships. Therefore, these other multiple-period
spaceships all travel at the common orthogonal speed of c/2.
For the remainder of this article I will usually be showing puffer trains
instead of spaceships. The reason for this is that usually puffer trains
are more useful than bare spaceships because you can build things with them,
and secondly the output of a puffer train can usually be destroyed to turn
it into an actual spaceship if desired. Therefore, the objects shown will
not have the puffer output deleted.
Much of the common puffer debris can be deleted easily by perturbations
using standard spaceships. Examples of this are shown below.
[Loaf, block, blinker, and gliders being deleted by passing spaceships]
...OO.. OO..... .O..... ...O. ...O..
..OO.OO OO..... .O..... .O.O. ...O.O
...OOOO ....... .O..... ..OO. ...OO.
....OO. ....O.. ....... ..... ......
....... ..O...O ...OO.. ..... ......
....... .O..... .O....O ..OO. .O..O.
....... .O....O O...... .OOOO O.....
..O.... .OOOOO. O.....O OO.OO O...O.
.O.O... OOOOOO. .OO.. OOOO..
O..O...
.OO....
.......
....O..
..O...O
.O.....
.O....O
.OOOOO.
Other debris such as beehives and loaves in the other orientation are not as
easy to destroy. They and other debris can be destroyed by passing rakes
(puffer trains which produce streams of gliders). Alternatively, in many
cases the debris can be suppressed by perturbing the debris with a passing
spaceship before it stabilizes into the beehive or loaf. So even though most
of the objects are puffer trains, they can all be converted into spaceships
of the same period by adding extra standard spaceships or rakes.
Many of the puffer trains and spaceships shown in the remainder of this
article are rather large. Their pictures have been compressed when necessary
by replacing sets of 10 adjacent periods with a dollar sign. Use an editor
to replace each dollar sign by ten periods to restore the full picture.
There are many periods which are constructible using standard spaceships
and a puffer engine or tagalong. Each puffer engine has a reasonably small
period, which must be a multiple of 4 because of their use of standard
spaceships to support the puffer engine. The puffer output can either be
of the same period as the puffer engine, or a small multiple of it.
Following are five of the basic puffer engines or tagalongs which are used
to produce puffer-based output. This list does not include the period 8
blinker puffers, which I will cover separately a little later.
[Five basic puffer engines]
A B C
OOOO..... .OO....... .OO..
O...O.... OO.OO..... OO.OO
O........ .OOOO..... .OOOO
.O..O..OO ..OO...... ..OO.
......OOO .......... .....
.O..O..OO .......... .....
O........ ....O..... ....O
O...O.... ...OO..... ...OO
OOOO..... ..OO...... ..OO.
...OO..... ...OO
.......... .....
.......... .....
.......... .....
.......... .....
....OOOOO. .OO..
....O....O OO.OO
....O..... .OOOO
.....O.... ..OO.
D E
...OO............ .OO.....
..OO.OOOO........ OO.OOOO.
...OOOOOO........ .OOOOOO.
....OOOO......... ..OOOO..
................. ........
................. .....OO.
OOOOOOOOOO....... ........
O................ ..OO....
O................ .O....OO
.O............... .O....O.
................. .OO.....
................. ...O....
................. ........
...OO............ ...O....
..OO.OOOO...OO... .OO.....
...OOOOOO..OO.OOO .O....O.
....OOOO....OOOOO .O....OO
.............OOO. ..OO....
........
.....OO.
........
..OOOO..
.OOOOOO.
OO.OOOO.
.OO.....
These puffer engines labeled above with letters are described as follows.
Puffer A: The Schick engine, with period 12. By itself, leaves no exhaust.
Puffer B: Period 12 engine found by David Buckingham. By itself, produces
a tub every 24 generations.
Puffer C: Period 20 engine found by Bill Gosper. By itself, it becomes a
period 140 puffer which leaves much debris (after about 2000
generations).
Puffer D: Period 20 engine found by Robert Wainwright. By itself, produces
a loaf every 40 generations.
Puffer E: Period 32 engine found by Bill Gosper. By itself, produces 4
blinkers and a pair of bookends every 128 generations. This was
the first puffer train found.
Based on these puffer engines, spaceships can be constructed which have
periods of 12, 20, 24, 32, 36, 40, 48, 60, 64, 72, 80, 84, 96, 120, 128,
and 140. These higher periods are created by perturbing the puffer debris
produced by the basic puffer engine with extra standard spaceships. The
most useful results to obtain are single gliders (rakes), since then the
gliders can easily be combined to produce other useful results. I do not
want to devote much room here for cataloging all these puffer trains since
most of the results are old and are easy enough to rediscover. Two examples
of puffer trains are given here, and several others are shown in the rest
of this article.
[Period 32 backwards glider puffer]
.................................OOOOO.
.............OOOO................O....O
.O..........OOOOOO...............O.....
O..........OO.OOOO................O....
O.....O.....OO.........................
OOOOOO.................................
.......................................
.......................................
....OOO................................
.....OO................................
..O....................................
.OO....................................
OO.....................................
.OO....................................
.......................................
.......................................
.......................................
.OO....................................
OO.....................................
.OO....................................
..O....................................
.....OO................................
....OOO................................
.......................................
.......................................
OOOOOO.................................
O.....O.....O..........................
O..........O...........................
.O.........O.....O.....................
...........OOOOOO......................
[Period 60 backwards glider puffer]
..................O....................
.................O.....................
.................O...O.................
.................OOOO..................
.......................OOO.............
.......................OO.OO...........
.......................OOO.............
.O........OO.....OOOO..................
O........OOOO....O...O.................
O...O...OO.OO....O.....................
OOOO.....OO.......O....................
.......................................
.......................................
.......................................
....O..................................
..OO...................................
..O....................................
..O....................................
...O.............................O.....
................................O......
................................O.....O
.O..............................OOOOOO.
O......................................
O...O..................................
OOOO.............OOOO..................
.................O...O.................
.................O.....................
..................O....................
By combining spaceships using reactions between gliders produced by the
puffers, you can also generate the least common multiples of these periods.
The simplest way of doing this is simply by running the two spaceships side
by side. Better examples can be constructed by having the spaceships interact
slightly in some manner.
All of the above results only produce a limited number of periods for puffer
trains and spaceships. Dean Hickerson wondered whether it was possible to
produce a puffer train which had an arbitrarily large period. This turned
out to be possible, and now there are three different methods known to make
these puffers. Most of the remainder of this article will describe these
methods in detail.
The first two methods can only produce puffers whose periods are a base
period times any power of two. For this reason, these are called "period
doubling" methods. One of these two methods was thought of by Dean Hickerson,
and the other method was thought of by Paul Callahan.
Dean Hickerson's method of period doubling uses glider puffers of period N.
Three of these are used to collide triples of gliders together to produce a
MWSS which then travels with the puffers. The next time a triple of gliders
arrive together to attempt to create another MWSS, they collide with the
already present MWSS. This collision destroys the spaceship and two of the
gliders, letting the third glider escape. This produces a puffer of period 2N.
Since the creation of a spaceship requires gliders which travel both forwards
and backwards, two types of such puffers are used in order to repeat this
process for larger periods. The first type produces a glider which travels
in the forwards direction, whereas the second type produces a glider which
travels in the backwards direction. (Actually, only one type of puffer is
required if a two-glider reaction known as a "kick-back" is used to reverse
the direction of a glider. But doing this requires using another copy of the
puffer, and so is less efficient.)
The following is a period 80 forwards glider puffer train composed of
three sets of period 40 glider puffers, and a trailing spaceship to clean
up the final reaction. Two of the period 40 glider puffers are forwards
glider puffers, and the third period 40 glider puffer is a backwards glider
puffer.
[Period 80 puffer train producing forwards gliders]
$$$$$$...OOO$$$........
$$$$$$..OOOOO$$$.......
$$.........O$$$.OO.OOO$$$.......
$........OO.......O...O$.....OOO$..OO$$$$
$.......OOOO.....O$.........OOOOO$$$$$...
$......OO.OO.....O....O$...OO.OOO$$$$$...
$.......OO.......OOOOO$.....OO$$$$$......
$$$$$$$$$$....
$$..O$$$$$$$$.
$$....O$$.....OO$$.....OO$$.....
$$OO..O....OO$$OO$$...OO.OOOO$$.
$.........O.....O.OOO..O$........O.OO$$..OOOOOO$$.
$........OO..O.O..OOOOO.O$..OO......O$$...OOOO$$..
$.........OO...O.....OO.OO$.OO....OOO$$$$.........
$$OOO.......O..O$...O...OOO$$$$$
$$$$$.O$$$$$..
$$$.OO$........O$$$$$..
$........OO$$$$$..OO...OOOOO.OO$.........
$.......OOOO....OOOO$$$$..OOO..OO..OOOO$$
$......OO.OO....O...O$$$$..OOOO..O...O$$.
$.......OO......O$OOOO$$$...O.OOO$$......
$$......O..O.....OOOOOO$$$...OO$$........
$$$....OO.OOOO$$$$$$...
$$$.....OO$$$$$$.......
$$$$$$$$........OOO$...
$$$$$$$$.......OOOOO$..
$$$$$$$$......OO.OOO........OO..
$$$$$$$$.O.O...OO.........O....O
$$$$$$$$.OO$....O......
$$$$$$$$..O$....O.....O
$$$$$$$$$.......OOOOOO.
$$$$$$$$$$....
$$$$$$$$$$....
$$$$$$$$.........OO$...
$$$$$$$$........OO.OO$.
$$$$$$$$.........OOOO$.
$$$$$$$$$OO$..
$$$$$$$$$$....
$$$$$$$$$$....
$$$$$$$$.....OOO$......
$$$$$$$$.....O$........
$$$$$$$$......O$.......
$$$$$$$$$$....
$$..OO.......OOOOO$$$.......OOO$$........
$$.OO.OO.....O....O$$$........O$$........
$$..OOOO.....O$$$$..O$$.........
$$...OO.......O...O$$$$$$.......
$$$....O$$$$$$.........
$$$$$$$$$$....
$$.....OOO$$O$$......OOO$$......
$$....OO...O$........OOO$$....O$$........
$$...OO..O.O$....O..O.OOOO$$...O$$.......
$$....O.....O.....OO.....O.O.....OOO$$$$$
$$.....OO..O......OOO....O.......OOO$$$$$
$$.........O$....OO.O...OO$$$$$.
$$.......O$.........OO..O$$$$$..
$$$.O..O$.OO$$$$$......
$$..OO......O$$$$$$$...
$$.OO.OO....O...O$$$$$$.........
$$..OOOO....OOOO$.........OOOOO.......OOO.....O$$$
$$...OO$$........O....O......O.....O...O$$........
$$$$$...O$..O...O$$$...
$$$$$....O...O$.O....O$$........
$$.OO$$$...O$...OOOOO$$.........
$.........O....O$$$$$$$.........
$........O$$$$$$$$.....
$........O.....O$$$$$$$.........
.O..O.....OO......OOOOOO$$$$$$$$
O........OOOO$$$$$$$$$.
O...O...OO.OO$$$$..OOO..OOO.....O$$$.....
OOOO.....OO$$$$....O$.O.O$$$....
$$$$$......O...OO..OOO.OO$$$....
$$$$$$....OO$$$........
......OO$$.......OOO$$$$$$......
....O....OOO...OO$........OOO$$$$$$......
..OO....OOOOO...O.OOO$.OO..O..OO$$$$$$...
..O......OO..O...OOO$.......O..O$$$$$$...
..O.........OO....O$.......O...O$.........OOOOOO$$$........
...O..O$$$..O$$O.....O$$$.......
.....O$$.........OOOO$$.O$$$$...
$$$..O...OO$$...O....O$$$.......
.O..O$$.....O...O$$........OO$$$.........
O.........OO$.......O$$$$$$$....
O...O....OO.OOO$....O....O$...O$$$$$.....
OOOO......OOOOO$....OOOOO$..O...O$$$$$...
$.OOO$$$.O$$$$$........
$$$$.....O....O$$$$$...
$$$$.....OOOOO$$$$$....
The following is the other type of puffer required to continue the process.
This is a period 80 backwards glider puffer. This also uses the same three
period 40 glider puffers as in the above period 80 glider puffer, but the
reactions of the three gliders are slightly different. Here there are three
trailing spaceships instead of just one to clean up the debris.
[Period 80 puffer train producing backwards gliders]
$$$$$.OOOOO$$$$..
$$$$$.O....O$$$$.
$.......OOO$$$.O$$$$......
......OOOO......OOOOO$....OOOOO$..O...O$$$$.
......O...O....OO.OOO$....O....O$...O$$$$...
......O.........OO$.......O$$$$$$..
.......O..O$$.....O...O$$........OO$$.......
$$$........O$$........O....O$$.....
$$$$$$......O$$$.
.........OO...OO$$$$$O.....O$$.....
........O.O......O$........O..O$$......OOOOOO$$......
........O......O..O$....OO.OOOO$$$$$........
........OOO.......OO$.........O$$$$$........
$.......OO$......OOOO$$$$$.........
$$$.....O..O$$.......OO$$$
$$$$$$......O.O$$.........
$$$$$$.OO.....O$$.........
......OOOO.....OO$$$$...OO.O..OOO$$.........
......O...O...OO.OO$$$$..O..OO$$$..
......O........OOOO$$$$.....OO$$$..
.......O..O.....OO......OOOOOO$$$...O$$$....
$$....O.....O$$$$$$.......
$$....O$$$$$$$...
$$.....O....O$$$$$$.......
$$.......OO$$$$.O.....OOOOO$.......
$$$$$$.........O......O....O$......
$$$$$$.........OOO....O$$.
$$$$$$$.......O...O$......
$$$$$$$.........O$........
$$$$$$$$$........
$$$$$$$$..OOOOO$.
$$$$$$$$..O....O$
$$$$$$$$..O$.....
$$$$$$$$...O...O$
$$$$$$$$O....O$..
$$$$$$$.........O$........
$$$$$$$.........OOO$......
$$$$$$$$$........
$$$$$$$$$........
$$$$$$$$$........
$$$$$$$$$........
$$$$$$$$$........
$$$$$$$$OOOOO........OO...
$$$$$$$$O....O.......OO...
$$$..OOO$$$$.....O$.......
$$.OOOO......OOOOO$$$$.....O...O.........O..
$$.O...O....OO.OOO$$$$.......O.........O...O
$$.O.........OO$$$$$.........O.....
$$..O..O$$$$$$......O....O
$$$$$.........O$......OO$....OOOOO.
$$......O$$$..OO$.....O.O$.........
$$....OOO$$$.O.O$.....O$..O........
$$...O...O.........O$$$$.........O...O......
$$...O....OOO....OO$$$$.........O$.
$$...OO.O.OOO.....O.O..O$$$$....O....O......
$$.....O...OO......OO..O$$$$....OOOOO.......
$$......O.O$$$$$$.........
$$$$$$$$$........
$$$$$$$$$........
$$.OOOO.....OO$$$....OO$$$
$$.O...O...OO.OO$$OOO.........O.O$$.........
$$.O........OOOO$.........OOOOO........O$$$.
$$..O..O.....OO$.........OO.OOO$..OOOOO$$...
$$$$$...OO$.....O....O$$..
$$$$$$$O$$.......
$$$$$$$.O...O$$..
$........OOOOOO$$$$.........O$$....
$........O.....O$$$$$$$...
$........O$$$$$$$.........
OOOO.....OO........O....O$$$.OO$$$$
O...O...OO.OO........OO$$$...O.O...OO...OOO$$........
O........OOOO$$$$...O.........O...O$$.......
.O..O.....OO$$$$$..OO....O$$.......
$$$.......O$$.........O.O$$........
$.......O$........OOO$$$$$.........
...OO.......O...O.O$......OOOOO$$$$$........
..O.O...OO...OOOO.O.OO$....OO.O.OO$$OO$$$...
..O$.OO.OOO.O$.....OO...O$........O....O$$$.
..OOO........OO....OO$......OO...O$.......O$$$.......
$.........O$.........O.O$........O.....O$$$.
$$$........OO$$OOOOOO$$$..
$$$$$$$$$........
$.OOO$$$$$$$$....
OOOO......OOOOO$....OOOOO$$$$$$....
O...O....OO.OOO$....O....O$$$$$$...
O.........OO$.......O$$$$$$........
.O..O$$.....O...O$OOOOO$$$$........
$$$..O$..O....O$$$$.......
$$$$.....O$$$$$..
$$$$......O...O$$$$.......
$$$$........O$$$$.........
This process can be repeated indefinitely to produce glider puffers of
periods which are of the form 40 * 2^N. For example, to produce the forwards
and backwards glider puffers of period 160, use two copies of the above
period 80 forwards glider puffer and one copy of the period 80 backwards
glider puffer. Position them so that the three gliders react in the same
manner as in the back of the period 80 puffers, and add the spaceships at
the back to clean up the reactions just as in the period 80 puffers.
Dean Hickerson's method of period doubling is very expensive in terms of
basic components. Since three puffers of period N are required for period
2N, then for period M*2^N, a total of 3^N puffers of order M are required,
where M is the order of the basic glider puffer. Dean Hickerson later
found a method for producing a standard spaceship using just two gliders
and a perturbing spaceship. This reduces the number of puffers needed from
3^N to 2^N. Dean stopped working on his method when he heard about Paul
Callahan's construction method.
Paul Callahan's method of period doubling is more complicated in concept,
but requires only a linear increase in puffers for each doubling. His
method uses a row of beehives along with sets of three gliders which produce
the moving spaceship. A set of three new gliders is produced every time one
of the beehives is detected (and deleted) by another glider. When the
created spaceship is destroyed by its interaction with another set of three
gliders, a new beehive is produced at the back. Since the produced beehives
are produced half as often as the consumed ones, the period is doubled.
The following shows how a period 48 beehive puffer train is doubled to form
a period 96 beehive puffer. At the left is a period 48 beehive puffer train.
The rest of the construction is used to delete those beehives and lay down
new beehives with twice the separation. You can repeatedly add the rest
of the construction to the end to similarly double the separation of the
beehives as often as desired. The final beehives can easily be suppressed
by using a spaceship to perturb the debris before it forms the beehive.
For larger periods, extra gliders also begin to escape from the puffers,
which can also be suppressed with spaceships. This will produce a true
spaceship with an arbitrarily large period of the form 48 * 2^N.
[Period 96 beehive puffer train]
$$$$$$$$$$$$$$$$.......OO$$$$$$$$$$....
$$$$$$$$$$$OOOOOO$$$$.........O....O$$$$$$$$$$..
$$$$$$$$$$$O.....O$$$$.......O$$$$$$$$$$........
$$$$$$$$$$$O$$$$$...O.....O$$$$$$$$$$..
$$$$$$$$$$$.O....O$$$$.......OOOOOO$$$$$$$$$$...
$$$$$$$$$$$...OO$$$$$$$$$$$$$$$........
$$$$$$$$$........OOOO$$$$$.O..O$$$$$$$$$$$......
$$$$$$$$$........O...O$$$$.........O$$$$$$$$$$$$
$$$$$$$$$........O$$$$$...O...O$$$$$$$$$$$......
$$$$$$$$$.........O..O..OO........O.O$$$....OOOO$$$$$$$$$$$.......
$$$$$$$$$$....OOO.........OO$$$$OOO$O$$$$$$$$$$.
$$$$$$$$$.........O..O..OO.........O$$$$.OO.OO.........OO$$$$$$$$$.........
$$$$$$$$$........O$$$$$.........OOO$OO$$$$$$$$$$
$$$$$$$$$........O...O$$$$.........OOOO$$$$$$$$$$$.......
$$$$$$.......OOOOOO$$.....OOOO$$$$$O...O$$$$$$$$$$$......
$$$$$$.......O.....O$$$$$.........O.O$......O$$$$$$$$$$$$
$$$$$$.......O$$$$...OO$$.OO$.......O..O.........OOOO$.........O$$$$$$$$...
$$$$$$........O....O$$$......OO.OOOO$.......O$$$OOOOOO$.........OO$$$$$$$$.
$$$$$$$OO$$$.........OOOOOO$$$$.......OO.OOOO$........OO$$$$$$$$..
$$$$$.....OOOO$$$$$...OOOO$$$$.........OO$$$$$$$$$$......
$$$$$.....O...O$$$$$$$$$$$$$$$$$$$$$...
$$$$$.....O$$$$$$$$$.....O.O....O$$$$$$$$$$$....
$$$$$......O..O..OO........O.O$$$$$$$.......OO...OO$$$$........O$$$$$$.....
$$$$$$.OOO.........OO$$$$$$$.......O....O.O$$$$........OO$$$$$$...
$$$$$......O..O..OO.........O$$$$$$$$$$$$$...OO$$$$$$....
$$$$$.....O$$$$$$$$$$$$$$$$$$$$$.......
$$$$$.....O...O$$$$$$$$$$$$.....OO$$$$$$$$......
$$$$$.....OOOO$$$$$$$$$$$O.O$..O.O$$..O$$$$$$...
$$$$$$$$$O.O$$$$$$$.......OO$....O$$..O.O$$$$$$.
$$$$$$........OO$$.OO$$$$$$$.......O$$$........OO$$$$$$..
$$$$$$.......OO.OOOO$.......O$$$$$$$$$$$$$$$$$$.
$$$$$$........OOOOOO$$$$$$$$$$$$$$$$$$$.........
$$$$$$.........OOOO$$$$$$$$$$$$$$$$$$$........O.
$$$$$$$$$$$$$$......O$$$$$$$$$$$$...O.O
$$$$$$$$$$........O.O$$$....OO$$$$$$$$$$$$...O.O
$$$$$$$$$$.........OO$$$....O.O$$$$$$$$$$$$...O.
$$....OOOO$$$$$$$$.O$$$$$$$$$$$$$$$$...
$$...OOOOOO$$$$$$$$$$$$$$$$$$$$$$$$....
$$..OO.OOOO$$$$$$$$$$$$OO$$$$$$$$$$$$..
$$...OO$$$$$$$$$$$$...O.O$$$$$....O.O$...O$$$$$.
$$$.........O$$...O$$...O$$...O$....O.O$$.O$$$$$.....OO$...O.O$$$$.........
.O..O$$$...O.O$$.O.O$$.O.O$$.O.O$....OO$$$$$$$.......O$....OO$$$$$
O$$$.......O.O$$.O.O$$.O.O$$.O.O$....O$$$$$$$$$$$$$$.....
O...O.......O$$......O$$...O$$...O$$...O$$$$$$$$$$$.....O$$$$.....
OOOO....O...OOO$$$$$$$$$$$......OO$$$$$$$$$..O...O$$$$...
......OO.....OO$$$$$$$$$$$.....O.O$$$$$$$$$.O$$$$........
......OOO......O$$$$$$$$$$$......O$$$$$$$$$.O....O$$$$...
......OO.....OO$....O$$$$$$$$$$$$$$$$$$$....OOOOO$$$..OO$
OOOO....O...OOO...O........OOO.O$$$$$$$$$$$$$$$$$$$$$$$$.
O...O.......O....O.O.......O....O$$$$$$$$$$$$$$$$$$$$$$........OOO.........
O$......O.O........OOOO$$$$$$$$.OO$$$$$$$$$$$$$$$........
.O..O$$....O.O$$$$$$$$O.O$$$$$$$$$$$$$$$........
$....O...O$$$$$$$$$.....O$$$$$$$$$$.........OO$$$...OOOOOO........
$...O$$$$$$OO$$$$$$$$$$$$$$........O.O$$$..O.....O.......
$...O....O$$$$$...O....O$$$$$$$$$$$$$$......O$$$....O$...
$...OOOOO$$$$$...O$$$$$$$$$$$$$$$$$$........O....O.......
$$......O$$$$....O.....O$.......OO$$$$$$$$$$$$$$$$.....OO.........
$$....O...O$$$$..OOOOOO$.......O.O$$$$$$$$$$$$$$$$$......
$$...O$$$......OO$$$....O$$$$$$$$$$$$.OO$$$$$...
$$...O....O$$$OOOO$$$$$$$$$$$$$$$.....O.O$$$$$..
$$...OOOOO$$$OO.OO$$$$$$$$$$$$$$$.....O$$$$$....
$$$$$.........OO$$$$$$$$$$$$$$$$$$$$$..
$$$$$$.....O.O.........OO$$$$$$$$$$$$$$$$$$$....
$$$$$$....OO..O.......O.O$$$$$$$$$$$$$$$$$$$....
$$$$$$.....O.O$O$$$$$$$$$$$$$...OO$$$$$.........
$$$$$.........OO$$$$$$$$$$$$$.........OO$O.O$$$$$........
$$$$$........OO.OO$$$$$$$$$$$$$......OOOO.........O$$$$$$
$$$$$.........OOOO$$$$$$$$$$$$$.....OO.OO$$$$$$$
$$$$$$OO$$$$$$$$$$$$$.......OO$$$$$$$..
$$$$$$$$$$$$$$$$$$$$$$$$$$$...
$$$$$$$.OO$$$$$$$$$$$$$...OO$$$$$$.....
$$$$$$$OO.OOOO$$$$$$$$$$$O..O$....OO$$$$$$......
$$$$$$$.OOOOOO$$$$$$$$$$.........O$.......O$$$$$$........
$$$$$$$..OOOO$$$$$$$$$$$O...O.......O......O$$$$$$.......
$$$$$$$$$$$$$$$$$$......OOOO....O...OOO$$$$$$$..
$$$$$$$$$$$$$$$$$$$..OO.....OO$$$$$$$..
$$$$$$$$$$$$$$$$$$$..OOO......O.......O..O$$$$$$
$$$$$$$$$$$$$$$$$$$..OO.....OO.......OOO.O$$$$$$
$$$$$$$$$$$$$$$$$$......OOOO....O...OOO........O.O$$$$$$.
$$$$$$$$$$$$$$$$$$......O...O.......O.........O$$$$$$....
$$$$$$$$$$$$$$$$$$......O$$$$$$$$......
$$$$$$$$$$$$$$$$$$.......O..O$$$$$$$$..
$$$$$$$$$$$$$$$$$$$......OOOO$$$$$$$...
$$$$$$$$$$$$$$$$$$$.....OOOOOO........O.OO$$$$$$
$$$$$$$$$$$$$$$$$$$....OO.OOOO.........OO$$$$$$.
$$$$$$$$$$$$$$$$$$$.....OO$..O$$$$$$...
$$$$$$$$$$$$$$$$$$$$$$$$$$$...
$$$$$$$$$$$$$$$$$$$$.....OO$$$$$$......
$$$$$$$$$$$$$$$$$$$$....OO.OO$$$$$$....
$$$$$$$$$$$$$$$$$$$$.....OOOO$$$$$$....
$$$$$$$$$$$$$$$$$$$$......OO$$$$$$.....
Both of the above methods of making arbitrarily large period spaceships
only produce a few of the possible periods. Starting with a basic beehive
or glider puffer train, the methods only produce periods which are a power
of two times the base period, which is a geometric progression.
The newest method of making arbitrarily large periods is more versatile
than either of the previous methods. For instead of a geometric progression,
periods in an arithmetic progression can be constructed. The concepts and
constructions for this method were the work of several people. The base
blinker puffers were found by Robert Wainwright and myself, the impetus
for playing with them was provided by Bill Gosper, the glider reactions that
are needed to make it work were found by Dean Hickerson, and the final
construction method for making the large period puffers was by me. I will
spend most of the rest of this article describing this method in detail.
The method uses one of two different blinker puffers, and an interesting
reaction which burns the blinkers cleanly at a rate faster than the
blinkers are produced. These blinker puffers have been shown in previous
articles, but I will show them again here for convenience. The first one
was found by Robert Wainwright, and the second one by myself. These both
produce identical output, consisting of a row of blinkers, with a period
of 8.
[Two period 8 blinker puffers]
.OO...... ............OO...
OO.OOO... ...........OO.OOO
.OOOOO... ............OOOOO
..OOO.... .............OOO.
......... .................
......... ..........OOO....
.OOOOO... ..OO.O.OOOO.O....
.O....... .O...............
.O....... OO.OO............
..O...... .OOO.OO.O........
....O.... ..O....O.........
......... .........O.......
......... ..O....O.........
...OO.... .OOO.OO.O........
..OO.OOOO OO.OO............
...OOOOOO .O...............
....OOOO. ..OO.O.OOOO.O....
..........OOO....
.................
.............OOO.
............OOOOO
...........OO.OOO
............OO...
The puffer on the left is generally more convenient because of its smaller
size, but the puffer on the right does have some advantages, as we will see.
The reaction which burns the blinkers can be initiated by adding one ON cell
to the end of a row of produced blinkers to turn the last blinker into a
set of traffic lights at the end. This will leave some debris at the end,
but the rest of the blinkers will then burn cleanly. A reaction of this
kind where a repeating unit burns is called a "fuse" (whether or not the
burning produces any debris). The burning used here is a clean blinker fuse.
A way to ignite the blinkers without leaving any debris at all is to hit one
of the two end blinkers symmetrically with two gliders. These gliders will
also ignite the blinker fuse if they hit any of the other blinkers in the
row in the same manner, but in those cases one or more blinkers at the end
of the row will be left. For example, hitting the fifth-from-the-end blinker
will ignite the fuse but leave three blinkers remaining at the end of the row.
The following shows the gliders hitting the last blinker in the row.
[Two gliders cleanly igniting blinkers produced by blinker puffer]
.OO....................
OO.OOO.................
.OOOOO................O
..OOO...............OO.
.....................OO
.......................
.OOOOO.................
.O......O...O...O...O..
.O......O...O...O...O..
..O.....O...O...O...O..
....O..................
.......................
.....................OO
...OO...............OO.
..OO.OOOO.............O
...OOOOOO..............
....OOOO...............
Once the fuse is lit, it burns with a period of 18 at a speed of 2c/3.
When the fuse reaches the puffer engine, the reaction disconnects and the
blinker puffer begins to lay down a new row of blinkers. The disconnected
reaction can have one of three different outcomes (for each puffer). The
outcome is dependent on how many blinkers are present at the time the blinkers
are ignited. Some of these reactions leave some debris, some die out quickly,
and some die out after making a large debris cloud. The one shown above
terminates in a large debris cloud which dies out. This is the most useful
behavior since the debris can be tweaked by spaceships to do useful things
before it dies.
One of the three reactions for my blinker puffer is vigorous and almost
reignites the new row of blinkers being laid down by the puffer train.
It turns out that most reactions that reach the row of blinkers fail to
reignite it. Even if the row is reignited, there are three different
outcomes and so there is a 2/3 chance that the wrong kind of outcome will
then occur. If the reaction happens to work, however, then a large period
puffer (or spaceship) has been found.
By perturbing the vigorous reaction from my blinker puffer with two LWSSs
I found the first large period puffer train based on these ideas. This is
a relatively dirty puffer with period 292. The reaction products are two
blinkers, two blocks, two loaves, two boats, six beehives, and four gliders.
[Dirty period 292 puffer train]
.......................OOOO.
.......................O...O
...............O.......O....
.............O...O......O..O
............O...............
............O....O..........
............OOOOO...........
............................
............................
...........O................
..OO.O...OO.OO..............
.O..OOOOO.O.................
.O..O.OO.OO.................
.OO...OOO.OO........OO.O..OO
...O......OO.......O.O.OOOOO
..........OO...OOO.O........
...O......OO.......O.O.OOOOO
.OO...OOO.OO........OO.O..OO
.O..O.OO.OO.................
.O..OOOOO.O.................
..OO.O...OO.OO..............
...........O................
............................
............................
............OOOOO...........
............O....O..........
............O...............
.............O...O......O..O
...............O.......O....
.......................O...O
.......................OOOO.
One curious thing about this puffer train is that its period of 292 is
NOT a multiple of 8. Instead, 292 is 4 (mod 8). This is highly unusual.
Usually, puffer output from a compound reaction must be a multiple of the
base reaction. In this puffer, though, it is not. How this is possible
is explained by the fact that only the puffer output from the base engine
is of period 8, whereas the base engine itself is actually only of period 4.
When the fuse reaches the puffer engine and disconnects, the row of blinkers
is restarted with a phase shift of 4 generations. This allows puffer trains
to exist which are a multiple of 4 instead of a multiple of 8. This feature
is what makes this blinker puffer useful even though it is larger. Robert
Wainwright's blinker puffer engine is of period 8, and so can only be used
to produce puffer output which is a multiple of 8.
--------------------- [Continued in next mail article] ----------------------
David Seal
db...@pdact.pd.necisa.oz.au (David I. Bell) writes:
>This is the sixth and last in a series of articles concerning Conway's Game
>of Life. ...
First, I'd like to thank David Bell for producing this fascinating series of
articles. It's one of the best things I've ever seen on Usenet, and I hope
I'm not going to be suffering withdrawal symptoms in 2 weeks' time :-)
Secondly, a request: would it be possible to post the search programs
somewhere? I've had a quick go at writing such a program myself: it wasn't
unsuccessful, in the sense that it found some of the simpler and shorter
period spaceships in the articles. However, it was clearly a lot slower than
the programs used for the results in the articles, and I would be very
interested in seeing how the search was optimised.
David Seal
ds...@armltd.co.uk
All opinions are mine only...