home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.theory.cell-automata
- Path: sparky!uunet!gatech!darwin.sura.net!mips!mips!munnari.oz.au!manuel!sserve!pdact!dbell
- From: dbell@pdact.pd.necisa.oz.au (David I. Bell)
- Subject: Spaceships in Conway's Life (Part 1)
- Organization: NEC Information Systems Australia, Canberra
- Date: Fri, 14 Aug 1992 01:20:52 GMT
- Message-ID: <1992Aug14.012052.6306@pdact.pd.necisa.oz.au>
- Summary: First in a series of recent results in Life
- Keywords: life
- Sender: news@pdact.pd.necisa.oz.au (News Holder)
- Lines: 519
-
-
- Spaceships in Conway's Life (Part 1)
- by David I. Bell
- dbell@pdact.pd.necisa.oz.au
- 12 Aug 1992
-
-
- This is the first of a series of articles on recent results in Conway's
- Game of Life. There are many aspects of Life that are interesting and
- have recent developments, such as glider guns, spaceships, puffer trains,
- large period oscillators, and the construction of objects with desired
- properties.
-
- I am restricting this set of articles to spaceships because of two reasons.
- Firstly, since the earliest days of Life around 1970, no truly new spaceships
- had been discovered until just about three years ago, and therefore this area
- is very new and exciting. And secondly, I have had a part in developing
- this area, and therefore know first hand about some of the results. But I
- will touch on several of the other areas as I go.
-
- Almost all of the new spaceship results I will be describing were found by
- one of three people. Possibly others have independently discovered some of
- these things, and if so, we certainly should share credit with them. But
- until I know otherwise, the credit for the discoveries belongs to the people
- I mention. These people are Dean Hickerson, David Bell (myself), and
- Hartmut Holzwart (listed in order of involvement).
-
- Most of the new spaceships were found by computer search. The size and
- complexity of most of the discoveries are such that they would not be
- expected to turn up by running random patterns, or by manually trying a
- set of possibilities. However, some of the "fine tuning" of the results
- are the work of human thinking and manipulating pieces of the found results.
-
- Firstly, I should define some terminology. A spaceship is a finite pattern
- of live cells in Life that after a certain number of generations reappears,
- but translated in some direction by a nonzero distance. Translation is
- measured by the shortest king-wise connected path between two cells. So two
- cells adjacent to each other are one cell apart, whether or not the cells
- are adjacent orthogonally or diagonally. The process of translating after
- a certain number of generations is called moving or traveling.
-
- The number of generations before the pattern reappears (but translated)
- is called the period of the spaceship. (This is analogous to the period of
- stationary oscillators.) Many spaceships appear to be the same pattern
- after a number of generations, but on closer examination are not really
- the same. Instead of being merely translated, they are also reflected (or
- flipped) as in a mirror. After twice that number of generations, the
- spaceship does reappear in its original form, with just a translation.
- The period always measures this full number of generations. Spaceships
- which show their mirror image after half their period are called glide-
- reflection spaceships.
-
- Spaceships can travel orthogonally (straight left-right or up-down), or
- diagonally. All known diagonal spaceships travel the same distance left-
- right as they do up-down. There is no reason why a spaceship could not
- travel (for example) two units across and one unit up for its translation.
- However no example of such a spaceship is known. Theoretically, we could
- build ships with any translation by using a universal computer/constructor.
- But they would be very large and slow.
-
- The translated distance divided by the period is the speed of the spaceship.
- Since the maximum speed of propagation of a signal in Life is one cell per
- generation, this speed is known as c (the speed of light). This speed is
- also the fastest possible growth of any finite object for a finite number
- of generations (think of a long line of ON cells). However, growth (or
- even just movement) of a finite object for an infinite time cannot occur
- at this speed. It was proven in the early days of Life that the maximum
- possible speed of any spaceship is c/2 for orthogonal spaceships, and c/4
- for purely diagonal spaceships. More generally, if a spaceship moves A
- cells across and B cells up, then its period must be at least 2 * (A + B).
- This means (for example) that an orthogonal spaceship might move by one cell
- in two generations, or two cells in four generations, or three cells in six
- generations, and so on. But no spaceship (for example) can move by one cell
- in one generation, or two cells in three generations, or three cells in four
- generations.
-
- Whenever I list spaceships or puffers, I will follow some standard rules.
- Since most known spaceships move orthogonally, that movement will not be
- explicitly mentioned. They will always be drawn so as to move from right
- to left. The few diagonal spaceships will be marked as such, and will
- move in the indicated direction.
-
- To begin with and to be complete, I will list the original spaceships.
- These are the glider, the lightweight spaceship (LWSS), middleweight
- spaceship (MWSS), and the heavyweight spaceship (HWSS). These were all
- found very soon after Life was invented by Conway. They are:
-
- [glider (diagonal to lower left, glide-reflective, period 4, speed c/4)]
- .O.
- O..
- OOO
-
-
- [LWSS (glide-reflective, period 4, speed c/2)]
- .O..O
- O....
- O...O
- OOOO.
-
-
- [MWSS (glide-reflective, period 4, speed c/2)]
- ...O..
- .O...O
- O.....
- O....O
- OOOOO.
-
-
- [HWSS (glide-reflective, period 4, speed c/2)]
- ...OO..
- .O....O
- O......
- O.....O
- OOOOOO.
-
-
- The glider is the most basic spaceship. Since it is so small, it appears
- spontaneously from random objects. Collisions between gliders produce
- many useful things. For example, two gliders can produce another glider,
- and three gliders can produce a LWSS or MWSS or a HWSS. Gliders can be
- produced indefinitely by many kinds of "glider guns". The first glider gun
- was found by Bill Gosper in 1970, and was the first example of a Life object
- whose population grew arbitrarily large.
-
- The three orthogonal spaceships are very useful because of the presence of
- their "sparks". Sparks are cells at the edge of an object which die off,
- and which can perturb other objects without destroying the object which
- generates the spark. The commonest use of sparks from these spaceships is
- to perturb an "engine" to produce puffer trains, or to modify stationary
- objects when the spaceships pass by.
-
- The three orthogonal spaceships above show an obvious pattern, and the
- casual Life-player might wonder why the pattern cannot be continued to
- make even larger spaceships. This will not work directly because the
- sparks do not die off anymore for larger ships, but wreck the ship.
-
- The following for example, doesn't work because the spark at the top
- is actually a blinker, and doesn't die. Without the blinker, this object
- is known as an OWSS (overweight spaceship). This name is also given to
- even larger objects following the same pattern.
-
- [non-working OWSS]
- ...OOO..
- .O.....O
- O.......
- O......O
- OOOOOOO.
-
-
- It was discovered rather early that an OWSS can survive if it is "escorted"
- by other smaller spaceships. The escorting spaceships are positioned to
- prevent the formation of the deadly non-sparks. The following is an extreme
- example of this. This shows the largest overweight spaceship which can be
- safely escorted by only two other spaceships.
-
- [OWSS escorted by two HWSS (period 4, speed c/2)]
- ....OOOO.......
- ...OOOOOO......
- ..OO.OOOO......
- ...OO..........
- ...............
- ...........OO..
- .O............O
- O..............
- O.............O
- OOOOOOOOOOOOOO.
- ...............
- ...............
- ....OOOO.......
- ...OOOOOO......
- ..OO.OOOO......
- ...OO..........
-
-
- There are many other combinations of spaceships that will support one or
- more OWSS. Some OWSS can be supported by a convoy of two spaceships on
- each side. But for very long OWSS, no convoy of small spaceships can work
- to stabilize it. However, it is possible to support an arbitrarily long
- OWSS by nesting different sized OWSS side by side to stabilize them all,
- with final small spaceships on the outside.
-
- The next topic related to spaceships is called a tagalong. A tagalong is
- something which follows behind one or more spaceships, and needs the
- spaceships in order to survive. Generally, tagalongs are attached to the
- sparks of a spaceship so that they don't destroy the spaceship. But some
- tagalongs attach right to the base ship itself, and some even need some
- modification of the base ships in order to work. A tagalong along with its
- base ship can be considered as a large spaceship.
-
- One of the first tagalongs was found a couple of years into the history of
- Life. This is the Schick engine, found by Paul Schick in 1972. It uses
- the sparks from two adjacent LWSS to keep the engine going.
-
- [Schick engine tagalong (period 12, speed c/2)]
- OOOO.....
- O...O....
- O........
- .O..O..OO
- ......OOO
- .O..O..OO
- O........
- O...O....
- OOOO.....
-
-
- This tagalong is very useful, because it splits into two separate parts.
- The back part dies off on its own. But it can be perturbed by adjacent
- LWSS, MWSS, or HWSS in many ways to produce output which remains. It
- then becomes a puffer train. For example, adding one LWSS gives:
-
- [Simple puffer train producing pairs of beehives (period 24, speed c/2)]
- ...........OO.
- ..........OOOO
- .........OO.OO
- ..........OO..
- OOOO..........
- O...O.........
- O.............
- .O..O..OO.....
- ......OOO.....
- .O..O..OO.....
- O.............
- O...O.........
- OOOO..........
-
-
- If a second LWSS is also placed at the bottom of the above object
- symmetrically to the top LWSS, then the puffer produces a stream of
- blinkers with period 12.
-
- A tagalong can be changed into a puffer engine by perturbations as in
- the above example. The reverse can also happen. A puffer engine can
- be tamed and turned into a tagalong. This can generally be done by
- using passing spaceships to destroy all of the puffer output. Such an
- object will then be a large spaceship. I will give two examples.
-
- The first example uses a well known puffer engine, the B heptomino. The
- first two puffers in Life were found by Bill Gosper and are both based on
- the B heptomino. The one given here is the second one he found, where a
- single engine is perturbed by two LWSS to become a very dirty puffer. It
- takes over 4600 generations for this puffer to settle down. It then
- produces a large collection of objects with period 140.
-
- [Dirty puffer train based on B heptomino (eventual period 140, speed c/2)]
- .....
- .OO..
- OO.OO
- .OOOO
- ..OO.
- .....
- .....
- ....O
- ...OO
- ..OO.
- ...OO
- .....
- .....
- .....
- .....
- .OO..
- OO.OO
- .OOOO
- ..OO.
-
-
- By adding another LWSS, this dirty puffer is tamed and becomes a spaceship
- with period 20. This object has a rather large spark which can then be
- perturbed with other spaceships to produce simple useful outputs such as
- gliders.
-
- [Period 20 spaceship based on B heptomino (period 20, speed c/2)]
- ..........O..O........
- .OO......O............
- OO.OO....O...O........
- .OOOO....OOOO.........
- ..OO..................
- ......................
- ...........O..........
- ....O...O....O........
- ...OO....O...O...OO.OO
- ..OO.....O........O..O
- ...OO.............OOO.
- ............O..O......
- .............OO.......
- ......................
- ......................
- .OO...................
- OO.OO.................
- .OOOO.................
- ..OO..................
-
-
- The second example is based on a puffer discovered by Bob Wainwright
- in 1984. The period of this puffer is only eight, which is the minimum
- puffer period known. (There are several other different period 8 puffers
- known.) The one shown here produces a row of blinkers.
-
- [Period 8 puffer train producing blinkers (speed c/2)]
- ...O.....
- .O...O...
- O........
- O....O...
- OOOOO....
- .........
- .........
- .........
- .OO......
- OO.OOO...
- .OOOO....
- ..OO.....
- .........
- .....OO..
- ...O....O
- ..O......
- ..O.....O
- ..OOOOOO.
-
-
- By using a passing HWSS, the blinkers can be deleted, producing a true
- spaceship which can be made as large as desired by moving the trailing
- HWSS back.
-
- [Period 8 spaceship (speed c/2)]
- ...O.............
- .O...O...........
- O................
- O....O.....OO....
- OOOOO.....OO.OOOO
- ...........OOOOOO
- ............OOOO.
- .................
- .OO..............
- OO.OOO...........
- .OOOO...OOO.OOO..
- ..OO.............
- .................
- .....OO..........
- ...O....O........
- ..O..............
- ..O.....O........
- ..OOOOOO.........
-
-
- By using different puffers, and deleting the output in many many different
- ways, a very large number of spaceships can be produced. But they all
- have a few things in common. All of these orthogonal spaceships use the
- LWSS, MWSS, or HWSS as essential components. Therefore they must all have
- a speed of c/2, and a period which is a multiple of four. The question
- arises as to whether there are some spaceships which move at different
- speeds, have other periods, or don't make use of the normal spaceships.
- The answer is YES, and is why this area has been exciting in the last
- few years.
-
- Before proceeding to these new things, I will recap two tantalizing
- early results which showed that possibly such ships might be found.
-
- This first one was noticed by many people, and is the pi heptomino.
- The following is generation 1 of the pi heptomino. It reappears 30
- generations later, with a translation of 9, for a very obscure speed
- of 3c/10.
-
- [generation 1 of pi heptomino, a non-working spaceship]
- ..O
- .OO
- O..
- .OO
- ..O
-
-
- Unfortunately, it also produces a large amount of other debris which
- then quickly destroys the object. That debris can be controlled by
- carefully placed blocks in its path, or by placing many copies of the
- pi heptomino side by side. But all such constructions must be carried
- out to infinity to work forever. No one has figured out how to make a
- finite object based on this work.
-
- The second tantalizing result was discovered by Charles Corderman in 1971
- while doing an exhaustive search of polyominoes. A small object was
- discovered which translated itself diagonally by 8 cells, with some other
- debris remaining. The debris doesn't interfere immediately with the object,
- and so it translates itself again. Only after many such translations does
- the debris catch up to the engine and destroy it. Corderman found that by
- perturbing the debris in various ways, or by placing multiple copies of the
- engine alongside each other, the engine can survive forever. However, in
- none of these cases was it a spaceship. It was instead a puffer, and left
- debris behind. The following is one of the simplest of these puffers, and
- leaves just blocks behind.
-
- [Switch Engine puffer train (diagonal to upper left, glide-reflective,
- period 288, speed c/12)]
- .O.O........................
- O...........................
- .O..O.......................
- ...OOO......................
- ............................
- ..........................OO
- ..........................O.
-
-
- The above object is one of the smallest known objects whose population grows
- arbitrarily large. (All of these are based on the switch engine and have
- only 11 ON cells.) The only known diagonal puffer trains are all based on
- the switch engine. But no one succeeded in taming the debris completely to
- create a spaceship until Dean Hickerson did this in April, 1991. He did
- this by placing a large number of switch engines together so as to eliminate
- all debris. His original ship required 13 switch engines, but his smaller
- one given here only uses 10 of them. The number of them needed can possibly
- be reduced even further, but this isn't known.
-
- The spaceship is just a little too wide to be seen in an 80 column width,
- so the description below is compressed in the following manner. Each
- dollar sign represents 10 empty cells. Just use an editor to replace
- each dollar sign by 10 periods, and you will be able to reconstruct the
- picture of the full object.
-
- [Cordership (diagonal to upper right, symmetrical, period 96, speed c/12)]
- $$$.....OO$$$$$
- $$$.....O...OO$$$$......
- $$$....O......O.......OOO$$$.....
- $$$..OOOOO...O.....OOO$$$........
- $$$.....O...O......OOO$$$........
- $$$..O..O$.O$$$.........
- $$....OO.......OO$$$$$..
- $$....OO$$$$$$.
- $$$$$$$$.......
- $$$$$........O$$........
- $$$$$........O$$........
- $$$$$........O$$........
- $$$$$......OO$$.........
- $$$$$.....OOO$$.........
- $......OO$$$........OO$$.........
- $......OO$$$$$$.........
- $$$$$$$$.......
- $$$$$$$$.......
- $$$$$$$$.......
- $$$$$........O$$........
- $$$$$.......O$$.........
- $$$$$........O$$........
- ........OO$$$$$$$.......
- ........OO$$$......O$$$$
- $$$$.....O.O$$$.........
- $$$$....OO.OO$$$........
- $$$$.......OO$$$........
- $$$$.OO$$$$....
- $$$$...O..OOO$......O.O.......OOO.........
- $$$$.OO.O$$.O.....OOO$..
- OO$$$$.O..O$$.....OOO$..
- OO...O.......O$$.........O$$.........O$...
- ....O.O.....OOO$$.........OO$$$$.
- ...O..O..OOOO.OO$$$$$$$.
- .........O..OOO$$$O$$$$.
- ......O..OO..O$$.........OO.OO$$$......O..
- ....O.O.OO$$$....O$$$.........O..
- .....O$$$$.O$$$......O..
- $$$$.....O$..O.OO$$OO...
- $$$$.........O.O......O.OOO$........OOO...
- $$$$$.O....O.O....O$........OO...
- $$$$........O...O.O......OO$$....
- $$$$$OO..O..O...O$$.....
- $$$$$.O...OO.O$$........
- $$$$$.......O.O$$.......
- $$.......O$$.........O.O$$....O..
- $$......OOO$$$$$....O.O.
- $$.....OO.OO$$$$$..O..O.
- $$......OOO$$$$$........
- $$.......O$$$$$.........
- $$.....O.O$$$$$.....O..O
- $$....OOOO$$$$$...OOO.OO
- $$....O$$$$$.....O..OO..
- $$$$$$$$O..O...
- $$....OO.OO$$$$$..O.O...
- $$...O.....O$$$$$.......
- $$....O...O$$$$$........
- $$.......O...O.......O$$$$.......
- $$$O.O.....OOO$$$$......
- $$.........O..O..OOOO.OO$$$$.....
- $$$.....O..OOO$$$$......
- $$$..O..OO..O$$$.........OO......
- $$$O.O.OO$$$$...OO......
- $$$.O$$$$$.....
- $$$$$$$$.......
- $$$$$$$$.......
- $$$$$$$$.......
- $$$$$$$$.......
- $$$$$$$$.......
- $$$$$$$.OO$....
- $$$$$$$.OO$....
- $$$$$...O$$$...
- $$$$$..OOO$$$..
- $$$$$.OO.OO$$$.
- $$$$$..OOO$$$..
- $$$$$...O$$$...
- $$$$$.O.O$$$...
- $$$$$OOOO.........OO$$..
- $$$$$O$..OO$$..
- $$$$$$$$.......
- $$$$$OO.OO$$$..
- $$$$.........O.....O$$$.
- $$$$$O...O$$$..
- $$$$$...O$$$...
- $$$$$$$$.......
- $$$$$.....OO$$$
- $$$$$.....OO$$$
-
-
- The Cordership has lots of debris that dies away. Gliders can hit this
- debris and do interesting things. In particular, gliders can be turned
- by 90 or 180 degrees by hitting the debris appropriately. Dean Hickerson
- has used this fact to create some interesting constructions, such as
- reflecting gliders back and forth forever between two Corderships that are
- slowly pulling apart.
-
- The Corderships form one of several new classes of spaceships, ending a
- period of about 20 years when no new classes were found. However, it was
- not the first of these new classes. The next part of this series will begin
- exploring these new classes in earnest, starting with the c/2 period 2
- spaceships.
-
- That next article should appear in about two weeks.
-