From: dbell@pdact.pd.necisa.oz.au (David I. Bell)
Subject: Spaceships in Conway's Life (Part 3a)
Organization: NEC Information Systems Australia, Canberra
Date: Fri, 11 Sep 1992 01:11:05 GMT
Keywords: life

		Spaceships in Conway's Life (Part 3)
			by David I. Bell
			dbell@pdact.pd.necisa.oz.au
			11 Sep 1992


This is the third in a series of articles concerning Conway's Game of Life.
In this article, I will survey the results for all the known period 3
spaceships, and give some applications of them.  All period 3 spaceships
must be orthogonal, and must travel at the speed of c/3.  This follows
from the speed restrictions mentioned in my first article.

When Dean Hickerson started looking for spaceships using his search program,
the first spaceships he found were of period 2.  But he soon also tried
looking for period 3 spaceships.  In August 1989 he found a grammar for
constructing an infinite number of short wide c/3 period 3 spaceships.
(This grammar is used similarly to the grammar for period 2 spaceships
that was in my previous article.)  These period 3 spaceships were the first
orthogonal spaceships found which didn't travel at the "normal" speed of c/2.

In Dean's grammar, the components are labeled using letters, or letters
followed by either a single quote or a double quote (e.g., A, A', and A").
Any three components with the same letter are related, and represent the
same section of a period 3 spaceship in three successive generations.
Therefore, if component A appears in generation 0 of a spaceship, then
component A' must appear in the same location in generation 1, and
component A" must appear in the same location in generation 2.

A component name followed by a dash represents the mirror image of a
component.  The mirroring is done by reflecting the component across a
horizontal line.  For example, component B"- is the mirror image of
component B".

The components in Dean's grammar are the following.

 [A]     [A']    [A"]   [B]     [B']    [B"]     [C]       [C']       [C"]
 ..O.    ..O.    ..O    ..O.    ..O.    ..O    ...O...    .......    ...O...
 .O.O    .O.O    OO.    .O.O    .O.O    OO.    ..O....    .OOO...    ..O.O..
 .O.O    OO..    OO.    .O.O    OO..    OO.    .OO....    .OOO...    ..O....
 .O..    ..O.    ..O    .O..    .O..    ..O    ...O.O.    ...OO..    ..O...O
 ....    OO..    O..    OO..    O.O.    O..    .OOO..O    .O.O.OO    ....O.O
 OO..    OOO.    O.O     X       X      X      .OO..O.    .O.O...    .OO..O.
  X       X      X                             .......    O......    .O.....
                                               OOO....    OOO....    OO.....
                                               .O.....    O......    .O.....
                                                 X          X          X


  [D]      [D']     [D"]     [E]     [E']    [E"]     [F]     [F']    [F"]
   X         X        X       X       X       X        X        X       X
 ..O.O    ......    ..O..    .O.O    ....    .O.O    .OO..    .O.O    ..O..
 ..OO.    ...OO.    ...OO    O.O.    O..O    ..O.    ..O..    ..O.    ....O
 .....    ..O..O    .O...    OOO.    O.O.    OO..    ..O.O    .OO.    ..OO.
 OO.OO    .OOO..    .O.OO    ....    O...    .O..    ..OO.    ....    ..OO.
 OO...    O..O..    O..OO    .O.O    .O..    .OOO    .OO..    O..O    .....
 O....    O..O..    O..O.      X       X       X     OO...    O...    OO...
 OO.O.    .OO...    .OOO.                            X        X        X
 .O.O.    ....O.    .O...
   X        X         X


 [G]     [G']    [G"]    [H]       [H']      [H"]      [I]     [I']      [I"]
  X       X       X        X          X        X        X        X        X
 O..O    O...    O.O    ..OO..    ...O.O    ...O..    .O.O.    .O...    .OOO..
 OO..    OOO.    OO.    ...O..    ....O.    .....O    .....    O....    .O....
 .O..    ....    O..    ...O.O    ...OO.    ...OO.    OOO..    O.O..    OO....
 .OOO    .O.O    .O.    ...OO.    ......    ...OO.    OO...    O.O..    .O....
   X       X       X    .OOO..    ..O..O    ......    .....    .OOO.    ......
                        O.O...    .O....    OOO...    ..OOO    ..O.O    .....O
                        O.O...    OO....    OOO...    .O.OO    .O..O    .OOOO.
                        O.....    .O....    ......    .O...    OO...    .OO...
                        .O....    .OOO..    .O.O..    .O...    .....    ......
                          X         X         X       .....    OO...    .O.O..
                                                      OO...    OOO..    .O.O..
                                                       X        X        X


   [J]         [J']        [J"]       [K]     [K']      [K"]
   X            X          X           X        X        X
 ..O.....    ..OO....    .O.O....    .O.O.    .O...    .OOO..
 ..OOO...    ..OO....    ....O...    .....    O....    .O....
 ..O.....    ...O....    ...O....    OOO..    O.O..    OO....
 ........    ..O.....    ..OOO...    OO...    O.O..    .O....
 OO...O..    .O..OO..    .O.OO...    .....    .OOO.    ......
 OOOOO...    O...OOOO    OO..O..O    ..OOO    ..O.O    .....O
 OO...O.O    .O....O.    ........    .O.OO    .O..O    .OOOO.
 ..O..OO.    ...O.OOO    .O...OOO    O....    OO...    .OO...
 OO.O....    .OO.....    .O.OOO..    O....    .....    .OO...
 .O......    .OO..O..    .O..O...    .....    O....    .O....
 ..OOO...    ...OO...    ..OOO...    OOO..    OOO..    OO....
 ........    ........    ........    .O...    O....    .O....
 ..OOO...    ...OO...    ..OOO...      X        X        X
 .O......    .OO..O..    .O..O...
 OO.O....    .OO.....    .O.OOO..
 ..O..OO.    ...O.OOO    .O...OOO
 OO...O.O    .O....O.    ........
 OOOOO...    O...OOOO    OO..O..O
 OO...O..    .O..OO..    .O.OO...
 ........    ..O.....    ..OOO...
 ..O.....    ...O....    ...O....
 ..OOO...    ..OO....    ....O...
 ..O.....    ..OO....    .O.O....
   X            X          X


The components are strung together by stacking them above each other,
similarly to the way that period 2 components are stacked.  (The X's
indicate the horizontal alignment of components, and should be removed.)

The rules which give the allowed sequences of components to make a valid
spaceship are the following.

The sequence must begin with A, A', A", B, B', B", C, C', or C".

The sequence must end with A-, A'-, A"-, B-, B'-, B"-, C-, C'-, or C"-.

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    |  D    E
                        A'   |  D'   E'
                        A"   |  D"   E"
                        I    |  D
                        I'   |  D'
                        I"   |  D"
                        D-   |  A-   I-
                        D'-  |  A'-  I'-
                        D"-  |  A"-  I"-
                        E-   |  A-
                        E'-  |  A'-
                        E"-  |  A"-
              B    F-   H-   |  E-   G'-  H"-  I    K
              B'   F'-  H'-  |  E'-  G"-  H-   I'   K'
              B"   F"-  H"-  |  E"-  G-   H'-  I"   K"
    E    G'   H"   I-   K-   |  B-   F    H
    E'   G"   H    I'-  K'-  |  B'-  F'   H'
    E"   G    H'   I"-  K"-  |  B"-  F"   H"
                   C    K    |  J
                   C'   K'   |  J'
                   C"   K"   |  J"
                        J    |  C-   K-
                        J'   |  C'-  K'-
                        J"   |  C"-  K"-
                   D'   G-   |  F-
                   D"   G'-  |  F'-
                   D    G"-  |  F"-
                        F    |  D'-  G
                        F'   |  D"-  G'
                        F"   |  D-   G"


The simplest spaceship which can be constructed by these rules is A E B-,
which is shown below.  This spaceship has 25 ON cells in every generation.
There is no known period 3 spaceship which has fewer ON cells than 25.
(Any such spaceship must be spread out very thinly.)

[Smallest known period 3 spaceship (speed c/3)]
 ..O..
 .O.O.
 .O.O.
 .O...
 .....
 OO...
 .O.O.
 O.O..
 OOO..
 .....
 .O.O.
 .OO..
 ..O..
 ..O.O
 ..O.O
 ...O.


Another example spaceship created using these rules is C J C-, which
represents the following symmetrical spaceship.

[One of many period 3 spaceships constructed by the above grammar (speed c/3)]
 ...O....
 ..O.....
 .OO.....
 ...O.O..
 .OOO..O.
 .OO..O..
 ........
 OOO.....
 .O......
 ..O.....
 ..OOO...
 ..O.....
 ........
 OO...O..
 OOOOO...
 OO...O.O
 ..O..OO.
 OO.O....
 .O......
 ..OOO...
 ........
 ..OOO...
 .O......
 OO.O....
 ..O..OO.
 OO...O.O
 OOOOO...
 OO...O..
 ........
 ..O.....
 ..OOO...
 ..O.....
 .O......
 OOO.....
 ........
 .OO..O..
 .OOO..O.
 ...O.O..
 .OO.....
 ..O.....
 ...O....


Dean Hickerson also tried looking for long and thin period 3 spaceships.
He found two basic spaceships, which are given below.  They have the same
front ends.  Dean has named the leftmost spaceship the "turtle".

[The "turtle" and another related period 3 spaceship (speed c/3)]
 .OOO.......O        .........O...
 .OO..O.OO.OO        ........O.O..
 ...OOO....O.        ........O....
 .O..O.O...O.        .OOO....O...O
 O....O....O.        .OO..O....O.O
 O....O....O.        ...OOO.OO.OO.
 .O..O.O...O.        .O..O.O.OOO..
 ...OOO....O.        O....O.....O.
 .OO..O.OO.OO        O....O.....O.
 .OOO.......O        .O..O.O.OOO..
                     ...OOO.OO.OO.
                     .OO..O....O.O
                     .OOO....O...O
                     ........O....
                     ........O.O..
                     .........O...


For many people, the turtle spaceship is the most aesthetically pleasing
new spaceship that has been found so far.  Besides being pretty, it has a
feature which makes it useful.  In generation 2, it produces a two bit
spark at the back.  This spark can be used in several ways.

The first use of the spark is that it makes a good attachment point for
tagalongs.  Dean quickly found a repeatable tagalong for the turtle ship.
This tagalong can be said to have a period of 28, which is the number of
generations for it to reappear in the same location.  This tagalong is
not self-terminating, however.  A different kind of tagalong is required
to terminate the repeating one.  The following shows the base ship, four
copies of the repeating tagalong, and a small terminating tagalong.

[Period 3 spaceship with repeatable tagalong and ending tagalong (speed c/3)]
 ...................O........O........O.........O...........
 .................OO........O.O......O.O......OO............
 .OOO.......O.....OO.......OO........O.O......OO.........O.O
 .OO..O.OO.OO.......O........O.......O..........O.......OOOO
 ...OOO....O......O...O....OO............O....O...O....OO...
 .O..O.O...O...O.O...OOOO..OOOOOO...OO..O..O.O...OOOO..OO...
 O....O....O..O.OO...O.O..O.O...O.O..O.OO...OO...O.O..O.....
 O....O....O..O.OO...O.O..O.O...O.O..O.OO...OO...O.O..O.....
 .O..O.O...O...O.O...OOOO..OOOOOO...OO..O..O.O...OOOO..OO...
 ...OOO....O......O...O....OO............O....O...O....OO...
 .OO..O.OO.OO.......O........O.......O..........O.......OOOO
 .OOO.......O.....OO.......OO........O.O......OO.........O.O
 .................OO........O.O......O.O......OO............
 ...................O........O........O.........O...........
 
 
The same repeating tagalong can also be attached in a different way to
the base ship, as shown below.  Also shown is an alternate terminating
tagalong.

[Period 3 spaceship with repeatable tagalong and another ending (speed c/3)] 
 ..................O.........O........O.........O.O
 .................O.O......OO........O..OOO...O..O.
 .OOO.......O.....O.O......OO.......OO....O.O.O..OO
 .OO..O.OO.OO.....O..........O..........O.O........
 ...OOO....O..........O....O...O....OO.OO..........
 .O..O.O...O...O.OO..O..O.O...OOOO..OOO............
 O....O....O..O...O.OO...OO...O.O..O.OO............
 O....O....O..O...O.OO...OO...O.O..O.OO............
 .O..O.O...O...O.OO..O..O.O...OOOO..OOO............
 ...OOO....O..........O....O...O....OO.OO..........
 .OO..O.OO.OO.....O..........O..........O.O........
 .OOO.......O.....O.O......OO.......OO....O.O.O..OO
 .................O.O......OO........O..OOO...O..O.
 ..................O.........O........O.........O.O


The tails of the terminating tagalong above have alternate forms which
also work, and which are simple permutations of the positions of the cells
in the final few columns.  The following diagrams show these permutations
for the bottom 5 rows and rightmost 9 columns.

[Alternate endings for tail of final component]
 .........        .........        ......O.O
 O.....O.O        O...O..OO        O...O..O.
 O.O.O..O.        O.O.O..O.        O.O.O..OO
 O...O..OO        O.....O.O        O........
 .........        .........        .........


The second use of the spark from the turtle spaceship (and the sparks from
other c/3 spaceships) is that they can interact with faster spaceships to
produce various reactions (which is not possible for period 2 spaceships).
For example, a LWSS catches up to a period 3 spaceship with a relative speed
of c/6, and can then interact with it.  The following shows a simple case of
this, where the spark from the turtle ship destroys the pursuing LWSS, and
so saves the turtle.

[Period 3 spaceship uses its spark to destroy a pursuing LWSS]
 .OOO.......O.........
 .OO..O.OO.OO.........
 ...OOO....O......O..O
 .O..O.O...O.....O....
 O....O....O.....O...O
 O....O....O.....OOOO.
 .O..O.O...O..........
 ...OOO....O..........
 .OO..O.OO.OO.........
 .OOO.......O.........


The following demonstrates two useful reactions found by Dean Hickerson.
Here two turtle spaceships are pursued by a salvo of five LWSSs and a MWSS.
The three lower spaceships collide with the lower turtle spaceship to
produce a glider.  This glider then collides with the debris created by
the collision of the upper spaceships with the upper turtle spaceship to
produce a MWSS which travels in the reverse direction.

[Salvo of c/2 spaceships hits c/3 ships to produce backwards MWSS (speed c/3)]
 .OOO.......O.............................................................
 .OO..O.OO.OO.............................................................
 ...OOO....O...................OO.........................................
 .O..O.O...O..................OOOO........................................
 O....O....O........OOOO.....OO.OO........................................
 O....O....O........O...O.....OO..........................................
 .O..O.O...O........O................................................OOOO.
 ...OOO....O.........O..O............................................O...O
 .OO..O.OO.OO........................................................O....
 .OOO.......O.........................................................O..O
 .........................................................................
 .........................................................................
 .........................................................................
 ........................OOO.......O......................................
 ........................OO..O.OO.OO......................................
 ..........................OOO....O.......................................
 ........................O..O.O...O.....OO................................
 .......................O....O....O....OO.OOO...OOOO......................
 .......................O....O....O.....OOOOO...O...O.....................
 ........................O..O.O...O......OOO....O.........................
 ..........................OOO....O..............O..O......OOOO...........
 ........................OO..O.OO.OO.......................O...O..........
 ........................OOO.......O.......................O..............
 ...........................................................O..O..........


Dean found the above reaction in order to construct a Life pattern which
had a population growth like log(t), according to a method suggested by
Bill Gosper.  This is done by shooting one salvo of c/2 ships at the pair
of c/3 ships, and waiting until the returning MWSS arrives.  When it does,
then shoot out a glider somewhere, and send another salvo of the c/2 ships.
Since the period 3 ships quintuple their distance from the salvo gun every
cycle, the number of gliders grows at a rate which keeps dividing by 5, and
this causes the population to grow like log(t).  However, after finding the
reaction shown above, Dean found other simpler ways to create this behavior,
and so this construction has not been completed.  Later in this article is
another simpler reaction which produces the same result.

After finding the period 3 spaceships given above and their tagalongs,
Dean Hickerson went on to other things, and (like the period 2 spaceships),
nobody looked for further period 3 spaceships for a while.

In March, 1992 I started looking for period 3 spaceships and their tagalongs,
eventually doing an exhaustive search for long thin symmetrical spaceships
in an area up to 18 cells wide and 79 cells long.  I found several new
spaceships, and many tagalongs.  I have been the only person doing a search
for period 3 spaceships since Dean's earliest searches.  Therefore the rest
of the spaceships and tagalongs in this article were found by me, and so I
will omit mentioning the discoverer of each spaceship.

The first new spaceship found was the following.

[Small symmetrical period 3 spaceship (speed c/3)]
 .....O.......
 ....O.O....O.
 ....O.O...O.O
 ....O.....OO.
 ..........O..
 ...OO......O.
 ....O.OO...O.
 ...OO.OOOOO..
 .O..OOO......
 OO...........
 .O..OOO......
 ...OO.OOOOO..
 ....O.OO...O.
 ...OO......O.
 ..........O..
 ....O.....OO.
 ....O.O...O.O
 ....O.O....O.
 .....O.......


The following spaceship was the first new spaceship found using a new
search feature which allows searching in a large number of rows, but
limits the number of ON cells in any column to a specified number of
adjacent rows.  This ship has the same number of ON cells as the smallest
known period 3 spaceship, and thus ties in minimum size (but it has more
ON cells in the other phases).

[Second smallest known period 3 spaceship (speed c/3)]
 .....O..
 ....O.O.
 ...OO...
 ....O.O.
 ....OO..
 .......O
 ...O..O.
 ..O.....
 .OO.....
 .O.O....
 OO......
 ........
 .O......
 .O.O....
 .O.O....
 ..O.....


The spaceship above has two nice properties.  First, it is more spread out
than any other period 3 spaceship.  This makes it the best candidate for
being constructed from a set of glider collisions.  If it could be constructed,
then a spaceship gun for it could be built.  So far none of the new spaceships
have been able to be constructed from gliders.  (David Buckingham is an expert
at constructing objects from gliders.  He despairs of constructing most of
the new spaceships because they are what he calls "space dust".  Only a small
number of the new spaceships are simple enough to be constructed from gliders
using known techniques.  David says he does have a method that would allow the
above spaceship to be constructed, but he hasn't completed the construction.)

The second nice property of the spaceship is that it contains a different
set of sparks that can have new tagalongs attached to them.  The following
shows a repeatable tagalong for this ship.  Surprisingly, this tagalong was
not found by a search program, but was found manually.  This was possible
because most of the tagalong resembles a component of the base ship.

[Period 3 spaceship with small repeatable tagalong (speed c/3)]
 ............O..
 ...........O.O.
 ..........OO...
 .....O.....O.O.
 ....O.O....OO..
 ...OO.........O
 ....O.O...O..O.
 ....OO...O.....
 .......O.O.....
 ...O..O...O..O.
 ..O...........O
 .OO........OO..
 .O.O.......O.O.
 OO........OO...
 ...........O.O.
 .O..........O..
 .O.O...........
 .O.O...........
 ..O............


Since the tagalong has a pair of the same sparks as the base spaceship,
it can be attached to itself an arbitrary number of times.  Because there
is always a choice of two sets of sparks that another copy of the tagalong
can attach to, you can make a ship that weaves back and forth as desired.

This tagalong is even more versatile than is described above.  A section
of it can be repeatedly attached to itself to make a arbitrarily long "arm".
This allows a binary tree spaceship to be built for period 3 spaceships
(therefore sharing this capability with period 2 spaceships).  An example
of such a spaceship is shown below.  One of its phases is very striking in
appearance (one of the most unlikely-looking spaceships known).

[Period 3 "binary tree" spaceship (speed c/3)]
 ...........................O...............
 ..........................O.O..............
 .........................OO................
 ..........................O.O..............
 ..........................OO...............
 .............................O.............
 .........................O..O..............
 ........................O..................
 .......................OO..................
 ..................O.....O.O................
 .................O.O....OO.................
 ................OO.........O...............
 .................O.O...O..O................
 .................OO...O....................
 ....................O.O....................
 ................O..O...O..O................
 ...............O...........O...............
 ..............OO........OO.................
 ...............O.O......O.O................
 ...............OO......OO..................
 ..................O.....O..................
 ..............O..O.......O..O...........O..
 .............O...............O.........O.O.
 ............OO............OO..........OO...
 ..O..........O.O..........O.O..........O.O.
 .O.O.........OO..........OO............OO..
 .O.O............O.........O.O.............O
 .O..........O..O...........O..........O..O.
 ...........O.........................O.....
 OO........OO........................OO.....
 .O.O.......O.O.......................O.O...
 .OO........OO........................OO....
 ..O...........O.........................O..
 ...O..O...O..O......................O..O...
 .......O.O.........................O.......
 ....OO...O........................OO.......
 ....O.O...O..O...............O.....O.O.....
 ...OO.........O.............O.O....OO......
 ....O.O....OO..............OO.........O....
 .....O.....O.O..............O.O...O..O.....
 ..........OO................OO...O.........
 ...........O...................O.O.........
 ............O..O...........O..O...O..O.....
 ................O.........O...........O....
 .............OO..........OO........OO......
 .............O.O..........O.O......O.O.....
 ............OO............OO......OO.......
 .............O...............O.....O.......
 ..............O..O.......O..O.......O..O...
 ..................O.....O...............O..
 ...............OO......OO............OO....
 ...............O.O......O.O..........O.O...
 ..............OO........OO..........OO.....
 ...............O...........O.........O.....
 ................O..O...O..O...........O..O.
 ....................O.O...................O
 .................OO...O................OO..
 .................O.O...O..O............O.O.
 ................OO.........O..........OO...
 .................O.O....OO.............O.O.
 ..................O.....O.O.............O..
 .......................OO..................
 ........................O..................
 .........................O..O..............
 .............................O.............
 ..........................OO...............
 ..........................O.O..............
 .........................OO................
 ..........................O.O..............
 ...........................O...............


The base ship can be extended in the same manner as is done to the tagalong
to make it wider.  One interesting thing about the above spaceship is that
many perturbations to it will simply break off and not destroy the rest of
the spaceship.  The reason for this is that the repeating component has a
self-repairing feature.  If the dangling cell next to the edge cell of an
arm is removed (or equivalently, the end component is removed leaving
another similar component at the end), then the ship will regenerate the
missing cell.

The following shows a slightly extended base spaceship with the dangling
cell removed which will regenerate in generation 3.

[Regenerating period 3 spaceship (speed c/3)]
 ..O.......
 .O.O......
 .O.O......
 .O........
 ..........
 OO........
 .O.O......
 .OO.......
 ..O.......
 ...O..O...
 .......O..
 ....OO....
 ....O.O...
 ...OO.....
 ....O.....
 .....O..O.
 .........O
 ......OO..
 ......O.O.
 .....OO...
 ......O...
 .......O..


Other early tagalongs found were the following.  These are the same except
for where they attach to the base ship.  They have sparks at the back which
allow them to be repeatedly attached to each other.  These tagalongs can be
mixed with the one just above.

[Two period 3 ships with related repeatable tagalongs (speed c/3)]
 ..............O............       ..............O............
 .............O.O...........       .............O.O...........
 .....O.......O.O.......OO.O       .....O......OO.........O.O.
 ....O.O......O........O...O       ....O.O.......O........OO.O
 ...OO............O.......O.       ...OO.......OO........O....
 ....O.O...O.OO..O..O.O.O...       ....O.O.....OOOOOO...OO....
 ....OO...O...O.OO...OO.....       ....OO...OO..O...O.O.......
 .......O.O...O.OO...OO.....       .......O.OO..O...O.O.......
 ...O..O...O.OO..O..O.O.O...       ...O..O.....OOOOOO...OO....
 ..O..............O.......O.       ..O.........OO........O....
 .OO..........O........O...O       .OO...........O........OO.O
 .O.O.........O.O.......OO.O       .O.O........OO.........O.O.
 OO...........O.O...........       OO...........O.O...........
 ..............O............       ..............O............
 .O.........................       .O.........................
 .O.O.......................       .O.O.......................
 .O.O.......................       .O.O.......................
 ..O........................       ..O........................


These tagalongs are similar to the back ends of the original repeating
tagalongs that Dean Hickerson found for his turtle spaceship.  This means
that all these tagalongs can also be attached to that spaceship.

Another early tagalong is the following, which I called the "fly".  It
turns out that many tagalongs look similar to this one, but this was the
first one found with this appearance.  It can be repeatedly attached to
itself, as shown here.  The front part of this tagalong resembles the
front of the turtle spaceship, but is wider.

[Period 3 spaceship with repeatable "fly" tagalong (speed c/3)]
 ..........................O.O...O...........................
 .........................OO.O.O..O..........................
 ...........OOO........O.........O...........................
 ...........OO..O.OO...O..OOOO...............................
 .....O.......OOOO..O.O..OO....OO............................
 ....O.O....O..O...OOO.....OOO...............................
 ...OO.....O....O..OO..OO..O..O..............................
 ....O.O...O....O..OOO.O.O....OO.............................
 ....OO...OO....O..OOOO.....O........................OO...O.O
 .......O.OO....O..OOOO.....O...........O............OOO.O..O
 ...O..O...O....O..OOO.O.O....OO.......O..........OO....OO.O.
 ..O.......O....O..OO..OO..O..O.......OO..O.OO...OOOOOOO.OO..
 .OO........O..O...OOO.....OOO............OO..O.O........O...
 .O.O.........OOOO..O.O..OO....OO.....OO.O...O...O....OO.....
 OO.........OO..O.OO...O..OOOO........OOOO....O......OO....O.
 ...........OOO........O.........O...O..OO....O..OO....OO.O..
 .O.......................OO.O.O..O..O.OOO....O..OOO...OO....
 .O.O......................O.O...O...O.OOO....O..OOO...OO....
 .O.O................................O..OO....O..OO....OO.O..
 ..O..................................OOOO....O......OO....O.
 .....................................OO.O...O...O....OO.....
 .........................................OO..O.O........O...
 .....................................OO..O.OO...OOOOOOO.OO..
 ......................................O..........OO....OO.O.
 .......................................O............OOO.O..O
 ....................................................OO...O.O


Here are two short, wide period 3 spaceships which show more components that
could be added to Dean's grammar.  These ships have additional sparks that
are useful for perturbing following spaceships and for attaching tagalongs
to.  The spaceship on the right is the only known period 3 spaceship with a
spark on the edge.  This ship was found by an explicit search starting with
that spark.  But the edge spark has not been too useful so far.

[Two more period 3 spaceships with useful sparks (speed c/3)]
 ...O....       .....O.O...
 ..O.O...       .....O.....
 ..O.O...       ..OOO......
 ..O.....       ..OO.O.....
 ........       .O..OO.....
 .OO.....       ..OOOO.....
 ..O.O...       .....O.....
 .O.O....       ..O.O..O...
 .OOO....       OO.OO.O....
 ........       OOO........
 ..O.O...       .....O.....
 ..OO....       .OO...OOO..
 ...O....       .OOO..O....
 ...O.O..       ........O..
 ...OO...       ....OOOO...
 .OOO....       .....O.....
 O.O.....       .....OO....
 O..O....       ......O.OOO
 O.OO....       .......O...
 ...O....       ..........O
 O..O....       ......O....
 .OO.....       ....OOOOO.O
 ..O...O.       ...O...OO.O
 ...OO..O       ..O...O....
 ...OO...       ...O...O...
 ....O...       .....O.....
 ...OO...       ...OOO.....
 ..O...O.       ..O..O.....
 .OO.OO..       ......OO...
 ..O.....       ..OOO.OO...
 ..OO....       ..OO...OO..
 ...O....       ......O.O..
 ....O...       ....OOO....
                ....OOO....
                ....OO.....
                ......O....
                ....OO.....
                .....O.O...
                ......O....


I found a salvo of two LWSSs that could hit the back of the first ship above
and which generates a glider.  Dean Hickerson then extended that to a salvo
of four LWSSs that could hit two period 3 ships to generate a backwards-
traveling MWSS.  This is shown below.

[Four LWSSs hit two period 3 ships to produce backwards MWSS]
 ....O.........................................................
 ..OO..........................................................
 ..OO..........................................................
 ....O.........................................................
 ..O...........................................................
 ..O.O.........................................................
 ..O.O.........................................................
 ...O..........................................................
 .OO...........................................................
 ..O...........................................................
 ..OOO.........................................................
 ...O..........................................................
 .....O........................................................
 ...OO.........................................................
 ...OO.........................................................
 ..............................................................
 OOO...........................................................
 OO..OO........................................................
 ..O...........................................................
 .OO...........................................................
 .OO...........................................................
 .O..O.........................................................
 .....O........................................................
 ..OOOOO.......................................................
 ......OO......................................................
 ......OO..OO..................................................
 ...OOOO..OO.OO................................................
 ..O...O...OOOO............................................OO..
 ..OOO......OO............................................OO.OO
 ..O..O....................................................OOOO
 ...O.......................................................OO.
 ...O.O........................................................
 ....O.........................................................
 ..............................................................
 ..............................................................
 ..............................................................
 ..............................................................
 ..............................................................
 ..............................................................
 ..............................................................
 ..............................................................
 ..............................................................
 .......................O......................................
 ......................O.O.....................................
 ......................O.......................................
 .....................O..O..............O..O...................
 .....................OOO......OO......O.......................
 .....................O...O...OOOO.....O...O...................
 ......................OOOO..OO.OO.....OOOO....................
 .........................OO..OO...............................
 .........................OO...................................
 .....................OOOOO....................................
 ........................O.....................................
 ....................O..O......................................
 ....................OO........................................
 ....................OO........................................
 .....................O........................................
 ...................OO..OO.....................................
 ...................OOO........................................
 ..............................................................
 ......................OO......................................
 ......................OO......................................
 ........................O.....................................
 ......................O.......................................
 .....................OOO......................................
 .....................O........................................
 ....................OO........................................
 ......................O.......................................
 .....................O.O......................................
 .....................O.O......................................
 .....................O........................................
 .......................O......................................
 .....................OO.......................................
 .....................OO.......................................
 .......................O......................................


This pattern is similar to the one found earlier by Dean, but uses two fewer
spaceships.  It has another important advantage over the earlier pattern.
The returning MWSS is on a different path than the incoming LWSSs.  This
means that multiple salvos of LWSSs can be heading for the period 3 ships,
at the same time as multiple returning MWSSs can be heading backwards.

In August 1992, the above reaction was used by Dean Hickerson to implement
an example of a "sawtooth" pattern (his seventh).  A sawtooth is a pattern
whose population is unbounded, but which doesn't tend to infinity (the graph
of the population looks like a zig-zag pattern, with fixed lower points and
increasing higher points).  In this sawtooth, a salvo gun tries to shoot
salvos of the four LWSSs at the receding period 3 spaceships, but 5 of the
salvos are inhibited if a MWSS has just arrived.  So a stream of salvos
grows towards the period 3 ships and is reflected back towards the gun.
When the first MWSS reaches the gun, the salvos are turned off, and stay
off until the last returned MWSS arrives.  Since the period 3 spaceships
are receding, each cycle requires more salvos before being turned off, and
thus the population keeps reaching higher maximums.  But the population
always returns to the same low number of ON cells when the salvos are
used up.

--------------------- [Continued in next mail article] ----------------------
Newsgroups: comp.theory.cell-automata