Spaceship

The lightweight spaceship in Conway's Game of Life

A spaceship (much less commonly referred to as a glider or a fish) is a finite pattern that returns to its initial state after a number of generations (known as its period) but in a different location.

Spaceship Speed

Main article: Speed

The speed of a spaceship is the number of cells that the pattern moves during its period. This is expressed in terms of c (the metaphorical "speed of light") which is one cell per generation; thus, a spaceship with a period of five that moves two cells to the left during its period travels at a speed of 2c/5. All known spaceships in life travel either orthogonally (only horizontal or vertical displacement) or diagonally (equal horizontal and vertical displacement) at one of the twelve known speeds; however spaceships traveling in other directions and at different speeds have been constructed in other two dimensional cellular automata, and it is known that Life has spaceships that travel in all rational directions at arbitrarily slow speeds (see universal constructor).

History

the four smallest spaceships in life, the glider, lightweight spaceship, middleweight spaceship and heavyweight spaceship, were all found by hand in 1970. For almost twenty years spaceship development was limited to adding tagalongs to the known c/2 spaceships. Significant advances in spaceship technology came in 1989, when Dean Hickerson began using automated searches based on a depth-first backtracking algorithm. These searches found orthogonal spaceships with speeds of c/3, c/4, and 2c/5, and also the first spaceship to move at the speed of c/4 diagonally other than the glider, dubbed the big glider. Hickerson also found several ways to combine switch engines to create the first diagonal c/12 spaceships. The next new spaceship speed to be discovered was the orthogonal c/5 snail, found by Tim Coe in 1996, with a program he had designed using breadth first searching, and which could split tasks between multiple CPUs. In the following year David Bell found the much smaller c/5 spider using Lifesrc, a program based on Hickerson's search algorithm.

In March of 1998 David Eppstein created gfind, a search program that used a combination of breadth first search and depth first iterated deepening, and in 2000 he used this program to find the first spaceship to travel at the speed of 2c/7 orthogonally, the weekender. A search by Paul Tooke using the same program found the first c/6 orthogonal spaceship, the dragon, later that year. Also in 2000, Jason Summers found the first c/5 diagonal spaceship using David Bell's Lifesrc program.

In 2004 Gabriel Nivasch, with the help of Jason Summers and David Bell, finished construction on the caterpillar, the first known orthogonal 17c/45 spaceship. The caterpillar's design is unique in that it is made entirely of simple component parts and reactions, including many gliders and small orthogonal c/2 spaceships.

The most recently discovered spaceship speed is the diagonal c/6 seal, found by Nicolay Beluchenko in 2005.

Speed	First discovered	Discoverer	Year of discovery
c/2	lightweight spaceship	John Conway	1970
c/3	?	Dean Hickerson	1989
c/4	?	Dean Hickerson	1989
c/5	snail	Tim Coe	1996
2c/5	?	Dean Hickerson	1991
c/6	dragon	Paul Tooke	2000
2c/7	weekender	David Eppstein	2000
17c/45	caterpillar	Gabriel Nivasch	2004
c/4 Diagonal	glider	Richard Guy	1970
c/5 Diagonal	295P5H1V1.1	Jason Summers	2000
c/6 Diagonal	seal	Nicolay Beluchenko	2005
c/12 Diagonal	13-engine Cordership	Dean Hickerson	1991

Spaceship types

Main article: Spaceship types

Although Spaceships are most commonly categorized by their speed and direction, other categorizations have been applied to spaceships with similar components, properties, or appearances. One such categorization is the symmetry of spaceships; spaceships can be bilaterally symmetric, Such as Tim Coe's snail, may exhibit glide symmetry, such as the glider, or may be asymmetric, such as the caterpillar. Other, somewhat subjective categorizations have also been made, such as the greyship, a spaceship filled with large amounts of static, live cells, or Smoking ships that produce large sparks, a notable example of which is the schick engine. A spaceship may also support another component which would not function as a spaceship on its own; these additional components are often referred to as tagalongs, and spaceships created using these reactions are known as flotilla. a well known example of spaceship tagalong is the overweight spaceship, which is unstable on its own but may be 'escorted' by smaller spaceships.

Speed	Smallest known	Minimum # of cells
c/2	lightweight spaceship	9
c/3	25P3H1V0.1 and 25P3H1V0.2	25
c/4	46P4H1V0.1	46
2c/5	30P5H2V0.1	30
c/5	spider	58
c/6	dragon	102
2c/7	weekender	36
17c/45	caterpillar	11880063
c/4 Diagonal	glider	5
c/5 Diagonal	67P5H1V1.1	67
c/6 Diagonal	seal	170
c/12 Diagonal	4-engine Cordership	134

See also

• List of spaceships
• Spaceship terminology
• Types of spaceships

External links

• Spaceship at the Life Lexicon