Spaceship

From LifeWiki
Jump to navigation Jump to search
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, (2, 1)c/6 for slope 2, (3, 1)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. For Life, no spaceship can move at speed (m,n)c/x where (m+n)/x > 0.5; for other outer-totalistic and non-totalistic rules, the limit is at most 1. Certain range-1 non-isotropic rules can harbour c diagonal spaceships, giving a limit of 2.

Spaceship types

Main article: Types 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

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 elementary spaceships is usually difficult, as only a few have known glider syntheses (with those that do generally requiring a lot of gliders in awkward positions), with larger elementary spaceships tending to contain high concentrations of space dust.

The following table lists the smallest known cases for the lowest possible periods for each speed:

Speed Slope Direction Smallest known Minimum # of cells
c/2 0 orthogonal 64P2H1V0 64
c/3 0 orthogonal 25P3H1V0.1[n 1] 25
c/4 0 orthogonal 37P4H1V0 37
c/5 0 orthogonal spider 58
2c/5 0 orthogonal 30P5H2V0 30
c/6 0 orthogonal 56P6H1V0 56
c/7 0 orthogonal loafer 20
2c/7 0 orthogonal weekender 36
3c/7 0 orthogonal 232P7H3V0 232
c/10 0 orthogonal copperhead 28
c/4 1 diagonal glider 5
c/5 1 diagonal 58P5H1V1 58
c/6 1 diagonal 77P6H1V1 77
c/7 1 diagonal lobster 83
c/8 1 diagonal walrus 68
(2,1)c/6 2 knightwise Sir Robin 282
  1. 25P3H1V0.2 has the same population of 25, but has a more expansive bounding box

The following is an incomplete list of some higher-period ships which travel at the same velocities:[5]

Speed Direction Smallest known Minimum # of cells
2c/4 orthogonal lightweight spaceship 9
3c/6 orthogonal 86P6H3V0 86
2c/6 orthogonal 72P6H2V0 72
4c/8 orthogonal 31P8H4V0 31
2c/8 orthogonal 74P8H2V0 74
3c/9 orthogonal 55P9H3V0 55
5c/10 orthogonal 214P10H5V0 214
4c/10 orthogonal 66P10H4V0 66
2c/10 orthogonal 81P10H2V0 81
6c/12 orthogonal 35P12H6V0 35
4c/12 orthogonal 103P12H4V0 103
3c/12 orthogonal 314P12H3V0 314
2c/12 orthogonal 861P12H2V0 861
7c/14 orthogonal 174P14H7V0 174
5c/15 orthogonal 112P15H5V0 112
3c/15 orthogonal p15 pre-pulsar spaceship 252[6]
8c/16 orthogonal Coe ship 28
9c/18 orthogonal 293P18H9V0 293
6c/18 orthogonal 242P18H6V0 242
3c/18 orthogonal 861P18H3V0 861
10c/20 orthogonal sidewinder 32
2c/20 orthogonal fireship tagalong 131
6c/21 orthogonal doo-dah 74
11c/22 orthogonal 213P22H11V0 213
12c/24 orthogonal 39P24H12V0 39
12c/28 orthogonal 3c/7 wave stabilization 307
6c/30 orthogonal pre-pulsar spaceship 128
18c/36 orthogonal 35P12H6V0 with pufferfish tagalong 102
2c/8 diagonal p8 swan tagalong 117
3c/12 diagonal 142P12H3V3 142

Engineered spaceships

Engineered spaceships are defined as spaceships consisting of small interacting components.[7] Some engineered spaceships are composed of hundreds of thousands or even millions of active cells; these are also sometimes referred to as caterpillars after the first engineered macro-spaceship. Other simpler mechanisms like the Corderships might need a relatively small number of components, down to a minimum of just two for the 2-engine Cordership. Such spaceships have occurred naturally in other rules, but not yet in Conway Life.

Engineered spaceships have fixed speeds, because their mechanisms depend on supporting a specific active reaction that travels at one particular speed. Some rely on "crawlers", reactions in which a pattern reacts with another pattern, producing both the patterns in different positions as in the pi crawler. Others, like the Corderships and pufferfish spaceships, rely on stabilised puffer engines, and are often referred to as "Corderoids".

Speed Direction Smallest known Minimum # of cells Classification
17c/45 orthogonal caterpillar 11,880,063 Crawler-based
31c/240 orthogonal silverfish 210,108 Crawler-based
(23,5)c/79 slope 23/5 waterbear 197,896 Crawler-based
(34,7)c/156 slope 34/7 Unnamed (34,7)c/156 spaceship 25,013,268 Crawler-based
(6,3)c/1024 knightwise HBK caterpillar 329071 Crawler-based
c/2 orthogonal pufferfish spaceship 235 Stabilized puffer engine
c/12 diagonal 2-engine Cordership 100 Stabilized puffer engine

Traveling signal loops

