# Difference between revisions of "Spaceship"

AwesoMan3000 (talk | contribs) |
|||

(93 intermediate revisions by 14 users not shown) | |||

Line 4: | Line 4: | ||

__TOC__ | __TOC__ | ||

− | ==Spaceship | + | ==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]]. | 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 | + | Until the construction of [[Gemini]] in May {{year|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 spaceship]]s 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> | 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. For Life, no spaceship can move at speed (m,n)c/x where (m+n)/x > 0.5; for other [[Life-like cellular automaton|outer-totalistic]] and [[Non-totalistic Life-like cellular automaton|non-totalistic]] rules, the limit is at most 1. Certain range-1 [[non-isotropic Life-like cellular automaton|non-isotropic]] rules can harbour [[photon|c/1]] diagonal spaceships, giving a limit of 2. | + | The maximum speed for Life is [[c/2 orthogonal]] and [[c/4 diagonal]]<ref>{{cite web|url=http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/|title=Spaceship Speed Limits in "B3" Life-Like Cellular Automata|author=Nathaniel Johnston|date=October 30, 2009|accessdate=December 12, 2016}}</ref> (and continually, c/6 for [[knightship|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. For Life, no spaceship can move at speed (''m'',''n'')c/''x'' where (''m''+''n'')/''x'' > 0.5; for other [[Life-like cellular automaton|outer-totalistic]] and [[Non-totalistic Life-like cellular automaton|non-totalistic]] rules, the limit is at most 1. Certain range-1 [[non-isotropic Life-like cellular automaton|non-isotropic]] rules can harbour [[photon|c/1]] diagonal spaceships, giving a limit of 2. |

==Spaceship types== | ==Spaceship types== | ||

− | {{main| | + | {{main|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: | 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=== | ||

− | [[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 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 | + | ''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 that do generally require a lot of gliders in awkward positions. |

+ | |||

+ | [[Adam P. Goucher]] found the first elementary [[knightship]], [[Sir Robin]], on March 7, {{year|2018}}, based on a partial result by [[Tomas Rokicki]]. | ||

{| class="wikitable" | {| class="wikitable" | ||

Line 31: | Line 33: | ||

! [[c/2 orthogonal|c/2]] | ! [[c/2 orthogonal|c/2]] | ||

| orthogonal | | orthogonal | ||

− | | [[ | + | | [[Lightweight spaceship]] |

− | | | + | | {{cells|9}} |

|- | |- | ||

! [[c/3 orthogonal|c/3]] | ! [[c/3 orthogonal|c/3]] | ||

| orthogonal | | orthogonal | ||

− | | [[25P3H1V0.2]] | + | | [[25P3H1V0.1]], [[25P3H1V0.2]] |

− | | | + | | {{cells|25}} |

|- | |- | ||

! [[c/4 orthogonal|c/4]] | ! [[c/4 orthogonal|c/4]] | ||

| orthogonal | | orthogonal | ||

| [[37P4H1V0]] | | [[37P4H1V0]] | ||

− | | | + | | {{cells|37}} |

|- | |- | ||

! [[c/5 orthogonal|c/5]] | ! [[c/5 orthogonal|c/5]] | ||

| orthogonal | | orthogonal | ||

| [[spider]] | | [[spider]] | ||

− | | [[ | + | | {{cells|58}} |

+ | |- | ||

+ | ! [[2c/5 orthogonal|2c/5]] | ||

+ | | orthogonal | ||

+ | | [[30P5H2V0]] | ||

+ | | {{cells|30}} | ||

|- | |- | ||

! [[c/6 orthogonal|c/6]] | ! [[c/6 orthogonal|c/6]] | ||

| orthogonal | | orthogonal | ||

| [[56P6H1V0]] | | [[56P6H1V0]] | ||

− | | | + | | {{cells|56}} |

|- | |- | ||

! [[c/7 orthogonal|c/7]] | ! [[c/7 orthogonal|c/7]] | ||

| orthogonal | | orthogonal | ||

| [[loafer]] | | [[loafer]] | ||

− | | | + | | {{cells|20}} |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

|- | |- | ||

! [[2c/7 orthogonal|2c/7]] | ! [[2c/7 orthogonal|2c/7]] | ||

| orthogonal | | orthogonal | ||

| [[weekender]] | | [[weekender]] | ||

− | | | + | | {{cells|36}} |

|- | |- | ||

! [[3c/7 orthogonal|3c/7]] | ! [[3c/7 orthogonal|3c/7]] | ||

| orthogonal | | orthogonal | ||

| [[spaghetti monster]] | | [[spaghetti monster]] | ||

− | | [[ | + | | {{cells|702}} |

+ | |- | ||

+ | ! [[c/10 orthogonal|c/10]] | ||

+ | | orthogonal | ||

+ | | [[copperhead]] | ||

+ | | {{cells|28}} | ||

|- | |- | ||

! colspan="5" | | ! colspan="5" | | ||

Line 84: | Line 86: | ||

| diagonal | | diagonal | ||

| [[glider]] | | [[glider]] | ||

− | | | + | | {{cells|5}} |

|- | |- | ||

! [[c/5 diagonal|c/5]] | ! [[c/5 diagonal|c/5]] | ||

| diagonal | | diagonal | ||

| [[58P5H1V1]] | | [[58P5H1V1]] | ||

− | | | + | | {{cells|58}} |

|- | |- | ||

! [[c/6 diagonal|c/6]] | ! [[c/6 diagonal|c/6]] | ||

| diagonal | | diagonal | ||

| [[77P6H1V1]] | | [[77P6H1V1]] | ||

− | | | + | | {{cells|77}} |

|- | |- | ||

! [[c/7 diagonal|c/7]] | ! [[c/7 diagonal|c/7]] | ||

| diagonal | | diagonal | ||

| [[Lobster_(spaceship)|lobster]] | | [[Lobster_(spaceship)|lobster]] | ||

− | | [[ | + | | {{cells|83}} |

+ | |- | ||

+ | ! colspan="5" | | ||

+ | |- | ||

+ | ! [[(2,1)c/6]] | ||

+ | | slope 2 ([[knightwise]]) | ||

+ | | [[Sir Robin]] | ||

+ | | {{cells|282}} | ||

|- | |- | ||

|} | |} | ||

− | + | The following is an incomplete list of some higher-period ships which travel at the same velocities:<ref>{{CiteSummersPattern|name=jslife|accessdate=January 17, 2019}}</ref> | |

− | |||

− | |||

{| class="wikitable" | {| class="wikitable" | ||

|- | |- | ||

Line 115: | Line 122: | ||

! [[c/2 orthogonal|c/2]] | ! [[c/2 orthogonal|c/2]] | ||

| orthogonal | | orthogonal | ||

− | | [[ | + | | [[64P2H1V0]] |

− | | [[: | + | | {{cells|64}} |

+ | |- | ||

+ | ! [[c/2 orthogonal|2c/4]] | ||

+ | | orthogonal | ||

+ | | [[lightweight spaceship]] | ||

+ | | {{cells|9}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|3c/6]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq6_0go4u1992s0k6cog0goc6k0s2991u4ogz54x1x10ss0v2i2v0ss01x1x45|patternname=86P6H3V0|style=raw}} | ||

+ | | {{cells|86}} | ||

+ | |- | ||

+ | ! [[c/3 orthogonal|2c/6]] | ||

+ | | orthogonal | ||

+ | | [[72P6H2V0]] | ||

+ | | {{cells|72}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|4c/8]] | ||

+ | | orthogonal | ||

+ | | [[31P8H4V0]] | ||

+ | | {{cells|31}} | ||

+ | |- | ||

+ | ! [[c/4 orthogonal|2c/8]] | ||

+ | | orthogonal | ||

+ | | [[74P8H2V0]] | ||

+ | | {{cells|74}} | ||

+ | |- | ||

+ | ! [[c/3 orthogonal|3c/9]] | ||

+ | | orthogonal | ||

+ | | [[55P9H3V0]] | ||

+ | | {{cells|55}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|5c/10]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq10_wg0cc4625ggowgo8cy5gz4et915x137c4clkig0g0s6231fpogzx3l5e3y310665d0ew8owh6qaa33zx2d0ly9g0gwgo50d0vggaz0gom5536y0g0gc8bb5d0ry0gosb2245cz13d4klx4efp11dpigx132647czy0111325y41|patternname=214P10H5V0|style=raw}} | ||

+ | | {{cells|214}} | ||

+ | |- | ||

+ | ! [[2c/5 orthogonal|4c/10]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq10_ggcmhe404ehmcggz8pjmy3mjp8zy0p81s1ohzx8nnw745|patternname=66P10H4V0|style=raw}} | ||

+ | | {{cells|66}} | ||

+ | |- | ||

+ | ! [[c/5 orthogonal|2c/10]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq10_ydoo0e0913zy8sis8016zy6gni2ooa162zxo0oo066f13zxpqe6zcslopbzw19pzx7c|patternname=81P10H2V0|style=raw}} | ||

+ | | {{cells|81}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|6c/12]] | ||

+ | | orthogonal | ||

+ | | [[Schick engine|lightweight Schick engine]] | ||

+ | | {{cells|39}} | ||

+ | |- | ||

+ | ! [[c/3 orthogonal|4c/12]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq12_y6g81t0t18gzy4so4k7ece7k4oszy7l3i4i3lzy52q9fxf9q2z25c2ce057y7750ec2c52|patternname=103P12H4V0|style=raw}} | ||

+ | | {{cells|103}} | ||

+ | |- | ||

+ | ! [[c/4 orthogonal|3c/12]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq12_yidhd0dhdzy16f9t2t9f6y3mr9ooo9rmy3cuiq4qiuczy0oo5310135ooy011ekjl2ljke11y0gga63036aggzxsex434xesy2oj303joy2ot1w868w1tozgsc961mke7ekm169csgxemo0omey0oojc2c8ses8c2cjooz1712e311x113e2171w4sgs0sgsx3f24s633x336s42f3zw301331606133103yd602662c0c266206|patternname=319P12H3V0|style=raw}} | ||

+ | | {{cells|319}} | ||

+ | |- | ||

+ | ! [[c/6 orthogonal|2c/12]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq12_yj13922y022931zymo7q99q7ozyggg0nj611tuut116jn0ggzyi1y0gc44cgy01z03m0m3y03m0m3y8223322y93m0m3y03m0m3zw3gn3aaaa3ng3y7o035w530oy83gn3aaaa3ng3zwu97y279uy812222221y9u97y279uz22qggy2ggq220248oe2yb2eo842022qggy2ggq22zxq03q22q30qy526csssssssssssc62y5q03q22q30qzxdidy0didybe2i2eybdidy0didzyk8g40cscsc04g8zyjg0omb86068bmo0gzyj1247y37421zyk4ao9f9o9f9oa4zykg8kg0o5o0gk8gzyk12jg12121gj21zyj11cn4mo0om4nc11zyjgo0g61x16g0ogzyhegcd16b6g0g6b61dcgezyhc4g122e0a0a0e221g4czyh124epni2h0h2inpe421zyjg8mti47074itm8gzyg8u125g11gg0gg11g521u8zyj1h9o8pp0pp8o9h1zyj12t60uu0uu06t21zymora202arozyi80a191vg0gv191a08zyh18d6oy5o6d81zyk1gp4y14pg1zyhgg07g24gxg42g70ggzyh1210121y11210121|patternname=861P12H2V0|style=raw|format=extended}} | ||

+ | | {{cells|861}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|7c/14]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq14_y6ogmm23zy427ekgi0gzy71q2n1zy71mgqzy5g0gr31w3mh0c0gwgxgy3gzwogmm23125dkl0eb8a9ll51x8h11y0311z27ekgi0gy1120612zx1q2n1zx1mgqzgosb2i13z0162qqggzy31|patternname=174P14H7V0|style=raw}} | ||

+ | | {{cells|174}} | ||

+ | |- | ||

+ | ! [[c/3 orthogonal|5c/15]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq15_sa408bb5z0344pa3t123z4ah0vwvv0a0ez0o44jaong8oy06mhgz7a402qqky1c4c111zy8br5gzya1|patternname=112P15H5V0|style=raw}} | ||

+ | | {{cells|112}} | ||

+ | |- | ||

+ | ! [[c/5 orthogonal|3c/15]] | ||

+ | | orthogonal | ||

+ | | [[p15 pre-pulsar spaceship]] | ||

+ | | {{cells|494}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|8c/16]] | ||

+ | | orthogonal | ||

+ | | [[Coe ship]] | ||

+ | | {{cells|28}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|9c/18]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq18_ykggy4g8go0v1s0gzyl364kg4li620hl0v0j220aigz59o0o4gg0th8a0sos0a8ht0gg4o0uh67y06os0v1kg880988zx1344421y71244431wggxg0ggqa1x1fc3t0g8xq2gk0ogo0kg2qx8g0giazyq24c0vge833y41127899431x111x134998721zyd8oy38o0u1coc72zye338fgps87431zyj1|patternname=293P18H9V0|style=raw|format=extended}} | ||

+ | | {{cells|293}} | ||

+ | |- | ||

+ | ! [[c/3 orthogonal|6c/18]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq18_061ugzw1cdcy3iccy1hmsgwa6my2ggz3jroy3gog4n081qq222q38c2agr2amf2of2z0gggx66wvvm9g609ggxg90999gg09pf0gzccd1y41g2e01855kkklc134l0d456fkhf4zw8jr3y3433y1863x566z0687|patternname=242P18H6V0|style=raw}} | ||

+ | | {{cells|242}} | ||

+ | |- | ||

+ | ! [[c/6 orthogonal|3c/18]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq18_yh2mk0kkkg0ookkc40704s080888g88gzyh11x1v0uy71v0ii1011zyhhra0abb2066aac80o08e1504452552zyx58gzogy4oo80r4yh62310cogy5gy188gy1gy2ggy0oy3gog2qq4g06282kogy0g8kai32oxg8gy5g0k0agoc0gy0ggg06a4z16010kc4qaehpoowo84gsxc48112sy7vvv0o88xqoh4mid3223ws98v2w2hmajw62afhq844025ea4g0n4k0je21nilr276xppwvq1qrpp4s0e6f88aox11204230240952zgc0g0564baehj33w32417x642gg87y7vvv07441wn728qicggggwe44vh10h2qliwogks2m4880g8sk820q8a0isg0qiamgoox66wum0mm668e0sos44k6y1g08gg0g8048gz31y43320r4yhoggwc731y421x15421x121y01221x6011y0263gmm821og4ha63101125akigh7w1252111y1120a0k26d12x12220pl8zyx8431yzyu1zyh2mk0kkkg0ookkc40704s080888g88gzyh11x1v0uy71v0ii1011zyhhra0abb2066aac80o08e1504452552zyx1|patternname=861P18H3V0|style=raw|format=extended}} | ||

+ | | {{cells|861}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|10c/20]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq20_27de6zw8smx2ceaz0ggz13673|patternname=32P20H10V0|style=raw}} | ||

+ | | {{cells|32}} | ||

+ | |- | ||

+ | ! [[c/10 orthogonal|2c/20]] | ||

+ | | orthogonal | ||

+ | | [[Fireship|fireship tagalong]] | ||

+ | | {{cells|131}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|11c/22]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq22_1fe2o2s0giay1gyfggxg0ggo8zx11avg180g4gu0749c8899988egs0g0g0g24c0vge833zy3131011y2k50t9895x234e8f0aoc72zy2ggy89l0gmd8zy377hs1u0o95w8a0u1cf1zy75fogk0oi8f211zya1|patternname=213P22H11V0|style=raw|format=extended}} | ||

