Difference between revisions of "Spaceship"
m (→External links: removed a link that now appears as a reference) |
(added to the history section, but it still needs references (I wrote it based on what I know, so there might be some mistakes)) |
||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
[[Image:lwss.gif|framed|right|A lightweight spaceship]]A '''spaceship''' (much less commonly referred to as a '''glider'''<ref> | [[Image:lwss.gif|framed|right|A lightweight spaceship]]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 generations (known as its [[Period#Spaceships|period]]) but in a different location. | ||
| Line 11: | Line 11: | ||
==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]] the known c/2 spaceships. Significant advances in spaceship technology came | 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, 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 a way to combine [[switch engine]]s to create the first diagonal c/12 spaceship. 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<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 a smaller c/5 spaceship 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 search program that used a combination of breadth first search and depth first iterated deepening<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 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<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 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=H. Koenig}}</ref>. | |||
<table border="0" cellpadding="0" cellspacing="0" width="100%"><tr><td align="center" width="50%"> | <table border="0" cellpadding="0" cellspacing="0" width="100%"><tr><td align="center" width="50%"> | ||
Revision as of 22:35, 18 April 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 a speed of 2c/5. All known spaceships in life travel either orthogonally (displacement in only the x or y direction) or diagonally (equal displacement in both the x and y directions) 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, 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 a way to combine switch engines to create the first diagonal c/12 spaceship. 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[4]. In the following year David Bell found a smaller c/5 spaceship using Lifesrc, a program based on Hickerson's search algorithm[5].
In March of 1998 David Eppstein created gfind, a search program that used a combination of breadth first search and depth first iterated deepening[6], 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[7].
The most recently discovered spaceship speed is the diagonal c/6 seal, found by Nicolay Beluchenko in 2005[8].
|
|
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. H. Koenig.
External links
- Spaceship at the Life Lexicon