Difference between revisions of "Spaceship"

From LifeWiki
Jump to navigation Jump to search
(24 intermediate revisions by 3 users not shown)
Line 6: Line 6:
==Spaceship Speed==
==Spaceship Speed==
{{main|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 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==
==Spaceship types==
Line 14: Line 20:
===Elementary spaceships===
===Elementary spaceships===
[[Image:AlmostKnightship.png|framed|right|An "almost knightship"]]
[[Image:AlmostKnightship.png|framed|right|An "almost knightship"]]
''Elementary spaceships'' are the smallest classification of spaceships. This class consists of ships found by direct computer search, such as the [[weekender]], as well as ships composed of a small number of natural moving components, such as [[Cordership]]s. 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 (however, there have been [[Almost knightship|some close calls]]).
''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 27: Line 33:
| [[lightweight spaceship]]
| [[lightweight spaceship]]
| [[:Category:Patterns with 9 cells|9]]
| [[:Category:Patterns with 9 cells|9]]
|-
! [[3c/7 orthogonal|3c/7]]
| orthogonal
| [[spaghetti monster]]
| [[:Category:Patterns with 702 cells|702]]
|-
! [[2c/5 orthogonal|2c/5]]
| orthogonal
| [[30P5H2V0]]
| [[:Category:Patterns with 30 cells|30]]
|-
|-
! [[c/3 orthogonal|c/3]]
! [[c/3 orthogonal|c/3]]
Line 42: Line 38:
| [[25P3H1V0.2]]
| [[25P3H1V0.2]]
| [[:Category:Patterns with 25 cells|25]]
| [[:Category:Patterns with 25 cells|25]]
|-
! [[2c/7 orthogonal|2c/7]]
| orthogonal
| [[weekender]]
| [[:Category:Patterns with 36 cells|36]]
|-
|-
! [[c/4 orthogonal|c/4]]
! [[c/4 orthogonal|c/4]]
Line 72: Line 63:
| [[copperhead]]
| [[copperhead]]
| [[:Category:Patterns with 28 cells|28]]
| [[: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" |
! colspan="5" |
Line 94: Line 100:
| [[Lobster_(spaceship)|lobster]]
| [[Lobster_(spaceship)|lobster]]
| [[:Category:Patterns with 83 cells|83]]
| [[:Category:Patterns with 83 cells|83]]
|-
! [[c/12 diagonal|c/12]]
| diagonal
| [[4-engine Cordership]]
| [[:Category:Patterns with 134 cells|134]]
|-
|-
|}
|}


===Engineered spaceships===
===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]].
''Engineered spaceships'', also known as ''caterpillars'' after the first known engineered spaceship, are defined as spaceships consisting of 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> Some engineered spaceships are composed of hundreds of thousands to well over millions of active cells, with others reaching into the low hundreds. Engineered spaceships still have fixed speeds, some relying on "[[crawler]]s", reactions in which a pattern reacts with another pattern, producing both the patterns in different positions; such as the [[pi crawler]], and others relying on ''stabilised [[puffer]] engines''.


