Spaceship: Difference between revisions
mNo edit summary |
m added many links and first 2c/5 spaceship |
||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
[[Image:lwss.gif|framed|right|The lightweight spaceship in [[Conway's Game of Life]]]]A '''spaceship''' (much less commonly referred to as a '''glider'''<ref>{{cite web|url=http://www.argentum.freeserve.co.uk/lex_g.htm#glider |title=Glider |work=The Life Lexicon |publisher=Stephen Silver |accessdate=April 18, 2009}}</ref> or a '''fish'''<ref>{{cite web|url=http://www.argentum.freeserve.co.uk/lex_f.htm#fish |title=Fish |work=The Life Lexicon |publisher=Stephen Silver |accessdate=April 18, 2009}}</ref>) is a finite pattern that returns to its initial state after a number of | [[Image:lwss.gif|framed|right|The lightweight spaceship in [[Conway's Game of Life]]]]A '''spaceship''' (much less commonly referred to as a '''glider'''<ref>{{cite web|url=http://www.argentum.freeserve.co.uk/lex_g.htm#glider |title=Glider |work=The Life Lexicon |publisher=Stephen Silver |accessdate=April 18, 2009}}</ref> or a '''fish'''<ref>{{cite web|url=http://www.argentum.freeserve.co.uk/lex_f.htm#fish |title=Fish |work=The Life Lexicon |publisher=Stephen Silver |accessdate=April 18, 2009}}</ref>) is a finite [[pattern]] that returns to its initial state after a number of [[generation]]s (known as its [[Period#Spaceships|period]]) but in a different location. | ||
| Line 7: | Line 7: | ||
==Spaceship Speed== | ==Spaceship Speed== | ||
{{main|Speed}} | {{main|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 the speed of 2c/5. All known spaceships in | 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 the speed of [[2c/5 orthogonal|2c/5]]. All known spaceships in [[Conway's Game of Life|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 automaton|cellular automata]],<ref>{{cite web|url=http://fano.ics.uci.edu/ca/ |title=Gliders in Life-Like Cellular Automata |publisher=David Eppstein|accessdate=April 18, 2009}}</ref> and it is known that Life has spaceships that travel in all rational directions at arbitrarily slow speeds (see [[universal constructor]]). | ||
==History== | ==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 [[Tagalong|tagalongs]] to the known c/2 spaceships. Significant advances in spaceship technology came in 1989, when [[Dean Hickerson]] began using [[Computer search|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 engine]]s to create the first diagonal c/12 spaceships, named [[Cordership]]s 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.<ref>{{cite web|url=http://www.radicaleye.com/lifepage/patterns/p5ss.html |title=c/5 Orthogonal spaceship |author=Tim Coe |publisher=Paul's Page of Conway's Life Miscellany |accessdate=April 18, 2009}}</ref> In the following year [[David Bell]] found the much smaller c/5 [[spider]] using [[lifesrc]], a program based on Hickerson's search algorithm.<ref>{{cite web|url=http://radicaleye.com/lifepage/patterns/newc5/newc5.html |title=New c/5 spaceship |author=David Bell |publisher=Paul's Page of Conway's Life Miscellany |accessdate=April 18, 2009}}</ref> | The four smallest spaceships in life, the [[glider]], [[lightweight spaceship]], [[middleweight spaceship]] and [[heavyweight spaceship]], were all found by hand in [[:Category:patterns found in 1970|1970]]. For almost twenty years spaceship development was limited to adding [[Tagalong|tagalongs]] to the known [[c/2 orthogonal|c/2]] spaceships. Significant advances in spaceship technology came in [[:Category:patterns found in 1989|1989]], when [[Dean Hickerson]] began using [[Computer search|automated searches]] based on a depth-first backtracking algorithm. These searches found orthogonal spaceships with speeds of [[c/3 orthogonal|c/3]], [[c/4 orthogonal|c/4]], and [[3c/5 orthogonal|2c/5]], as well as the first spaceship other than the glider to travel at the speed of [[c/4 diagonal|c/4]] diagonally, dubbed the [[big glider]]. Hickerson also found several ways to combine [[switch engine]]s to create the first diagonal [[c/12 diagonal|c/12]] spaceships, named [[Cordership]]s in honour of [[Charles Corderman]]. The next spaceship speed to be discovered was that of the orthogonal [[c/5 orthogonal|c/5]] [[snail]], found by [[Tim Coe]] in [[:Category:patterns found in 1996|1996]], with a program he had designed using breadth-first searching, and which could split tasks between multiple CPUs.<ref>{{cite web|url=http://www.radicaleye.com/lifepage/patterns/p5ss.html |title=c/5 Orthogonal spaceship |author=Tim Coe |publisher=Paul's Page of Conway's Life Miscellany |accessdate=April 18, 2009}}</ref> In the following year [[David Bell]] found the much smaller c/5 [[spider]] using [[lifesrc]], a program based on Hickerson's search algorithm.<ref>{{cite web|url=http://radicaleye.com/lifepage/patterns/newc5/newc5.html |title=New c/5 spaceship |author=David Bell |publisher=Paul's Page of Conway's Life Miscellany |accessdate=April 18, 2009}}</ref> | ||
In March of 1998 [[David Eppstein]] created [[gfind]], a program that uses iterative deepening depth-first searching,<ref>{{cite web|url=http://arxiv.org/PS_cache/cs/pdf/0004/0004003v2.pdf |title=Searching for Spaceships (PDF) |author=David Eppstein |accessdate=April 18, 2009}}</ref> 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 March of [[:Category:patterns found in 1998|1998]] [[David Eppstein]] created [[gfind]], a program that uses iterative deepening depth-first searching,<ref>{{cite web|url=http://arxiv.org/PS_cache/cs/pdf/0004/0004003v2.pdf |title=Searching for Spaceships (PDF) |author=David Eppstein |accessdate=April 18, 2009}}</ref> and in [[:Category:patterns found in 2000|2000]] he used this program to find the first spaceship that travels at the speed of [[2c/7 orthogonal|2c/7]] orthogonally, the [[weekender]]. A search by [[Paul Tooke]] using the same program found the first [[c/6 orthogonal|c/6]] orthogonal spaceship, the [[dragon]], later that year. Also in 2000, [[Jason Summers]] found the first [[c/5 diagonal|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.<ref>{{cite web|url=http://www.yucs.org/~gnivasch/life/article_cat/ |title=The 17c/45 Caterpillar spaceship |author=Gabriel Nivasch |publisher=Gabriel Nivasch's Game of Life page}}</ref> | In [[:Category:patterns found in 2004|2004]] [[Gabriel Nivasch]], with the help of Jason Summers and David Bell, finished construction on the [[caterpillar]], the first known orthogonal [[17c/45 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.<ref>{{cite web|url=http://www.yucs.org/~gnivasch/life/article_cat/ |title=The 17c/45 Caterpillar spaceship |author=Gabriel Nivasch |publisher=Gabriel Nivasch's Game of Life page}}</ref> | ||
The most recently discovered spaceship speed is that of the diagonal c/6 [[seal]], found by [[Nicolay Beluchenko]] in 2005.<ref>{{cite web|url=http://pentadecathlon.com/lifeNews/2005/09/c6_diagonal_spaceship_1.html |title=c/6 Diagonal Spaceship |work=Game of Life News |publisher=Heinrich Koenig}}</ref> | The most recently discovered spaceship speed is that of the diagonal [[c/6 diagonal|c/6]] [[seal]], found by [[Nicolay Beluchenko]] in [[:Category:patterns found in 2005|2005]].<ref>{{cite web|url=http://pentadecathlon.com/lifeNews/2005/09/c6_diagonal_spaceship_1.html |title=c/6 Diagonal Spaceship |work=Game of Life News |publisher=Heinrich Koenig}}</ref> | ||
[[Image:weekender_small.gif|framed|right|David Eppstein's weekender]] | [[Image:weekender_small.gif|framed|right|David Eppstein's weekender]] | ||
| Line 32: | Line 32: | ||
| diagonal | | diagonal | ||
| [[glider]] | | [[glider]] | ||
| [[ | | [[Richard Guy]] | ||
| [[:Category:Patterns found in 1970|1970]] | | [[:Category:Patterns found in 1970|1970]] | ||
|- | |- | ||
| Line 38: | Line 38: | ||
| diagonal | | diagonal | ||
| [[295P5H1V1]] | | [[295P5H1V1]] | ||
| [[ | | [[Jason Summers]] | ||
| [[:Category:Patterns found in 2000|2000]] | | [[:Category:Patterns found in 2000|2000]] | ||
|- | |- | ||
| Line 44: | Line 44: | ||
| diagonal | | diagonal | ||
| [[seal]] | | [[seal]] | ||
| [[ | | [[Nicolay Beluchenko]] | ||
| [[:Category:Patterns found in 2005|2005]] | | [[:Category:Patterns found in 2005|2005]] | ||
|- | |- | ||
| Line 50: | Line 50: | ||
| diagonal | | diagonal | ||
| [[13-engine Cordership]] | | [[13-engine Cordership]] | ||
| [[ | | [[Dean Hickerson]] | ||
| [[:Category:Patterns found in 1991|1991]] | | [[:Category:Patterns found in 1991|1991]] | ||
|- | |- | ||
| Line 58: | Line 58: | ||
| orthogonal | | orthogonal | ||
| [[lightweight spaceship]] | | [[lightweight spaceship]] | ||
| [[ | | [[John Conway]] | ||
| [[:Category:Patterns found in 1970|1970]] | | [[:Category:Patterns found in 1970|1970]] | ||
|- | |- | ||
| Line 64: | Line 64: | ||
| orthogonal | | orthogonal | ||
| ? | | ? | ||
| [[ | | [[Dean Hickerson]] | ||
| [[:Category:Patterns found in 1989|1989]] | | [[:Category:Patterns found in 1989|1989]] | ||
|- | |- | ||
| Line 70: | Line 70: | ||
| orthogonal | | orthogonal | ||
| ? | | ? | ||
| [[ | | [[Dean Hickerson]] | ||
| [[:Category:Patterns found in 1989|1989]] | | [[:Category:Patterns found in 1989|1989]] | ||
|- | |- | ||
! 2c/5 | ! 2c/5 | ||
| orthogonal | | orthogonal | ||
| | | [[44P5H2V0]] | ||
| [[ | | [[Dean Hickerson]] | ||
| [[:Category:Patterns found in 1991|1991]] | | [[:Category:Patterns found in 1991|1991]] | ||
|- | |- | ||
| Line 82: | Line 82: | ||
| orthogonal | | orthogonal | ||
| [[snail]] | | [[snail]] | ||
| [[ | | [[Tim Coe]] | ||
| [[:Category:Patterns found in 1996|1996]] | | [[:Category:Patterns found in 1996|1996]] | ||
|- | |- | ||
| Line 88: | Line 88: | ||
| orthogonal | | orthogonal | ||
| [[dragon]] | | [[dragon]] | ||
| [[ | | [[Paul Tooke]] | ||
| [[:Category:Patterns found in 2000|2000]] | | [[:Category:Patterns found in 2000|2000]] | ||
|- | |- | ||
| Line 94: | Line 94: | ||
| orthogonal | | orthogonal | ||
| [[weekender]] | | [[weekender]] | ||
| [[ | | [[David Eppstein]] | ||
| [[:Category:Patterns found in 2000|2000]] | | [[:Category:Patterns found in 2000|2000]] | ||
|- | |- | ||
| Line 100: | Line 100: | ||
| orthogonal | | orthogonal | ||
| [[caterpillar]] | | [[caterpillar]] | ||
| [[ | | [[Gabriel Nivasch]] | ||
| [[:Category:Patterns found in 2004|2004]] | | [[:Category:Patterns found in 2004|2004]] | ||
|} | |} | ||
| Line 119: | Line 119: | ||
! c/4 | ! c/4 | ||
| diagonal | | diagonal | ||
| glider | | [[glider]] | ||
| [[:Category:Patterns with 5 cells|5]] | | [[:Category:Patterns with 5 cells|5]] | ||
|- | |- | ||
| Line 129: | Line 129: | ||
! c/6 | ! c/6 | ||
| diagonal | | diagonal | ||
| seal | | [[seal]] | ||
| [[:Category:Patterns with 170 cells|170]] | | [[:Category:Patterns with 170 cells|170]] | ||
|- | |- | ||
| Line 141: | Line 141: | ||
! c/2 | ! c/2 | ||
| orthogonal | | orthogonal | ||
| lightweight spaceship | | [[lightweight spaceship]] | ||
| [[:Category:Patterns with 9 cells|9]] | | [[:Category:Patterns with 9 cells|9]] | ||
|- | |- | ||
| Line 171: | Line 171: | ||
! 2c/7 | ! 2c/7 | ||
| orthogonal | | orthogonal | ||
| weekender | | [[weekender]] | ||
| [[:Category:Patterns with 36 cells|36]] | | [[:Category:Patterns with 36 cells|36]] | ||
|- | |- | ||
! 17c/45 | ! 17c/45 | ||
| orthogonal | | orthogonal | ||
| caterpillar | | [[caterpillar]] | ||
| [[:Category:Patterns with 1000 or more cells|11880063]] | | [[:Category:Patterns with 1000 or more cells|11880063]] | ||
|} | |} | ||
Revision as of 04:44, 11 August 2009

A spaceship (much less commonly referred to as a glider[1] or a fish[2]) 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 the 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,[3] 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.[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 program that uses iterative deepening depth-first searching,[6] 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. 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.[7]
The most recently discovered spaceship speed is that of the diagonal c/6 seal, found by Nicolay Beluchenko in 2005.[8]

| 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/12 | diagonal | 13-engine Cordership | Dean Hickerson | 1991 |
| c/2 | orthogonal | lightweight spaceship | John Conway | 1970 |
| c/3 | orthogonal | ? | Dean Hickerson | 1989 |
| c/4 | orthogonal | ? | 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 |
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; 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 two smaller spaceships.

| Speed | Direction | Smallest known | Minimum # of cells |
|---|---|---|---|
| c/4 | diagonal | glider | 5 |
| c/5 | diagonal | 67P5H1V1 | 67 |
| c/6 | diagonal | seal | 170 |
| 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 | 11880063 |
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.
- ↑ Gabriel Nivasch. "The 17c/45 Caterpillar spaceship". Gabriel Nivasch's Game of Life page.
- ↑ "c/6 Diagonal Spaceship". Game of Life News. Heinrich Koenig.
External links
- Spaceship at the Life Lexicon