+ | | {{cells|213}} | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|12c/24]] | ||

+ | | orthogonal | ||

+ | | {{LinkCatagolue|xq24_xo8ox6frcz0gh242hgz6d73037d6|patternname=39P24H12V0|style=raw}} | ||

+ | | {{cells|39}} | ||

+ | |- | ||

+ | ! [[3c/7 orthogonal|12c/28]] | ||

+ | | orthogonal | ||

+ | | [[Spaghetti monster|3c/7 wave stabilization]] | ||

+ | | {{cells|1434}} | ||

+ | |- | ||

+ | ! [[c/5 orthogonal|6c/30]] | ||

+ | | orthogonal | ||

+ | | [[pre-pulsar spaceship]] | ||

+ | | {{cells|128}} | ||

+ | |- | ||

+ | ! colspan="5" | | ||

+ | |- | ||

+ | ! [[c/4 diagonal|2c/8]] | ||

+ | | diagonal | ||

+ | | [[Swan|p8 swan tagalong]] | ||

+ | | {{cells|117}} | ||

+ | |- | ||

+ | ! [[c/4 diagonal|3c/12]] | ||

+ | | diagonal | ||

+ | | {{LinkCatagolue|xq12_ym8u0mwhhh0igxoozyfgg0ggwepg09f011whuby0562zy8o8cc46baqo046jrp6zy8g5ray34pczxc0k822ijr3x247zig831y0114oczx562|patternname=142P12H3V3|style=raw|format=extended}} | ||

