Spaceship: Difference between revisions
fix table a little |
ordered second table by year of discovery |
||
| Line 185: | Line 185: | ||
| [[Richard Guy]] | | [[Richard Guy]] | ||
| [[:Category:Patterns found in 1970|1970]] | | [[:Category:Patterns found in 1970|1970]] | ||
|- | |- | ||
! c/2 | ! c/2 | ||
| Line 229: | Line 203: | ||
| [[Dean Hickerson]] | | [[Dean Hickerson]] | ||
| [[:Category:Patterns found in 1989|1989]] | | [[:Category:Patterns found in 1989|1989]] | ||
|- | |||
! c/12 | |||
| diagonal | |||
| [[13-engine Cordership]] | |||
| [[Dean Hickerson]] | |||
| [[:Category:Patterns found in 1991|1991]] | |||
|- | |- | ||
! 2c/5 | ! 2c/5 | ||
| Line 241: | Line 221: | ||
| [[Tim Coe]] | | [[Tim Coe]] | ||
| [[:Category:Patterns found in 1996|1996]] | | [[:Category:Patterns found in 1996|1996]] | ||
|- | |||
! 2c/7 | |||
| orthogonal | |||
| [[weekender]] | |||
| [[David Eppstein]] | |||
| [[:Category:Patterns found in 2000|2000]] | |||
|- | |- | ||
! c/6 | ! c/6 | ||
| Line 248: | Line 234: | ||
| [[:Category:Patterns found in 2000|2000]] | | [[:Category:Patterns found in 2000|2000]] | ||
|- | |- | ||
! c/ | ! c/5 | ||
| | | diagonal | ||
| [[ | | [[295P5H1V1]] | ||
| [[ | | [[Jason Summers]] | ||
| [[:Category:Patterns found in 2000|2000]] | | [[:Category:Patterns found in 2000|2000]] | ||
|- | |- | ||
| Line 272: | Line 246: | ||
| [[:Category:Patterns found in 2004|2004]] | | [[:Category:Patterns found in 2004|2004]] | ||
|- | |- | ||
! | ! c/6 | ||
| diagonal | |||
| [[seal]] | |||
| [[Nicolay Beluchenko]] | |||
| [[:Category:Patterns found in 2005|2005]] | |||
|- | |- | ||
! (5120,1024)c/16849793 | ! (5120,1024)c/16849793 | ||
| Line 292: | Line 270: | ||
| [[:Category:Patterns found in 2010|2010]] | | [[:Category:Patterns found in 2010|2010]] | ||
|- | |- | ||
! | ! c/7 | ||
| diagonal | | diagonal | ||
| [ | | [[83P7H1V1|Lobster]] | ||
| [[ | | [[Matthias Merzenich]] | ||
| [[:Category:Patterns found in | | [[:Category:Patterns found in 2011|2011]] | ||
|- | |- | ||
! | ! c/7 | ||
| | | orthogonal | ||
| [ | | [[loafer]] | ||
| [[ | | [[Josh Ball]] | ||
| [[:Category:Patterns found in | | [[:Category:Patterns found in 2013|2013]] | ||
|- | |- | ||
! (6,3)c/2621440 | ! (6,3)c/2621440 | ||
| Line 325: | Line 301: | ||
|- | |- | ||
! (23,5)c/79 | ! (23,5)c/79 | ||
| | | slope 23/5 | ||
| [[waterbear]] | | [[waterbear]] | ||
| [[Brett Berger]] | | [[Brett Berger]] | ||
| [[:Category:Patterns found in 2014|2014]] | | [[:Category:Patterns found in 2014|2014]] | ||
|- | |||
! 130c/(1636712+16N) | |||
| diagonal | |||
| [http://conwaylife.com/forums/viewtopic.php?f=2&p=25411#p25401 10hd Demonoid] | |||
| [[Chris Cain]] and [[Dave Greene]] | |||
| [[:Category:Patterns found in 2015|2015]] | |||
|- | |||
! 65c/(438852+16N) | |||
| diagonal | |||
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=1469&p=25709#p25702 0hd Demonoid] | |||
| [[Chris Cain]] | |||
| [[:Category:Patterns found in 2015|2015]] | |||
|- | |||
! c/10 | |||
| orthogonal | |||
| [[Copperhead]] | |||
| [[zdr]] | |||
| [[:Category:Patterns found in 2016|2016]] | |||
|} | |} | ||
Revision as of 03:00, 15 March 2016

A spaceship (much less commonly referred to as a glider[1] or a fish[2]) is an object which reappears in a different position after completing its period.
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). Other recently constructed large spaceships such as the waterbear and the Parallel HBK. It is known that Life has spaceships that travel in all rational directions at arbitrarily slow speeds (see universal constructor). Spaceships traveling in other directions and at different speeds have also been constructed in other two dimensional cellular automata,[3]
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 that of the overweight spaceships, which are unstable alone but may be 'escorted' by two or more smaller spaceships.

| 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 | |
| 65c/438856 | diagonal | 0hd Demonoid | 27,250 | |
| 65c/818356 | diagonal | 10hd Demonoid | 47,701 | |
| c/2 | orthogonal | lightweight spaceship | 9 | |
| 2c/5 | orthogonal | 30P5H2V0 | 30 | |
| 17c/45 | orthogonal | caterpillar | 11,880,063 | |
| c/3 | orthogonal | 25P3H1V0.2 | 25 | |
| 2c/7 | orthogonal | weekender | 36 | |
| c/4 | orthogonal | 37P4H1V0 | 37 | |
| c/5 | orthogonal | spider | 58 | |
| c/6 | orthogonal | 56P6H1V0 | 56 | |
| c/7 | orthogonal | loafer | 20 | |
| 31c/240 | orthogonal | centipede | 620,901 | |
| c/10 | orthogonal | copperhead | 28 | |
| (4096,2048)c/17783745 | slope 2 | Gemini 2 | <=872252 | |
| (6,3)c/245912 | slope 2 | Parallel HBK | 132,945 | |
| (6,3)c/2621440 | slope 2 | Half-baked knightship | 1,049,395 | |
| (3072,1024)c/36000001 | slope 3 | Gemini 3 | <=850932 | |
| (23,5)c/79 | slope 23/5 | waterbear | 197,896 | |
| (5120,1024)c/16849793 | slope 5 | Gemini | 846,278 | |
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.[4] In the following year David Bell found the much smaller c/5 spider using lifesrc, a program based on Hickerson's search algorithm.[5]
In March of 1998 David Eppstein created gfind, a breadth-first program that uses a depth-first search to limit the size of the search queue.[6] 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.[7] 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.
In Febuary 2013, the first c/7 orthogonal spaceship, loafer, was discovered by Josh Ball.
In July 2014 several half-bakery-based knightships were constructed using a new technique that did not require universal-constructor circuitry. These produced spaceships that were both much slower and much smaller than the Gemini variants.
In September 2014, Dave Greene and Chris Cain completed two 31c/240 orthogonal spaceships, along the same general lines as the original Caterpillar but using a number of new mechanisms.
In December 2014, an oblique caterpillar dubbed the Waterbear was completed by Brett Berger, traveling at (23,5)c/79.
In December 2015, Chris Cain completed a diagonal self-constructing spaceship -- a "0hd Demonoid" -- based on Geminoid technology, adapted from a larger 10hd version constructed in November in collaboration with Dave Greene.

In March 2016, forum user zdr discovered an extremely small c/10 spaceship, named the Copperhead.
See also
Notes
- ↑ "Glider". The Life Lexicon. Stephen Silver. Retrieved on April 18, 2009.
- ↑ "Fish". The Life Lexicon. Stephen Silver. Retrieved on April 18, 2009.
- ↑ "Gliders in Life-Like Cellular Automata". David Eppstein. Retrieved on April 18, 2009.
- ↑ Tim Coe. "c/5 Orthogonal spaceship". Paul's Page of Conway's Life Miscellany. Retrieved on April 18, 2009.
- ↑ David Bell. "New c/5 spaceship". Paul's Page of Conway's Life Miscellany. Retrieved on April 18, 2009.
- ↑ David Eppstein. "Searching for Spaceships (PDF)". Retrieved on April 18, 2009.
- ↑ Adam P. Goucher (May 19, 2010). "Oblique Life spaceship created". Game of Life News. Retrieved on May 21, 2010.
External links
- Spaceship at the Life Lexicon