{| class="wikitable"
{| class="wikitable"
Line 111: Line 112:
! Smallest known
! Smallest known
! Minimum # of [[cell]]s
! Minimum # of [[cell]]s
|-
! [[c/2 orthogonal|c/2]]
| orthogonal
| [[pufferfish]] spaceship
| [[:Category:Patterns with 235 cells|235]]
|-
|-
! [[17c/45 orthogonal|17c/45]]
! [[17c/45 orthogonal|17c/45]]
Line 124: Line 130:
! colspan="5" |
! colspan="5" |
|-
|-
! (23,5)c/79
! [[c/12 diagonal|c/12]]
| diagonal
| [[4-engine Cordership]]
| [[:Category:Patterns with 134 cells|134]]
|-
! colspan="5" |
|-
! [[:Category:Spaceships with speed (23,5)c/79|(23,5)c/79]]
| slope 23/5
| slope 23/5
| [[waterbear]]
| [[waterbear]]
Line 133: Line 146:
=== Engineerable spaceships ===
=== Engineerable spaceships ===


''Engineerable spaceships'' are the third class of spaceships. Although on average smaller than the engineered spaceships, their magic comes from having (to an extent) adjustable speeds. With some usually 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.
''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"
{| class="wikitable"
Line 156: Line 169:
| [[Caterloopillar|other caterloopillars]]
| [[Caterloopillar|other caterloopillars]]
| [[:Category:Patterns with 1000 or more cells|Varies]]
| [[: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" |
! colspan="5" |
|-
|-
! (5120,1024)c/16849793
! (5120,1024)c/16849793
| slope 5
| slope 5 (ibiswise)
| [[Gemini]]
| [[Gemini]]
| [[:Category:Patterns with 1000 or more cells|846,278]]
| [[:Category:Patterns with 1000 or more cells|846,278]]
|-
|-
! (3072,1024)c/36000001
! (3072,1024)c/36000001
| camelwise
| slope 3 (camelwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2590 Gemini 3]
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2590 Gemini 3]
| <=850932
| <=850932
|-
|-
! (4096,2048)c/17783745
! (4096,2048)c/17783745
| knightwise
| slope 2 (knightwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2578 Gemini 2]
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2578 Gemini 2]
| <=872252
| <=872252
|-
|-
! (6,3)c/245912
! (6,3)c/245912
| knightwise
| slope 2 (knightwise)
| [[Parallel HBK]]
| [[Parallel HBK]]
| [[:Category:Patterns with 1000 or more cells|132,945]]
| [[:Category:Patterns with 1000 or more cells|132,945]]
|-
|-
! (6,3)c/2621440
! (6,3)c/2621440
| knightwise
| slope 2 (knightwise)
| [[Half-baked knightship]]
| [[Half-baked knightship]]
| [[:Category:Patterns with 1000 or more cells|1,049,395]]
| [[:Category:Patterns with 1000 or more cells|1,049,395]]
Line 210: Line 233:


===1980s===
===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]], [[c/4 orthogonal|c/4]], and [[2c/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 [[c/12 diagonal]] spaceships, named [[Cordership]]s in honour of [[Charles Corderman]].
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===
===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>
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>  
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===
===2000s===
Line 234: Line 259:


[[File:Copperhead.gif|framed|right|The copperhead spaceship.]]
[[File:Copperhead.gif|framed|right|The copperhead spaceship.]]
In March 2016, forum user 'zdr' discovered [[copperhead]], an extremely small c/10 spaceship. A tagalong for this spaceship, alongside many other c/10 technologies, were constructed within two months after the discovery of the ship.
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 April 2016 Michael Simkin finished the adjustable [[caterloopillar]] project, making it possible to build spaceships of arbitrary orthogonal speeds slower than c/4.
Line 320: Line 345:
|-
|-
! (5120,1024)c/16849793
! (5120,1024)c/16849793
| slope 5
| slope 5 (ibiswise)
| [[Gemini]]
| [[Gemini]]
| [[Andrew J. Wade]]
| [[Andrew J. Wade]]
Line 326: Line 351:
|-
|-
! (4096,2048)c/17783745
! (4096,2048)c/17783745
| slope 2
| slope 2 (knightwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2578 Gemini 2]
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2578 Gemini 2]
| [[Dave Greene]]
| [[Dave Greene]]
Line 332: Line 357:
|-
|-
! (3072,1024)c/36000001
! (3072,1024)c/36000001
| slope 3
| slope 3 (camelwise)
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2590 Gemini 3]
| [http://www.conwaylife.com/forums/viewtopic.php?f=2&t=406&start=25#p2590 Gemini 3]
| [[Dave Greene]]
| [[Dave Greene]]
Line 350: Line 375:
|-
|-
! (6,3)c/2621440
! (6,3)c/2621440
| slope 2
| slope 2 (knighwise)
| [[Half-baked knightship]]
| [[Half-baked knightship]]
| [[Adam P. Goucher]]
| [[Adam P. Goucher]]
Line 356: Line 381:
|-
|-
! (6,3)c/245912
! (6,3)c/245912
| slope 2
| slope 2 (knightwise)
| [[Parallel HBK]]
| [[Parallel HBK]]
| [[Chris Cain]]
| [[Chris Cain]]

Revision as of 14:32, 4 July 2017

The lightweight spaceship in Conway's Game of Life

A spaceship (also referred to as a glider[1] or less commonly a fish[2], and commonly shortened to "ship") 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); 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 automata.[3]

The maximum speed for Life is c/2 orthogonal and c/4 diagonal[4] (and continually, c/6 for slope 2, c/8 for slope 3, etc.); however, certain agar crawlers 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 article: 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

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 soups. Constructing guns 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 knightships or other slopes (however, there have been some close calls).

Speed Direction Smallest known Minimum # of cells
c/2 orthogonal lightweight spaceship 9
c/3 orthogonal 25P3H1V0.2 25
c/4 orthogonal 37P4H1V0 37
c/5 orthogonal spider 58
c/6 orthogonal 56P6H1V0 56
c/7 orthogonal loafer 20
c/10 orthogonal copperhead 28
2c/5 orthogonal 30P5H2V0 30
2c/7 orthogonal weekender 36
3c/7 orthogonal spaghetti monster 702
c/4 diagonal glider 5
c/5 diagonal 58P5H1V1 58
c/6 diagonal 77P6H1V1 77
c/7 diagonal lobster 83

Engineered spaceships

Engineered spaceships, also known as caterpillars after the first known engineered spaceship, are defined as spaceships consisting of small interacting components.[5] Some engineered spaceships are composed of hundreds of thousands to well over millions of active cells, with others reaching into the low hundreds. Engineered spaceships still have fixed speeds, some relying on "crawlers", reactions in which a pattern reacts with another pattern, producing both the patterns in different positions; such as the pi crawler, and others relying on stabilised puffer engines.

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

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.

Speed Direction Smallest known Minimum # of cells
31c/240 orthogonal centipede caterloopillar 361,070
c/8 orthogonal Original caterloopillar 232,815
All speeds slower than c/4 orthogonal other caterloopillars Varies
c/16384 orthogonal Hashlife-friendly Orthogonoid A lot
c/32768 orthogonal Double-wide Orthogonoid A lot
(5120,1024)c/16849793 slope 5 (ibiswise) Gemini 846,278
(3072,1024)c/36000001 slope 3 (camelwise) Gemini 3 <=850932
(4096,2048)c/17783745 slope 2 (knightwise) Gemini 2 <=872252
(6,3)c/245912 slope 2 (knightwise) Parallel HBK 132,945
(6,3)c/2621440 slope 2 (knightwise) Half-baked knightship 1,049,395
65c/438852 diagonal 0hd Demonoid 27,250
65c/818356 diagonal 10hd Demonoid 47,701

Other classifications

Main article: Spaceship types
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 glide symmetry (e.g. glider), or simply be asymmetric (e.g. loafer). 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; 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 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.

History

1970s

A middleweight spaceship

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, such as the Schick engine.

1980s

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 and c/4, new c/2 ships, and the first spaceship other than the glider to travel at the speed of c/4 diagonally, 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 engines to create the first c/12 diagonal 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.[6] In the following year, David Bell found the much smaller c/5 spider using lifesrc, a program based on Hickerson's search algorithm.[7]

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.[8]

2000s

David Eppstein's weekender

Eppstein put his search program to good use in 2000, discovering 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.

2010s

Josh Ball's loafer

In May 2010 Andrew J. Wade created a universal constructor-based spaceship, Gemini, which travels at a speed of (5120,1024)c/33699586.[9] 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.

2014 provided a handful of new engineered spaceships, using various new technologies. In July, several 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 "0hd Demonoid" -- based on Geminoid technology, adapted from a larger 10hd version constructed in November in collaboration with Dave Greene.

The copperhead spaceship.

In March 2016, forum user 'zdr' discovered copperhead, an extremely small c/10 spaceship. A 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.

Speed Direction First discovered Discoverer Year of discovery
c/4 diagonal glider Richard Guy 1970
c/2 orthogonal lightweight spaceship John Conway 1970
c/3 orthogonal 25P3H1V0.2 Dean Hickerson 1989
c/4 orthogonal 119P4H1V0 Dean Hickerson 1989
c/12 diagonal 13-engine Cordership Dean Hickerson 1991
2c/5 orthogonal 44P5H2V0 Dean Hickerson 1991
c/5 orthogonal snail Tim Coe 1996
2c/7 orthogonal weekender David Eppstein 2000
c/6 orthogonal dragon Paul Tooke 2000
c/5 diagonal 295P5H1V1 Jason Summers 2000
17c/45 orthogonal caterpillar Gabriel Nivasch, Jason Summers, and David Bell 2004
c/6 diagonal seal Nicolay Beluchenko 2005
(5120,1024)c/16849793 slope 5 (ibiswise) Gemini Andrew J. Wade 2010
(4096,2048)c/17783745 slope 2 (knightwise) Gemini 2 Dave Greene 2010
(3072,1024)c/36000001 slope 3 (camelwise) Gemini 3 Dave Greene 2010
c/7 diagonal Lobster Matthias Merzenich 2011
c/7 orthogonal loafer Josh Ball 2013
(6,3)c/2621440 slope 2 (knighwise) Half-baked knightship Adam P. Goucher 2014
(6,3)c/245912 slope 2 (knightwise) Parallel HBK Chris Cain 2014
31c/240 orthogonal shield bug Dave Greene 2014
(23,5)c/79 slope 23/5 waterbear Brett Berger 2014
130c/(1636712+16N) diagonal 10hd Demonoid Chris Cain and Dave Greene 2015
65c/(438852+16N) diagonal 0hd Demonoid Chris Cain 2015
c/10 orthogonal Copperhead‎‎ zdr 2016
All speeds slower than c/4 orthogonal caterloopillar Michael Simkin 2016
3c/7 orthogonal 702P7H3V0 Tim Coe 2016

See also

Notes

  1. "Glider". The Life Lexicon. Stephen Silver. Retrieved on April 18, 2009.
  2. "Fish". The Life Lexicon. Stephen Silver. Retrieved on April 18, 2009.
  3. "Gliders in Life-Like Cellular Automata". David Eppstein. Retrieved on April 18, 2009.
  4. http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/
  5. Alexey Nigin (7 Mar 2016). "New Spaceship Speed in Conway’s Game of Life". Retrieved on 11 Jun 2016.
  6. Tim Coe. "c/5 Orthogonal spaceship". Paul's Page of Conway's Life Miscellany. Retrieved on April 18, 2009.
  7. David Bell. "New c/5 spaceship". Paul's Page of Conway's Life Miscellany. Retrieved on April 18, 2009.
  8. David Eppstein. "Searching for Spaceships (PDF)". Retrieved on April 18, 2009.
  9. Adam P. Goucher (May 19, 2010). "Oblique Life spaceship created". Game of Life News. Retrieved on May 21, 2010.

External links

Template:LinkWeisstein