A traveling signal loop is a subcategory somewhat similar to an engineered spaceship, but with key differences. The usual reason for constructing a traveling signal loop is to extract an extra output glider at some point in each cycle, producing an engineless rake. Suppressing a rake's output glider will trivially produce a high-period spaceship.

One main difference between engineered spaceships and traveling signal loops is that the "specific active reactions that travel at one particular speed" are spaceships themselves, and don't need any additional support. The signals traveling in the signal loops can generally be removed without having any effect on the fleet of spaceships supporting the loop.

Speed Direction Examples Classification
2c/7 orthogonal weekender distaff High-period signal loop
c/3 orthogonal c/3 orthogonal rake High-period signal loop
c/4 orthogonal p388 c/4 forward rake, David Bell's adjustable-period backrake High-period signal loop
c/5 orthogonal c/5 orthogonal rake High-period signal loop
2c/5 orthogonal 2c/5 orthogonal rake High-period signal loop
c/4 diagonal c/4 diagonal rake High-period signal loop
c/5 diagonal c/5 diagonal rake High-period signal loop
c/12 diagonal c/12 diagonal rake High-period signal loop

Adjustable spaceships

Adjustable spaceships (formerly known as engineerable spaceships) are the third extant class of spaceships. On average smaller than the engineered spaceships in terms of population, but much larger in bounding box, 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. Adjustable spaceships can be based on variable-speed reactions such as the half-bakery and glider reaction or the freezing/reanimation cycle of the Caterloopillar, or by reading instruction tapes as in the Gemini. Families of adjustable spaceships include the Geminoids, Demonoids, Orthogonoids, loopships, 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
16c/217251 orthogonal Orthogonoid 467,746
c/16384 orthogonal Hashlife-friendly Orthogonoid 467,585
c/32768 orthogonal Double-wide Orthogonoid 467,346
1000130c/20003511 orthogonal loopship 267,672
(200,7)c/81976184 slope 200/7 Stable Storage Spaceship 633,388
(5120,1024)c/16849793 slope 5 (ibiswise) Gemini 846,278
(3,1)c/3948264 slope 3 (camelwise) camelship 239,822
(4096,2048)c/17783745 slope 2 (knightwise) Gemini 2 <=872,252
(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
79c/1183842 diagonal single-channel Demonoid 60,672
c/16384 diagonal Scorbie's Demonoid 72,207
c/512 diagonal Hashlife-friendly Demonoid 105,369
1746011c/8916896 diagonal Speed Demonoid 1,021,124

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 in the form of an agar, 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.[8] In the following year, David Bell found the much smaller c/5 spider using lifesrc, a program based on Hickerson's search algorithm.[9]

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

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.[11] 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 August 2011, Matthias Merzenich discovered lobster, the first c/7 diagonal spaceship.

In February 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, 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, the spaghetti monster.

Sir Robin, the first elementary knightship to be found.
Download RLE: click here

In March 2018, Adam P. Goucher and Tomas Rokicki found the first elementary knightship, Sir Robin, which translates itself by (2,1) every six generations.

2020s

Over the course of December 2020 and the first half of 2021, three speeds received versatile new technology, including the first intermediate-period 2c/7 orthogonal ships (based on the doo-dah by John Winston Garth), several smaller 3c/7 orthogonal ships by Dylan Chen allowing higher-period ships to be constructed, and higher-period (2,1)c/6 knightships based on the sprayer by Adam P. Goucher and Dylan Chen, all aided by the new ikpx2 spaceship search program.

In 2023, the first elementary c/8 diagonal spaceship was found: the walrus.

Speed Direction First discovered Discoverer Year of discovery
c/4 diagonal glider Richard Guy 1969
c/2 orthogonal lightweight spaceship John Conway 1970
c/3 orthogonal 84P3H1V0.1 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 (knightwise) 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 Spaghetti monster Tim Coe 2016
(2,1)c/6 slope 2 (knightwise) Sir Robin Adam P. Goucher and Tomas Rokicki 2018
All speeds slower than c/4 diagonal Speed Demonoid Pavel Grankovskiy and Dave Greene 2020

The first known cases for unsimplified speeds are unknown.

In other rules

A map of outer-totalistic rules. Birth conditions iterate in binary over the x axis (the right half has B0), survival in the y axis (the bottom half has S8). Outside of the bottom-left quadrant (where only the all-off agar is considered space), it is symmetrical due to the duality of black/white reversal. Green rules have known explicit examples of spaceships within them, red ones have been proven not to support any. (See file description for more details.)
A map of outer-totalistic rules. Birth conditions iterate in a Gray code over the x axis, survival in the y axis. Green rules have known explicit examples of spaceships within them, red ones have been proven not to support any. (See file description for more details.)

Many Life-like cellular automata afford spaceships, as do their generalizations; this includes both outer-totalistic and isotropic non-totalistic rules, as well as non-isotropic, Generations and Larger than Life rules.

Various segments of the Life-like rulespace cannot contain spaceships, however. For instance, assuming B0 is not active:

  • In any rule with B1, any pattern expands in all directions.
    • In non-totalistic rules, this applies to any rule with B1c.
  • In any rule with S01234a, the trailing edge of a pattern cannot die.
  • It appears that in some rules patterns cannot escape the bounding box or the bounding diamond despite having the B3a or B2e condition. This is likely the case for LongLife and Assimilation[citation needed].
  • In any rule with B23/S0, the trailing edge of a pattern cannot die.
  • In any rule without B1, B2 or B3, no pattern can escape its initial bounding box.
    • In non-totalistic rules, this applies to any rule without at least one of B1ce, B2ac or B3i.
  • In any rule with none of B123, no pattern can escape its initial bounding diamond.
    • In non-totalistic rules, this applies to any rule with none of B1e, B1c, B2a, B2e or B3a.

In rules with S4w and/or S5a, the diagonal speed limit is c/3, not c/4 and the knightwise speed limit is[citation needed] c/5, not c/6 and so on. The orthogonal limit remains c/2 unless B1e, B1c, or B2a is present.

While assuming B0 is active, we can treat them as either strobing rules or black/white reversals of rules. This yields the following rulespaces[12]:

  • Rules containing all of the transitions in at least one of {B0/S7,B08/S56,B05678/S6,B045678} without any of the transitions in at least one of {S01234,B3/S0123,B2/S0123,B23/S0,B1}
  • Rules with B0234567 without S123456

Also:

  • With B0/S6 and without B1 or B2, or with B0/S67 without B2, all patterns expand at (2,1)c/2.
  • With B0123 and without any of S567, patterns can never leave their bounding box.

The slowest known orthogonal elementary non-adjustable spaceship in any Life-like rule is a c/5648 orthogonal spaceship in the rule Gems, followed by a c/2068 orthogonal spaceship in Gems Minor. The slowest known orthogonal spaceship in a range-1 isotropic non-totalistic rule is a c/5953 ship in B2-an3acqry4cnw5-cj6cei78/S1c2n3-nqy4acknqtw5-ijkr6ei78.[13]

Currently known speeds

There is currently an ongoing tabulation at the 5s project cataloging the smallest known spaceships for each speed across different rules.

Alongside these, certain "series" of speeds can be proved to all exist:

  • All orthogonal spaceships with the unsimplified speed c/n are known to exist in range-1 isotropic cellular automata; true-period c/1, c/2 and c/3 spaceships are known, all c/n speeds where n is even and greater than 3 can be constructed using the rule B2c3ae4ai56c/S2-kn3-enq4, and all c/n speeds where n is odd and greater than 4 can be constructed using the rule B2c3aj4nrt5i6c78/S1c23enr4aet5-iq67. It is not currently known if there exists a rule with a family of spaceships that simulate an infinite range of speeds of form 2c/n where n is odd, 3c/n where n is not divisible by 3, and so on, and it is also not known if similar technology can be applied to other directions.
  • All orthogonal spaceships of the form 2c/n, where n is double an odd number greater than 4, are known, and can be constructed using the rule B2ik3aijn4ant5r6i7e/S02a4i

Notes


See also

General

Conway's Life

Other cellular automata

References

  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. Nathaniel Johnston (October 30, 2009). "Spaceship Speed Limits in "B3" Life-Like Cellular Automata". Retrieved on December 12, 2016.
  5. Jason Summers' jslife pattern collection. Retrieved on January 17, 2019.
  6. Bullet51 (November 17, 2022). Re: Suggested LifeWiki edits (discussion thread) at the ConwayLife.com forums
  7. Alexey Nigin (March 7, 2016). "New Spaceship Speed in Conway’s Game of Life". Retrieved on June 11, 2016.
  8. Tim Coe. "c/5 Orthogonal spaceship". Paul's Page of Conway's Life Miscellany. Retrieved on April 18, 2009.
  9. David Bell. "New c/5 spaceship". Paul's Page of Conway's Life Miscellany. Retrieved on April 18, 2009.
  10. David Eppstein (April 26, 2000). "Searching for Spaceships (PDF)". Retrieved on December 4, 2023.
  11. Oblique Life spaceship created at Game of Life News. Posted by Adam P. Goucher on May 19, 2010.
  12. LaundryPizza03 (April 10, 2020). Re: Spaceships in Life-like cellular automata (discussion thread) at the ConwayLife.com forums
  13. wildmyron (July 24, 2019). Re: Smallest Spaceships Supporting Specific Speeds (5s) Project (discussion thread) at the ConwayLife.com forums

Further reading

  • Carter Bays, Gliders in Cellular Automata, in: Robert A. Meyers (ed). Encyclopedia of Complexity and Systems Science, Springer 2009, pp. 4240–4249.

External links