+ | | {{cells|142}} | ||

+ | |} | ||

+ | |||

+ | ===Engineered spaceships=== | ||

+ | ''Engineered spaceships'' 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 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 [[Cordership]]s might need a relatively small number of components, down to a minimum of just two for the [[2-engine Cordership]]. Such spaceships have occurred [[natural]]ly in other rules, but not yet in [[Conway's Game of Life|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 "[[crawler]]s", reactions in which a pattern reacts with another pattern, producing both the patterns in different positions as in the [[pi crawler]]. Others, like the [[Cordership]]s and [[pufferfish spaceship]]s, rely on ''stabilised [[puffer]] engines''. | ||

+ | |||

+ | {| class="wikitable" | ||

+ | |- | ||

+ | ! Speed | ||

+ | ! Direction | ||

+ | ! Smallest known | ||

+ | ! Minimum # of [[cell]]s | ||

+ | ! Classification | ||

|- | |- | ||

! [[17c/45 orthogonal|17c/45]] | ! [[17c/45 orthogonal|17c/45]] | ||

| orthogonal | | orthogonal | ||

| [[caterpillar]] | | [[caterpillar]] | ||

− | | | + | | {{cells|11,880,063}} |

+ | | Crawler-based | ||

|- | |- | ||

! [[31c/240 orthogonal|31c/240]] | ! [[31c/240 orthogonal|31c/240]] | ||

| orthogonal | | orthogonal | ||

| [[centipede]] | | [[centipede]] | ||

− | | [[:Category: | + | | {{cells|620,901}} |

+ | | Crawler-based | ||

+ | |- | ||

+ | ! [[:Category:Spaceships with speed (23,5)c/79|(23,5)c/79]] | ||

+ | | slope 23/5 | ||

+ | | [[waterbear]] | ||

+ | | {{cells|197,896}} | ||

+ | | Crawler-based | ||

|- | |- | ||

! colspan="5" | | ! colspan="5" | | ||

+ | |- | ||

+ | ! [[c/2 orthogonal|c/2]] | ||

+ | | orthogonal | ||

+ | | [[pufferfish spaceship]] | ||

+ | | {{cells|235}} | ||

+ | | Stabilized puffer engine | ||

|- | |- | ||

! [[c/12 diagonal|c/12]] | ! [[c/12 diagonal|c/12]] | ||

| diagonal | | diagonal | ||

− | | [[ | + | | [[2-engine Cordership]] |

− | | [[ | + | | {{cells|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. | ||

+ | |||

+ | {| class="wikitable" | ||

+ | |- | ||

+ | ! Speed | ||

+ | ! Direction | ||

+ | ! Examples | ||

+ | ! Classification | ||

+ | |- | ||

+ | ! [[2c/7 orthogonal|2c/7]] | ||

+ | | orthogonal | ||

+ | | [[weekender distaff]] | ||

+ | | High-period signal loop | ||

+ | |- | ||

+ | ! [[c/3 orthogonal|c/3]] | ||

+ | | orthogonal | ||

+ | | [[c/3 orthogonal rake]] | ||

+ | | High-period signal loop | ||

+ | |- | ||

+ | ! [[c/4 orthogonal|c/4]] | ||

+ | | orthogonal | ||

+ | | p388 c/4 forward rake, David Bell's adjustable-period backrake | ||

+ | | High-period signal loop | ||

+ | |- | ||

+ | ! [[c/5 orthogonal|c/5]] | ||

+ | | orthogonal | ||

+ | | [[c/5 orthogonal rake]] | ||

+ | | High-period signal loop | ||

+ | |- | ||

+ | ! [[2c/5 orthogonal|2c/5]] | ||

+ | | orthogonal | ||

+ | | [[2c/5 orthogonal rake]] | ||

+ | | High-period signal loop | ||

+ | |- | ||

+ | ! [[c/4 diagonal|c/4]] | ||

+ | | diagonal | ||

+ | | [[c/4 diagonal rake]] | ||

+ | | High-period signal loop | ||

|- | |- | ||

− | ! | + | ! [[c/5 diagonal|c/5]] |

+ | | diagonal | ||

+ | | [[c/5 diagonal rake]] | ||

+ | | High-period signal loop | ||

|- | |- | ||

− | ! [[ | + | ! [[c/12 diagonal|c/12]] |

− | | | + | | diagonal |

− | | [[ | + | | [[c/12 diagonal rake]] |

− | | | + | | High-period signal loop |

|- | |- | ||

|} | |} | ||

− | === | + | === Adjustable spaceships === |

− | '' | + | ''Adjustable spaceships'' (formerly ''engineerable spaceships'') are the third 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. |

{| class="wikitable" | {| class="wikitable" | ||

Line 158: | Line 383: | ||

| orthogonal | | orthogonal | ||

| [[centipede caterloopillar]] | | [[centipede caterloopillar]] | ||

− | | | + | | {{cells|361,070}} |

|- | |- | ||

! [[c/8 orthogonal|c/8]] | ! [[c/8 orthogonal|c/8]] | ||

| orthogonal | | orthogonal | ||

| [[Caterloopillar|Original caterloopillar]] | | [[Caterloopillar|Original caterloopillar]] | ||

− | | | + | | {{cells|232,815}} |

|- | |- | ||

! [[c/8 orthogonal|All speeds slower than c/4]] | ! [[c/8 orthogonal|All speeds slower than c/4]] | ||

Line 169: | Line 394: | ||

| [[Caterloopillar|other caterloopillars]] | | [[Caterloopillar|other caterloopillars]] | ||

| [[:Category:Patterns with 1000 or more cells|Varies]] | | [[:Category:Patterns with 1000 or more cells|Varies]] | ||

+ | |- | ||

+ | ! 16c/217251 | ||

+ | | orthogonal | ||

+ | | [[Orthogonoid]] | ||

+ | | {{cells|467,746}} | ||

|- | |- | ||

! [[c/16384 orthogonal|c/16384]] | ! [[c/16384 orthogonal|c/16384]] | ||

| orthogonal | | orthogonal | ||

| [[Hashlife-friendly Orthogonoid]] | | [[Hashlife-friendly Orthogonoid]] | ||

− | | | + | | {{cells|467,585}} |

|- | |- | ||

! [[c/32768 orthogonal|c/32768]] | ! [[c/32768 orthogonal|c/32768]] | ||

| orthogonal | | orthogonal | ||

| [[Double-wide Orthogonoid]] | | [[Double-wide Orthogonoid]] | ||

− | | [[ | + | | {{cells|467,346}} |

+ | |- | ||

+ | ! 1000130c/20003511 | ||

+ | | orthogonal | ||

+ | | [[loopship]] | ||

+ | | {{cells|267,672}} | ||

|- | |- | ||

! colspan="5" | | ! colspan="5" | | ||

Line 185: | Line 420: | ||

| slope 5 (ibiswise) | | slope 5 (ibiswise) | ||

| [[Gemini]] | | [[Gemini]] | ||

− | | | + | | {{cells|846,278}} |

|- | |- | ||

− | ! ( | + | ! (3,1)c/3948264 |

| slope 3 (camelwise) | | slope 3 (camelwise) | ||

− | | [http:// | + | | [http://conwaylife.com/forums/viewtopic.php?p=66297#p66297 camelship] |

− | | | + | | {{cells|239,822}} |

|- | |- | ||

! (4096,2048)c/17783745 | ! (4096,2048)c/17783745 | ||

| slope 2 (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] | ||

− | | <= | + | | [[:Category:Patterns with 1000 or more cells|<=872,252]] |

|- | |- | ||

! (6,3)c/245912 | ! (6,3)c/245912 | ||

| slope 2 (knightwise) | | slope 2 (knightwise) | ||

| [[Parallel HBK]] | | [[Parallel HBK]] | ||

− | | | + | | {{cells|132,945}} |

|- | |- | ||

! (6,3)c/2621440 | ! (6,3)c/2621440 | ||

| slope 2 (knightwise) | | slope 2 (knightwise) | ||

| [[Half-baked knightship]] | | [[Half-baked knightship]] | ||

− | | | + | | {{cells|1,049,395}} |

|- | |- | ||

! colspan="5" | | ! colspan="5" | | ||

Line 212: | Line 447: | ||

| diagonal | | diagonal | ||

| [[Demonoid|0hd Demonoid]] | | [[Demonoid|0hd Demonoid]] | ||

− | | | + | | {{cells|27,250}} |

|- | |- | ||

! 65c/818356 | ! 65c/818356 | ||

| diagonal | | diagonal | ||

| [[Demonoid|10hd Demonoid]] | | [[Demonoid|10hd Demonoid]] | ||

− | | [[ | + | | {{cells|47,701}} |

+ | |- | ||

+ | ! 79c/1183842 | ||

+ | | diagonal | ||

+ | | [[Demonoid|single-channel Demonoid]] | ||

+ | | {{cells|60,672}} | ||

+ | |- | ||

+ | ! c/16384 | ||

+ | | diagonal | ||

+ | | [[Demonoid|Scorbie's Demonoid]] | ||

+ | | {{cells|72,207}} | ||

+ | |- | ||

+ | ! c/512 | ||

+ | | diagonal | ||

+ | | [[Demonoid|Hashlife-friendly Demonoid]] | ||

+ | | {{cells|105,369}} | ||

|- | |- | ||

|} | |} | ||

Line 230: | Line 480: | ||

===1970s=== | ===1970s=== | ||

[[Image:mwss.gif|framed|right|A middleweight spaceship]] | [[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 | + | The four smallest spaceships in life, the glider, lightweight spaceship, [[middleweight spaceship]] and [[heavyweight spaceship]], were all found by hand in {{year|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=== | ===1980s=== | ||

− | Significant advances in spaceship technology came in | + | Significant advances in spaceship technology came in {{year|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]]. | 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 | + | The next spaceship speed to be discovered was that of the orthogonal [[c/5 orthogonal|c/5]] [[snail]], found by [[Tim Coe]] in {{year|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 | + | In March of {{year|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=== | ||

[[Image:weekender_small.gif|framed|right|David Eppstein's weekender]] | [[Image:weekender_small.gif|framed|right|David Eppstein's weekender]] | ||

− | Eppstein put his search program to good use in | + | Eppstein put his search program to good use in {{year|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 | + | In {{year|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=== | ===2010s=== | ||

[[File:Loafer.gif|framed|right|Josh Ball's loafer]] | [[File:Loafer.gif|framed|right|Josh Ball's loafer]] | ||

− | In May | + | In May {{year|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. | In Febuary 2013, the first c/7 orthogonal spaceship, [[loafer]], was discovered by Josh Ball. | ||

Line 261: | Line 511: | ||

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 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. |

+ | |||

+ | In June 2016, Tim Coe found a large elementary 3c/7 orthogonal spaceship, the [[spaghetti monster]]. | ||

+ | |||

+ | [[File:Sirrobin tiny.png|framed|right|[[Sir Robin]], the first elementary knightship to be found.<br />{{JavaRLE|sirrobin}}]] | ||

+ | 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. | ||

+ | |||

− | |||

{| class="wikitable" | {| class="wikitable" | ||

|- | |- | ||

Line 276: | Line 531: | ||

| [[glider]] | | [[glider]] | ||

| [[Richard Guy]] | | [[Richard Guy]] | ||

− | | | + | | {{year|1970}} |

|- | |- | ||

! c/2 | ! c/2 | ||

Line 282: | Line 537: | ||

| [[lightweight spaceship]] | | [[lightweight spaceship]] | ||

| [[John Conway]] | | [[John Conway]] | ||

− | | | + | | {{year|1970}} |

|- | |- | ||

! c/3 | ! c/3 | ||

| orthogonal | | orthogonal | ||

− | | [[ | + | | [[84P3H1V0.1]] |

| [[Dean Hickerson]] | | [[Dean Hickerson]] | ||

− | | | + | | {{year|1989}} |

|- | |- | ||

! c/4 | ! c/4 | ||

Line 294: | Line 549: | ||

| [[119P4H1V0]] | | [[119P4H1V0]] | ||

| [[Dean Hickerson]] | | [[Dean Hickerson]] | ||

− | | | + | | {{year|1989}} |

|- | |- | ||

! c/12 | ! c/12 | ||

Line 300: | Line 555: | ||

| [[13-engine Cordership]] | | [[13-engine Cordership]] | ||

| [[Dean Hickerson]] | | [[Dean Hickerson]] | ||

− | | | + | | {{year|1991}} |

|- | |- | ||

! 2c/5 | ! 2c/5 | ||

Line 306: | Line 561: | ||

| [[44P5H2V0]] | | [[44P5H2V0]] | ||

| [[Dean Hickerson]] | | [[Dean Hickerson]] | ||

− | | | + | | {{year|1991}} |

|- | |- | ||

! c/5 | ! c/5 | ||

Line 312: | Line 567: | ||

| [[snail]] | | [[snail]] | ||

| [[Tim Coe]] | | [[Tim Coe]] | ||

− | | | + | | {{year|1996}} |

|- | |- | ||

! 2c/7 | ! 2c/7 | ||

Line 318: | Line 573: | ||

| [[weekender]] | | [[weekender]] | ||

| [[David Eppstein]] | | [[David Eppstein]] | ||

− | | | + | | {{year|2000}} |

|- | |- | ||

! c/6 | ! c/6 | ||

Line 324: | Line 579: | ||

| [[dragon]] | | [[dragon]] | ||

| [[Paul Tooke]] | | [[Paul Tooke]] | ||

− | | | + | | {{year|2000}} |

|- | |- | ||

! c/5 | ! c/5 | ||

Line 330: | Line 585: | ||

| [[295P5H1V1]] | | [[295P5H1V1]] | ||

| [[Jason Summers]] | | [[Jason Summers]] | ||

− | | | + | | {{year|2000}} |

|- | |- | ||

! 17c/45 | ! 17c/45 | ||

Line 336: | Line 591: | ||

| [[caterpillar]] | | [[caterpillar]] | ||

| [[Gabriel Nivasch]], [[Jason Summers]], and [[David Bell]] | | [[Gabriel Nivasch]], [[Jason Summers]], and [[David Bell]] | ||

− | | | + | | {{year|2004}} |

|- | |- | ||

! c/6 | ! c/6 | ||

Line 342: | Line 597: | ||

| [[seal]] | | [[seal]] | ||

| [[Nicolay Beluchenko]] | | [[Nicolay Beluchenko]] | ||

− | | | + | | {{year|2005}} |

|- | |- | ||

! (5120,1024)c/16849793 | ! (5120,1024)c/16849793 | ||

Line 348: | Line 603: | ||

| [[Gemini]] | | [[Gemini]] | ||

| [[Andrew J. Wade]] | | [[Andrew J. Wade]] | ||

− | | | + | | {{year|2010}} |

|- | |- | ||

! (4096,2048)c/17783745 | ! (4096,2048)c/17783745 | ||

Line 354: | Line 609: | ||

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

− | | | + | | {{year|2010}} |

|- | |- | ||

! (3072,1024)c/36000001 | ! (3072,1024)c/36000001 | ||

Line 360: | Line 615: | ||

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

− | | | + | | {{year|2010}} |

|- | |- | ||

! c/7 | ! c/7 | ||

Line 366: | Line 621: | ||

| [[Lobster]] | | [[Lobster]] | ||

| [[Matthias Merzenich]] | | [[Matthias Merzenich]] | ||

− | | | + | | {{year|2011}} |

|- | |- | ||

! c/7 | ! c/7 | ||

Line 372: | Line 627: | ||

| [[loafer]] | | [[loafer]] | ||

| [[Josh Ball]] | | [[Josh Ball]] | ||

− | | | + | | {{year|2013}} |

|- | |- | ||

! (6,3)c/2621440 | ! (6,3)c/2621440 | ||

− | | slope 2 ( | + | | slope 2 (knightwise) |

| [[Half-baked knightship]] | | [[Half-baked knightship]] | ||

| [[Adam P. Goucher]] | | [[Adam P. Goucher]] | ||

− | | | + | | {{year|2014}} |

|- | |- | ||

! (6,3)c/245912 | ! (6,3)c/245912 | ||

Line 384: | Line 639: | ||

| [[Parallel HBK]] | | [[Parallel HBK]] | ||

| [[Chris Cain]] | | [[Chris Cain]] | ||

− | | | + | | {{year|2014}} |

|- | |- | ||

! 31c/240 | ! 31c/240 | ||

Line 390: | Line 645: | ||

| [[shield bug]] | | [[shield bug]] | ||

| [[Dave Greene]] | | [[Dave Greene]] | ||

− | | | + | | {{year|2014}} |

|- | |- | ||

! (23,5)c/79 | ! (23,5)c/79 | ||

Line 396: | Line 651: | ||

| [[waterbear]] | | [[waterbear]] | ||

| [[Brett Berger]] | | [[Brett Berger]] | ||

− | | | + | | {{year|2014}} |

|- | |- | ||

! 130c/(1636712+16N) | ! 130c/(1636712+16N) | ||

Line 402: | Line 657: | ||

| [[Demonoid|10hd Demonoid]] | | [[Demonoid|10hd Demonoid]] | ||

| [[Chris Cain]] and [[Dave Greene]] | | [[Chris Cain]] and [[Dave Greene]] | ||

− | | | + | | {{year|2015}} |

|- | |- | ||

! 65c/(438852+16N) | ! 65c/(438852+16N) | ||

Line 408: | Line 663: | ||

| [[Demonoid|0hd Demonoid]] | | [[Demonoid|0hd Demonoid]] | ||

| [[Chris Cain]] | | [[Chris Cain]] | ||

− | | | + | | {{year|2015}} |

|- | |- | ||

! c/10 | ! c/10 | ||

Line 414: | Line 669: | ||

| [[Copperhead]] | | [[Copperhead]] | ||

| [[zdr]] | | [[zdr]] | ||

− | | | + | | {{year|2016}} |

|- | |- | ||

! All speeds slower than c/4 | ! All speeds slower than c/4 | ||

Line 420: | Line 675: | ||

| [[caterloopillar]] | | [[caterloopillar]] | ||

| [[Michael Simkin]] | | [[Michael Simkin]] | ||

− | | | + | | {{year|2016}} |

|- | |- | ||

! 3c/7 | ! 3c/7 | ||

| orthogonal | | orthogonal | ||

− | | [[ | + | | [[Spaghetti monster]] |

| [[Tim Coe]] | | [[Tim Coe]] | ||

− | | [[ | + | | {{year|2016}} |

+ | |- | ||

+ | ! (2,1)c/6 | ||

+ | | slope 2 (knightwise) | ||

+ | | [[Sir Robin]] | ||

+ | | [[Adam P. Goucher]] and [[Tomas Rokicki]] | ||

+ | | {{year|2018}} | ||

|} | |} | ||

==In other rules== | ==In other rules== | ||

− | Many [[Life-like cellular automata]] afford spaceships, as do their generalizations; this includes both [[outer-totalistic]] and [[non-totalistic]] rules, as well as [[non-isotropic]], [[Generations]] | + | 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: | + | Various segments of the Life-like [[rulespace]] cannot contain spaceships, however. For instance, assuming [[Birth on zero neighbours|B0]] is not active: |

* In any rule with B1, any pattern expands in all directions. | * In any rule with B1, any pattern expands in all directions. | ||

** In non-totalistic rules, this applies to any rule with B1c. | ** In non-totalistic rules, this applies to any rule with B1c. | ||

− | * In any rule with | + | * 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 of the bounding diamond. This is likely the case for [[OCA:LongLife|LongLife]]. | ||

* In any rule with B23/S0, the trailing edge of a pattern cannot die. | * In any rule with B23/S0, the trailing edge of a pattern cannot die. | ||

− | * In any rule without B2 or B3, no pattern can escape its initial bounding box. | + | * 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 B2ac or B3i. | + | ** In non-totalistic rules, this applies to any rule without at least one of B1ce, B2ac or B3i. |

− | * In any rule | + | * In any rule with none of B123, no pattern can escape its initial bounding diamond. |

− | ** In non-totalistic rules, this applies to any rule | + | ** In non-totalistic rules, this applies to any rule with none of B1e, B1c, B2a, B2e or B3a. |

+ | |||

+ | The slowest known orthogonal elementary non-adjustable spaceship in any range-1 Life-like rule is a [[c/5648 orthogonal]] spaceship in the rule [[Gems]], followed by a [[c/2068 orthogonal]] spaceship in [[Gems Minor]]. | ||

+ | |||

+ | === Currently known speeds === | ||

+ | There is currently an ongoing tabulation at [[LifeWiki:Smallest Spaceships Supporting Specific Speeds|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 true-period orthogonal spaceships of the form c/n are known to exist in range-1 Life-like cellular automata; true-period [[Photon|c/1]], [[64P2H1V0|c/2]] and [[25P3H1V0.2|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. | ||

+ | |||

+ | *All period-1 orthogonal spaceships of the form nc/1 where n is an integer greater than 0 are known to exist, using a trick detailed [http://www.conwaylife.com/forums/viewtopic.php?p=46358#p46358 here]. | ||

+ | |||

+ | *All period-2 orthogonal spaceships of the form nc/2 where n is an integer greater than 0 and n+1 is prime are also known to exist.<ref name="post45641" /><ref name="post47857" /> | ||

==See also== | ==See also== | ||

+ | *[[List of common spaceships]] | ||

*[[:Category:Spaceships|List of spaceships]] | *[[:Category:Spaceships|List of spaceships]] | ||

+ | *[[List of spaceships|List of spaceship speeds]] | ||

*[[Spaceship flotilla]] | *[[Spaceship flotilla]] | ||

*[[LifeWiki:Game_of_Life_Status_page#Spaceship_periods|Spaceship periods status table]] | *[[LifeWiki:Game_of_Life_Status_page#Spaceship_periods|Spaceship periods status table]] | ||

Line 457: | Line 732: | ||

*[[HighLife#Spaceships|Spaceships of HighLife]] | *[[HighLife#Spaceships|Spaceships of HighLife]] | ||

− | == | + | ==References== |

− | <references/> | + | <references> |

+ | <ref name="post45641">{{LinkForumThread | ||

+ | |format = ref | ||

+ | |title = Re: Larger than Life | ||

+ | |p = 45641 | ||

+ | |author = gameoflifeboy | ||

+ | |date = June 30, 2017 | ||

+ | }}</ref> | ||

+ | <ref name="post47857">{{LinkForumThread | ||

+ | |format = ref | ||

+ | |title = Re: Larger than Life | ||

+ | |p = 47857 | ||

+ | |author = AforAmpere | ||

+ | |date = August 3, 2017 | ||

+ | }}</ref> | ||

+ | </references> | ||

==External links== | ==External links== | ||

+ | {{LinkWikipedia|Spaceship_(cellular_automaton)}} | ||

{{LinkLexicon|filename=lex_s.htm#spaceship|patternname=Spaceship}} | {{LinkLexicon|filename=lex_s.htm#spaceship|patternname=Spaceship}} | ||

{{LinkWeisstein|filename=Spaceship.html|patternname=Spaceship}} | {{LinkWeisstein|filename=Spaceship.html|patternname=Spaceship}} |

## Latest revision as of 13:04, 14 February 2020

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.

## Contents

## 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. 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/1 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 these spaceships is usually difficult, as only a few elementary spaceships have known glider syntheses; those that do generally require a lot of gliders in awkward positions.

Adam P. Goucher found the first elementary knightship, Sir Robin, on March 7, 2018, based on a partial result by Tomas Rokicki.

Speed | Direction | Smallest known | Minimum # of cells | |
---|---|---|---|---|

c/2 | orthogonal | Lightweight spaceship | 9 | |

c/3 | orthogonal | 25P3H1V0.1, 25P3H1V0.2 | 25 | |

c/4 | orthogonal | 37P4H1V0 | 37 | |

c/5 | orthogonal | spider | 58 | |

2c/5 | orthogonal | 30P5H2V0 | 30 | |

c/6 | orthogonal | 56P6H1V0 | 56 | |

c/7 | orthogonal | loafer | 20 | |

2c/7 | orthogonal | weekender | 36 | |

3c/7 | orthogonal | spaghetti monster | 702 | |

c/10 | orthogonal | copperhead | 28 | |

c/4 | diagonal | glider | 5 | |

c/5 | diagonal | 58P5H1V1 | 58 | |

c/6 | diagonal | 77P6H1V1 | 77 | |

c/7 | diagonal | lobster | 83 | |

(2,1)c/6 | slope 2 (knightwise) | Sir Robin | 282 |

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

### Engineered spaceships

*Engineered spaceships* are defined as spaceships consisting of small interacting components.^{[6]} 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*.

Speed | Direction | Smallest known | Minimum # of cells | Classification |
---|---|---|---|---|

17c/45 | orthogonal | caterpillar | 11,880,063 | Crawler-based |

31c/240 | orthogonal | centipede | 620,901 | Crawler-based |

(23,5)c/79 | slope 23/5 | waterbear | 197,896 | 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 *engineerable spaceships*) are the third 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 | |

(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 |

### Other classifications

*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 (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

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

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.^{[9]}

### 2000s

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

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

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

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.

## In other rules

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 of the bounding diamond. This is likely the case for LongLife.
- 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.

The slowest known orthogonal elementary non-adjustable spaceship in any range-1 Life-like rule is a c/5648 orthogonal spaceship in the rule Gems, followed by a c/2068 orthogonal spaceship in Gems Minor.

### 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 true-period orthogonal spaceships of the form c/n are known to exist in range-1 Life-like 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.

- All period-1 orthogonal spaceships of the form nc/1 where n is an integer greater than 0 are known to exist, using a trick detailed here.

- All period-2 orthogonal spaceships of the form nc/2 where n is an integer greater than 0 and n+1 is prime are also known to exist.
^{[11]}^{[12]}

## See also

- List of common spaceships
- List of spaceships
- List of spaceship speeds
- Spaceship flotilla
- Spaceship periods status table
- Spaceship terminology
- Types of spaceships
- Velocities of spaceships and related objects status table
- Spaceships of HighLife

## References

- ↑ "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.
- ↑ Nathaniel Johnston (October 30, 2009). "Spaceship Speed Limits in "B3" Life-Like Cellular Automata". Retrieved on December 12, 2016.
- ↑ Jason Summers' jslife pattern collection. Retrieved on January 17, 2019.
- ↑ Alexey Nigin (7 Mar 2016). "New Spaceship Speed in Conway’s Game of Life". Retrieved on 11 Jun 2016.
- ↑ 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.
- ↑ Adam P. Goucher (May 19, 2010). "Oblique Life spaceship created".
*Game of Life News*. Retrieved on May 21, 2010. - ↑ gameoflifeboy (June 30, 2017). Re: Larger than Life (discussion thread) at the ConwayLife.com forums
- ↑ AforAmpere (August 3, 2017). Re: Larger than Life (discussion thread) at the ConwayLife.com forums

## External links

- Spaceship at Wikipedia

- Spaceship at the Life Lexicon