Spaceship: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
Undo revision 38473 by AwesoMan3000 (talk)
→Engineered spaceships: I hate the edit conflict glitch with the fieriest of passions
Line 1: Line 1:
{{Glossary}}
===Engineered spaceships===
[[Image:lwss.gif|framed|right|The lightweight spaceship in [[Conway's Game of Life]]]]A '''spaceship''' (also referred to as a '''glider'''<ref>{{CiteLexicon|file=lex_g.htm#glider|name=Glider|accessdate=April 18, 2009}}</ref> or less commonly a '''fish'''<ref>{{CiteLexicon|file=lex_f.htm#fish|name=Fish|accessdate=April 18, 2009}}</ref>, and commonly shortened to "ship") 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.
''Engineered spaceships'', also known as ''caterpillars'' after the first known engineered spaceship, are defined as spaceships consisting of many small interacting components.<ref>{{cite web|url=https://niginsblog.wordpress.com/2016/03/07/new-spaceship-speed-in-conways-game-of-life/|title=New Spaceship Speed in Conway’s Game of Life|author=Alexey Nigin|date=7 Mar 2016|accessdate=11 Jun 2016}}</ref> Almost all engineered spaceships are composed of hundreds of thousands to well over millions of active cells. Engineered spaceships still have fixed speeds, and tend to rely on "[[crawler]]s", reactions in which a pattern reacts with another pattern, producing both the patterns in different positions; such as the [[pi crawler]].
 
__TOC__
 
==Spaceship Speed==
{{main|Speed}}
The speed of a spaceship is the number of [[cell]]s 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 orthogonal|2c/5]].
 
Until the construction of [[Gemini]] in May [[:Category:patterns found in 2010|2010]], all known spaceships in [[Conway's Game of Life|Life]] traveled either orthogonally (only horizontal or vertical displacement) or diagonally (equal horizontal and vertical displacement); other oblique spaceships have been constructed since then, e.g. [[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 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>
 
The maximum speed for Life is [[c/2 orthogonal]] and [[c/4 diagonal]]<ref>http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/</ref> (and continually, c/6 for slope 2, c/8 for slope 3, etc.); however, certain [[agar crawler]]s such as [[lightspeed wire]] can break this speed in their respective medium. Spaceships in the traditional [[Moore neighbourhood]] of range 1 have a maximum speed of c, although [[Larger than Life]] neighbourhoods can increase this limit depending on the interactable distance between cells.
 
==Spaceship types==
{{main|List of spaceships}}
Spaceships are most commonly sorted by their speed and direction, and sometimes their period. They can be separated into three fundamental categories:
 
===Elementary spaceships===
[[Image:AlmostKnightship.png|framed|right|An "almost knightship"]]
''Elementary spaceships'' are the smallest classification of spaceships. This class consists of naturally-occurring ships, as well as those found by direct computer search, such as the [[weekender]]. Despite their generally small size, only a few of them have been known to have emerged from [[soup]]s. Constructing [[gun]]s for these spaceships is usually difficult, as only a few elementary spaceships have known glider syntheses; those who do generally require a lot of gliders in awkward positions. Only elementary spaceships which move orthogonally or diagonally have been found; there are currently no known elementary [[knightship]]s or other slopes (however, there have been [[Almost knightship|some close calls]]).


{| class="wikitable"
{| class="wikitable"
Line 31: Line 11:
! [[c/2 orthogonal|c/2]]
! [[c/2 orthogonal|c/2]]
| orthogonal
| orthogonal
| [[lightweight spaceship]]
| [[pufferfish]] spaceship
| [[:Category:Patterns with 9 cells|9]]
| [[:Category:Patterns with 235 cells|235]]
|-
! [[c/3 orthogonal|c/3]]
| orthogonal
| [[25P3H1V0.2]]
| [[:Category:Patterns with 25 cells|25]]
|-
! [[c/4 orthogonal|c/4]]
| orthogonal
| [[37P4H1V0]]
| [[:Category:Patterns with 37 cells|37]]
|-
! [[c/5 orthogonal|c/5]]
| orthogonal
| [[spider]]
| [[:Category:Patterns with 58 cells|58]]
|-
! [[c/6 orthogonal|c/6]]
| orthogonal
| [[56P6H1V0]]
| [[:Category:Patterns with 56 cells|56]]
|-
! [[c/7 orthogonal|c/7]]
| orthogonal
| [[loafer]]
| [[:Category:Patterns with 20 cells|20]]
|-
! [[c/10 orthogonal|c/10]]
| orthogonal
| [[copperhead]]
| [[:Category:Patterns with 28 cells|28]]
|-
! [[2c/5 orthogonal|2c/5]]
| orthogonal
| [[30P5H2V0]]
| [[:Category:Patterns with 30 cells|30]]
|-
! [[2c/7 orthogonal|2c/7]]
| orthogonal
| [[weekender]]
| [[:Category:Patterns with 36 cells|36]]
|-
! [[3c/7 orthogonal|3c/7]]
| orthogonal
| [[spaghetti monster]]
| [[:Category:Patterns with 702 cells|702]]
|-
! colspan="5" |
|-
! [[c/4 diagonal|c/4]]
| diagonal
| [[glider]]
| [[:Category:Patterns with 5 cells|5]]
|-
! [[c/5 diagonal|c/5]]
| diagonal
| [[58P5H1V1]]
| [[:Category:Patterns with 58 cells|58]]
|-
! [[c/6 diagonal|c/6]]
| diagonal
| [[77P6H1V1]]
| [[:Category:Patterns with 77 cells|77]]
|-
! [[c/7 diagonal|c/7]]
| diagonal
| [[Lobster_(spaceship)|lobster]]
| [[:Category:Patterns with 83 cells|83]]
|-
|}
 
===Engineered spaceships===
''Engineered spaceships'', also known as ''caterpillars'' after the first known engineered spaceship, are defined as spaceships consisting of many small interacting components.<ref>{{cite web|url=https://niginsblog.wordpress.com/2016/03/07/new-spaceship-speed-in-conways-game-of-life/|title=New Spaceship Speed in Conway’s Game of Life|author=Alexey Nigin|date=7 Mar 2016|accessdate=11 Jun 2016}}</ref> Almost all engineered spaceships are composed of hundreds of thousands to well over millions of active cells. Engineered spaceships still have fixed speeds, and tend to rely on "[[crawler]]s", reactions in which a pattern reacts with another pattern, producing both the patterns in different positions; such as the [[pi crawler]].
 
{| class="wikitable"
|-
! Speed
! Direction
! Smallest known
! Minimum # of [[cell]]s
|-
|-
! [[17c/45 orthogonal|17c/45]]
! [[17c/45 orthogonal|17c/45]]
Line 138: Line 39:
|-
|-
|}
|}
=== Engineerable spaceships ===
''Engineerable spaceships'' (or ''adjustable spaceships'') are the third class of spaceships. Although on average smaller than the engineered spaceships, their magic comes from having (to an extent) adjustable features, usually speed. With some almost always trivial modifications, these spaceships can be made to travel at different velocities and even directions. Rather than being searched for, programs exist that explicitly construct the spaceships. Engineerable spaceships can run on engineerable reactions, such as the half-bakery and glider reaction, or by reading instruction tapes, such as Gemini. Families of engineerable spaceships include the geminoids, demonoids, half-baked knightships and caterloopillars.
{| class="wikitable"
|-
! Speed
! Direction
! Smallest known
! Minimum # of [[cell]]s
|-
! [[31c/240 orthogonal|31c/240]]
| orthogonal
| [[centipede caterloopillar]]
| [[:Category:Patterns with 1000 or more cells|361,070]]
|-
! [[c/8 orthogonal|c/8]]
| orthogonal
| [[Caterloopillar|Original caterloopillar]]
| [[:Category:Patterns with 1000 or more cells|232,815]]
|-
! [[c/8 orthogonal|All speeds slower than c/4]]
| orthogonal
| [[Caterloopillar|other caterloopillars]]
| [[:Category:Patterns with 1000 or more cells|Varies]]
|-
! [[c/16384 orthogonal|c/16384]]
| orthogonal
| [[Hashlife-friendly Orthogonoid]]
| [[:Category:Patterns with 1000 or more cells|A lot]]
|-
! [[c/32768 orthogonal|c/32768]]
| orthogonal
| [[Double-wide Orthogonoid]]
| [[:Category:Patterns with 1000 or more cells|A lot]]
|-
! colspan="5" |
|-
! (5120,1024)c/16849793
| slope 5 (ibiswise)
| [[Gemini]]
| [[:Category:Patterns with 1000 or more cells|846,278]]
|-
! (3072,1024)c/36000001
| slope 3 (camelwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2590 Gemini 3]
| <=850932
|-
! (4096,2048)c/17783745
| slope 2 (knightwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2578 Gemini 2]
| <=872252
|-
! (6,3)c/245912
| slope 2 (knightwise)
| [[Parallel HBK]]
| [[:Category:Patterns with 1000 or more cells|132,945]]
|-
! (6,3)c/2621440
| slope 2 (knightwise)
| [[Half-baked knightship]]
| [[:Category:Patterns with 1000 or more cells|1,049,395]]
|-
! colspan="5" |
|-
! 65c/438852
| diagonal
| [[Demonoid|0hd Demonoid]]
| [[:Category:Patterns with 1000 or more cells|27,250]]
|-
! 65c/818356
| diagonal
| [[Demonoid|10hd Demonoid]]
| [[:Category:Patterns with 1000 or more cells|47,701]]
|-
|}
=== Other classifications ===
{{main|Types of spaceships|Spaceship types}}
[[Image:Greyship2_H_Holzwart.png|framed|right|A greyship found by [[Hartmut Holzwart]]]]
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 (e.g. copperhead), exhibit [[Types_of_spaceships#Glide_symmetric_spaceship|glide symmetry]] (e.g. glider), or simply be asymmetric (e.g. loafer).  Other somewhat subjective categorizations have also been made, such as [[greyship]]s, spaceships filled with large amounts of static, live cells, or [[Types_of_spaceships#Smoking_ship|smoking ships]], <!--and frothing ships?-->which produce large [[spark]]s, 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 [[tagalong]]s; however they can be attached to any side of a spaceship, such as [[pushalong 1]] and [[sidecar]]. Unstable spaceships immersed in a sustaining cloud are known as [[Types_of_spaceships#Flotilla|flotillae]]. A well known example is that of the [[overweight spaceship]]s, which are unstable alone but may be 'escorted' by two or more smaller spaceships.
==History==
===1970s===
[[Image:mwss.gif|framed|right|A middleweight spaceship]]
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]]s to the known [[c/2 orthogonal|c/2]] spaceships, such as the Schick engine.
===1980s===
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]] and [[c/4 orthogonal|c/4]], new [[c/2 orthogonal|c/2]] ships, and the first spaceship other than the glider to travel at the speed of [[c/4 diagonal]]ly, dubbed the [[big glider]].
===1990s===
Hickerson continued to find new spaceship speeds, the first of this decade being [[2c/5 orthogonal]], plus several ways to combine [[switch engine]]s to create the first [[c/12 diagonal]] 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 [[:Category:patterns found in 1998|1998]] [[David Eppstein]] created [[gfind]], a breadth-first program that uses a depth-first search to limit the size of the search queue.<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>
===2000s===
[[Image:weekender_small.gif|framed|right|David Eppstein's weekender]]
Eppstein put his search program to good use in [[:Category:patterns found in 2000|2000]], discovering the first spaceship that travels at the speed of [[2c/7 orthogonal]]ly, 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 [[: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, which made use of the [[17c/45 reaction]].
===2010s===
[[File:Loafer.gif|framed|right|Josh Ball's loafer]]
In May [[:Category:patterns found in 2010|2010]] [[Andrew J. Wade]] created a universal constructor-based spaceship, [[Gemini]], which travels at a speed of (5120,1024)c/33699586.<ref>{{cite web|url=http://pentadecathlon.com/lifeNews/2010/05/oblique_life_spaceship_created.html|title=Oblique Life spaceship created|date=May 19, 2010|work=Game of Life News|author=Adam P. Goucher|accessdate=May 21, 2010}}</ref> This was the first explicitly constructed spaceship in Life to travel in an [[Types_of_spaceships#Knightship|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.
2014 provided a handful of new engineered spaceships, using various new technologies. In July, several [[half-baked knightship|half-bakery-based knightships]] were constructed with a new technique not requiring universal-constructor circuitry. These produced spaceships that were both much slower and much smaller than the Gemini variants. In September, [[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. Finally, in December, an oblique caterpillar dubbed the [[Waterbear]] was completed by Brett Berger, traveling at (23,5)c/79. Richard Schank discovered [[pufferfish]], a c/2 puffer, and Ivan Fomichev found a c/2 fuse for its exhaust and combined two pufferfish with fuses to assemble the first wholly high-period c/2 spaceship.
In December 2015, Chris Cain completed a diagonal self-constructing spaceship -- a [[Demonoid|"0hd Demonoid"]] -- based on Geminoid technology, adapted from a larger 10hd version constructed in November in collaboration with Dave Greene.
[[File:Copperhead.gif|framed|right|The copperhead spaceship.]]
In March 2016, forum user 'zdr' discovered [[copperhead]], an extremely small c/10 spaceship. A [[Fireship|pseudo-tagalong]] for this spaceship, alongside many other c/10 technologies, were constructed within two months after the discovery of the ship.
In April 2016 Michael Simkin finished the adjustable [[caterloopillar]] project, making it possible to build spaceships of arbitrary orthogonal speeds slower than c/4.
In June 2016 Tim Coe found a large elementary 3c/7 orthogonal spaceship, [[702P7H3V0]].
{| class="wikitable"
|-
! Speed
! Direction
! First discovered
! Discoverer
! Year of discovery
|-
! c/4
| diagonal
| [[glider]]
| [[Richard Guy]]
| [[:Category:Patterns found in 1970|1970]]
|-
! c/2
| orthogonal
| [[lightweight spaceship]]
| [[John Conway]]
| [[:Category:Patterns found in 1970|1970]]
|-
! c/3
| orthogonal
| [[25P3H1V0.2]]
| [[Dean Hickerson]]
| [[:Category:Patterns found in 1989|1989]]
|-
! c/4
| orthogonal
| [[119P4H1V0]]
| [[Dean Hickerson]]
| [[:Category:Patterns found in 1989|1989]]
|-
! c/12
| diagonal
| [[13-engine Cordership]]
| [[Dean Hickerson]]
| [[:Category:Patterns found in 1991|1991]]
|-
! 2c/5
| orthogonal
| [[44P5H2V0]]
| [[Dean Hickerson]]
| [[:Category:Patterns found in 1991|1991]]
|-
! c/5
| orthogonal
| [[snail]]
| [[Tim Coe]]
| [[:Category:Patterns found in 1996|1996]]
|-
! 2c/7
| orthogonal
| [[weekender]]
| [[David Eppstein]]
| [[:Category:Patterns found in 2000|2000]]
|-
! c/6
| orthogonal
| [[dragon]]
| [[Paul Tooke]]
| [[:Category:Patterns found in 2000|2000]]
|-
! c/5
| diagonal
| [[295P5H1V1]]
| [[Jason Summers]]
| [[:Category:Patterns found in 2000|2000]]
|-
! 17c/45
| orthogonal
| [[caterpillar]]
| [[Gabriel Nivasch]], [[Jason Summers]], and [[David Bell]]
| [[:Category:Patterns found in 2004|2004]]
|-
! c/6
| diagonal
| [[seal]]
| [[Nicolay Beluchenko]]
| [[:Category:Patterns found in 2005|2005]]
|-
! (5120,1024)c/16849793
| slope 5 (ibiswise)
| [[Gemini]]
| [[Andrew J. Wade]]
| [[:Category:Patterns found in 2010|2010]]
|-
! (4096,2048)c/17783745
| slope 2 (knightwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2578 Gemini 2]
| [[Dave Greene]]
| [[:Category:Patterns found in 2010|2010]]
|-
! (3072,1024)c/36000001
| slope 3 (camelwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2590 Gemini 3]
| [[Dave Greene]]
| [[:Category:Patterns found in 2010|2010]]
|-
! c/7
| diagonal
| [[Lobster]]
| [[Matthias Merzenich]]
| [[:Category:Patterns found in 2011|2011]]
|-
! c/7
| orthogonal
| [[loafer]]
| [[Josh Ball]]
| [[:Category:Patterns found in 2013|2013]]
|-
! (6,3)c/2621440
| slope 2 (knighwise)
| [[Half-baked knightship]]
| [[Adam P. Goucher]]
| [[:Category:Patterns found in 2014|2014]]
|-
! (6,3)c/245912
| slope 2 (knightwise)
| [[Parallel HBK]]
| [[Chris Cain]]
| [[:Category:Patterns found in 2014|2014]]
|-
! 31c/240
| orthogonal
| [[shield bug]]
| [[Dave Greene]]
| [[:Category:Patterns found in 2014|2014]]
|-
! (23,5)c/79
| slope 23/5
| [[waterbear]]
| [[Brett Berger]]
| [[:Category:Patterns found in 2014|2014]]
|-
! 130c/(1636712+16N)
| diagonal
| [[Demonoid|10hd Demonoid]]
| [[Chris Cain]] and [[Dave Greene]]
| [[:Category:Patterns found in 2015|2015]]
|-
! 65c/(438852+16N)
| diagonal
| [[Demonoid|0hd Demonoid]]
| [[Chris Cain]]
| [[:Category:Patterns found in 2015|2015]]
|-
! c/10
| orthogonal
| [[Copperhead‎‎]]
| [[zdr]]
| [[:Category:Patterns found in 2016|2016]]
|-
! All speeds slower than c/4
| orthogonal
| [[caterloopillar]]
| [[Michael Simkin]]
| [[:Category:Patterns found in 2016|2016]]
|-
! 3c/7
| orthogonal
| [[702P7H3V0]]
| [[Tim Coe]]
| [[:Category:Patterns found in 2016|2016]]
|}
==See also==
*[[:Category:Spaceships|List of spaceships]]
*[[Spaceship flotilla]]
*[[LifeWiki:Game_of_Life_Status_page#Spaceship_periods|Spaceship periods status table]]
*[[Spaceship terminology]]
*[[Types of spaceships]]
*[[LifeWiki:Game_of_Life_Status_page#Velocities_of_spaceships_and_related_objects|Velocities of spaceships and related objects status table]]
*[[HighLife#Spaceships|Spaceships of HighLife]]
==Notes==
<references/>
==External links==
{{LinkLexicon|filename=lex_s.htm#spaceship|patternname=Spaceship}}
{{LinkWeisstein|filename=Spaceship.html|patternname=Spaceship}}

Revision as of 16:14, 3 July 2017

Engineered spaceships

Engineered spaceships, also known as caterpillars after the first known engineered spaceship, are defined as spaceships consisting of many small interacting components.[1] Almost all engineered spaceships are composed of hundreds of thousands to well over millions of active cells. Engineered spaceships still have fixed speeds, and tend to rely on "crawlers", reactions in which a pattern reacts with another pattern, producing both the patterns in different positions; such as the pi crawler.

Speed Direction Smallest known Minimum # of cells
c/2 orthogonal pufferfish spaceship 235
17c/45 orthogonal caterpillar 11,880,063
31c/240 orthogonal centipede 620,901
c/12 diagonal 4-engine Cordership 134
(23,5)c/79 slope 23/5 waterbear 197,896
  1. ↑ Alexey Nigin (7 Mar 2016). "New Spaceship Speed in Conway’s Game of Life". Retrieved on 11 Jun 2016.