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 divided by the period length. 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 the speed of 2c/5. Until the construction of Gemini in May 2010, all known spaceships in Life traveled either orthogonally (only horizontal or vertical displacement) or diagonally (equal horizontal and vertical displacement) at one of the twelve known speeds; 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, as well as the first spaceship other than the glider to travel at the speed of c/4 diagonally, dubbed the big glider. Hickerson also found several ways to combine switch engines to create the first diagonal c/12 spaceships, named Corderships in honour of Charles Corderman. The next spaceship speed to be discovered was that of 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 program that uses iterative deepening depth-first searching, and in 2000 he used this program to find the first spaceship that travels 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, which made use of the 17c/45 reaction.

In May, 2010 Andrew J. Wade created a universal constructor-based spaceship, Gemini, which travels at a speed of (5120,1024)c/33699586. This was the first explicitly constructed spaceship in Life to travel in an oblique direction, and also yielded the first explicit method of constructing arbitrarily slow spaceships.

David Eppstein's weekender

Speed	Direction	First discovered	Discoverer	Year of discovery
c/4	diagonal	glider	Richard Guy	1970
c/5	diagonal	295P5H1V1	Jason Summers	2000
c/6	diagonal	seal	Nicolay Beluchenko	2005
c/7	diagonal	83P7H1V1	Matthias Merzenich	2011
c/12	diagonal	13-engine Cordership	Dean Hickerson	1991
c/2	orthogonal	lightweight spaceship	John Conway	1970
c/3	orthogonal	25P3H1V0.2	Dean Hickerson	1989
c/4	orthogonal	119P4H1V0	Dean Hickerson	1989
2c/5	orthogonal	44P5H2V0	Dean Hickerson	1991
c/5	orthogonal	snail	Tim Coe	1996
c/6	orthogonal	dragon	Paul Tooke	2000
2c/7	orthogonal	weekender	David Eppstein	2000
17c/45	orthogonal	caterpillar	Gabriel Nivasch	2004
2560c/16849793	slope 5	Gemini	Andrew J. Wade	2010
2048c/17783745	slope 2	Gemini 2	Dave Greene	2010

Spaceship types

Main article: Spaceship types

Although Spaceships are most commonly categorized by their speed and direction, other categorizations have been applied to spaceships based on their appearances, components, or other properties. 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 greyships, spaceships filled with large amounts of static, live cells, or smoking ships, which produce large sparks, a notable example being the schick engine. A spaceship may also support other components which would not function as spaceships on their own. Given a freestanding spaceship, such additional components are often referred to as tagalongs; perhaps even pushalongs. Unstable spaceships immersed in a sustaining cloud are known as flotillae. A well known example is the overweight spaceship, which is unstable on its own but may be 'escorted' by two smaller spaceships.

A greyship found by Hartmut Holzwart

Speed	Direction	Smallest known	Minimum # of cells
c/4	diagonal	glider	5
c/5	diagonal	58P5H1V1	58
c/6	diagonal	77P6H1V1	77
c/7	diagonal	Lobster	83
c/12	diagonal	4-engine Cordership	134
c/2	orthogonal	lightweight spaceship	9
c/3	orthogonal	25P3H1V0.1, 25P3H1V0.2	25
c/4	orthogonal	46P4H1V0	46
2c/5	orthogonal	30P5H2V0	30
c/5	orthogonal	spider	58
c/6	orthogonal	56P6H1V0	56
2c/7	orthogonal	weekender	36
17c/45	orthogonal	caterpillar	11,880,063
2560c/16849793	slope 5	Gemini	846,278
2048c/17783745	slope 2	Gemini 2

See also

• List of spaceships
• Spaceship terminology
• Types of spaceships
• Spaceship flotilla

External links

• Spaceship at the Life Lexicon