Difference between revisions of "Glider synthesis"
(→Spaceship syntheses: updated) |
(→Spaceship syntheses: updated) |
||
(48 intermediate revisions by 6 users not shown) | |||
Line 29: | Line 29: | ||
In the 1990s, glider syntheses for all [[still life]]s and known [[oscillator]]s with at most 14 [[cell]]s were found by [[David Buckingham]]. Almost all of these were successfully reduced to a synthesis cost of less than 1 glider per ON cell, or "1 glider per bit".<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=&p=21500#p20597 |title=Re: 4 glider syntheses |work=ConwayLife.com forums |author=Mark D. Niemiec|date=June 20, 2015|accessdate=February 21, 2018}}</ref> | In the 1990s, glider syntheses for all [[still life]]s and known [[oscillator]]s with at most 14 [[cell]]s were found by [[David Buckingham]]. Almost all of these were successfully reduced to a synthesis cost of less than 1 glider per ON cell, or "1 glider per bit".<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=&p=21500#p20597 |title=Re: 4 glider syntheses |work=ConwayLife.com forums |author=Mark D. Niemiec|date=June 20, 2015|accessdate=February 21, 2018}}</ref> | ||
A collaborative effort ending in May 2014 completed glider syntheses of all still lifes with 17 or fewer cells.<ref>{{cite web|url=http://pentadecathlon.com/lifeNews/2014/05/constructions_known_for_all_st.html |title=Constructions Known for All Still Lifes up to 17 Bits |work=Game of Life News |author=Dave Greene |date=May 23, 2014|accessdate=September 17, 2014}}</ref><ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=1276 |title=17-bit SL Syntheses (100% Complete!) |work=ConwayLife.com forums |author=Martin Grant|date=January 6, 2014 |accessdate=September 17, 2014}}</ref><ref name="post11972" /> A second, longer effort claimed to have completed all the 18-bit still lifes in November 2014,<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=1467#p13607 |title=18-bit SL Syntheses (100% Complete!)|work=ConwayLife.com forums |author=Martin Grant|date=October 2, 2014|accessdate=February 21, 2018}}</ref><ref name="post14272" /> but it was later found that some of these syntheses were erroneous.{{citation needed}} The project was finally completed for real in October 2019.<ref name="post83979" /> The syntheses for 19-bit still lifes were completed in February 2020.<ref name=" | A collaborative effort ending in May 2014 completed glider syntheses of all still lifes with 17 or fewer cells.<ref>{{cite web|url=http://pentadecathlon.com/lifeNews/2014/05/constructions_known_for_all_st.html |title=Constructions Known for All Still Lifes up to 17 Bits |work=Game of Life News |author=Dave Greene |date=May 23, 2014|accessdate=September 17, 2014}}</ref><ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=1276 |title=17-bit SL Syntheses (100% Complete!) |work=ConwayLife.com forums |author=Martin Grant|date=January 6, 2014 |accessdate=September 17, 2014}}</ref><ref name="post11972" /> A second, longer effort claimed to have completed all the 18-bit still lifes in November 2014,<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=1467#p13607 |title=18-bit SL Syntheses (100% Complete!)|work=ConwayLife.com forums |author=Martin Grant|date=October 2, 2014|accessdate=February 21, 2018}}</ref><ref name="post14272" /> but it was later found that some of these syntheses were erroneous.{{citation needed}} The project was finally completed for real in October 2019.<ref name="post83979" /> The syntheses for 19-bit still lifes were completed in February 2020,<ref name="post89061" /> and 20-bit still lifes in March 2021.<ref name="post125259" /> Later optimization projects reduced the maximum cost of construction for 15-bit,<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=2441|title=15 in 15: Efficient 15-bit Synthesis Project (DONE!)|work=ConwayLife.com forums |author=BlinkerSpawn|date=October 27, 2016|accessdate=February 21, 2018}}</ref><ref name="post37438" /> 16-bit,<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=2642 |title=16 in 16: Efficient 16-bit Synthesis Project |work=ConwayLife.com forums |author=Bob Shemyakin|date=December 20, 2016|accessdate=February 21, 2018}}</ref><ref name="post43734" /> and 17-bit<ref name="post82560" /> still lifes to less than one glider per bit, in November 2016, May 2017, and September 2019 respectively. | ||
The following table displays the | In September 2020, the 17-glider reverse caber-tosser proved that all synthesizable still lifes could theoretically be constructed with no more than one glider per bit.<ref name="post104484" /> | ||
The following table displays statistics about the costs (excluding RCT constructions) for strict and pseudo still lifes with up to 20 cells as of January 31, 2021.<ref>{{CiteCatagolue|page=syntheses|title=Syntheses|accessdate=January 31, 2021}}</ref> | |||
{| class="wikitable" style="text-align:center" | {| class="wikitable" style="text-align:center" | ||
! Live cells !! | ! rowspan=2 | Live cells !! colspan=4 | Strict still lifes !! colspan=3 | Pseudo still lifes | ||
|- | |- | ||
! Count<br>({{OEIS|A019473}}) !! Min. cost !! Avg. cost !! Max. cost !! Count<br>({{OEIS|A056613}}) !! Min. cost !! Max. cost | |||
|- | |- | ||
| | | 4 || {{A019473|4}} || 2 || 2.500 || 3 || {{A056613|4}} || – || – | ||
|- | |- | ||
| {{ | | 5 || {{A019473|5}} || 2 || 2.000 || 2 || {{A056613|5}} || – || – | ||
|- | |- | ||
| | | 6 || {{A019473|6}} || 2 || 3.200 || 4 || {{A056613|6}} || – || – | ||
|- | |- | ||
| | | 7 || {{A019473|7}} || 2 || 2.750 || 4 || {{A056613|7}} || – || – | ||
|- | |- | ||
| {{ | | 8 || {{A019473|8}} || 2 || 3.556 || 4 || {{A056613|8}} || 2 || 2 | ||
|- | |- | ||
| | | 9 || {{A019473|9}} || 3 || 4.000 || 5 || {{A056613|9}} || 3 || 3 | ||
|- | |- | ||
| | | 10 || {{A019473|10}} || 4 || 4.360 || 5 || {{A056613|10}} || 3 || 5 | ||
|- | |- | ||
| {{ | | 11 || {{A019473|11}} || 4 || 4.913 || 7 || {{A056613|11}} || 3 || 7 | ||
|- | |- | ||
| {{ | | 12 || {{A019473|12}} || 4 || 5.843 || 8 || {{A056613|12}} || 3 || 9 | ||
|- | |- | ||
| {{ | | 13 || {{A019473|13}} || 4 || 6.338 || 8 || {{A056613|13}} || 4 || 10 | ||
|- | |- | ||
| {{ | | 14 || {{A019473|14}} || 3 || 7.249 || 10 || {{A056613|14}} || 3 || 11 | ||
|- | |- | ||
| {{ | | 15 || {{A019473|15}} || 4 || 8.343 || 12 || {{A056613|15}} || 4 || 12 | ||
|- | |- | ||
| {{ | | 16 || {{A019473|16}} || 3 || 9.383 || 14 || {{A056613|16}} || 4 || style="background-color:#ffff80;" | 25{{refn|group=n|name=RCT}}{{refn|group=n|All but 5 16-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.}} | ||
|- | |- | ||
| {{ | | 17 || {{A019473|17}} || 4 || 10.601 || 16 || {{A056613|17}} || 4 || style="background-color:#ffff80;" | 19{{refn|group=n|name=RCT}}{{refn|group=n|All but 7 17-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.}} | ||
|- | |- | ||
| {{ | | 18 || {{A019473|18}} || 4 || 12.071 || style="background-color:#ffff80;" | 30{{refn|group=n|name=RCT|{{Reverse caber tosser/Lower bound}} gliders using the [[reverse caber-tosser]]}}{{refn|group=n|All but 727 18-bit strict still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.}} || {{A056613|18}}|| 4 || style="background-color:#ff8080;" | 2 unsynthesized{{refn|group=n|All but 49 18-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.}} | ||
|- | |- | ||
| {{ | | 19 || {{A019473|19}} || 4 || 13.580 || style="background-color:#ffff80;" | 72{{refn|group=n|name=RCT}}{{refn|group=n|All but 3,405 19-bit strict still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.}} || {{A056613|19}} || 4 || style="background-color:#ff8080;" | 4 unsynthesized{{refn|group=n|All but 105 19-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.}} | ||
|- | |||
| 20 || {{A019473|20}} || 4 || colspan="2" style="background-color:#ff8080;" | 321 unsynthesized{{refn|group=n|All but 14,330 20-bit strict still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.}} || {{A056613|20}} || colspan="2" style="background-color:#c0c0c0;" | {{refn|group=n|20-bit pseudo still lifes are currently not fully tabulated on Catagolue due to a combination of size constraints and the ongoing status of the 20-bit strict still life synthesis project.<ref name="message799632200403648523" />}} | |||
|} | |} | ||
<references group=n /> | |||
==Spaceship syntheses== | ==Spaceship syntheses== | ||
Line 84: | Line 89: | ||
! Date !! Discoverer !! Fewest gliders | ! Date !! Discoverer !! Fewest gliders | ||
|- | |- | ||
| [[60P5H2V0]] || data-sort-value="o 0.4" | [[2c/5 orthogonal]] || 2003-03-17 || [[Noam Elkies]] || | | [[60P5H2V0]] || data-sort-value="o 0.4" | [[2c/5 orthogonal]] || 2003-03-17 || [[Noam Elkies]] || 37 | ||
|- | |- | ||
| [[loafer]] || data-sort-value="o 0.142857" | [[c/7 orthogonal]] || 2013-02-17 || [[Adam P. Goucher]] || 8 | | [[loafer]] || data-sort-value="o 0.142857" | [[c/7 orthogonal]] || 2013-02-17 || [[Adam P. Goucher]] || 8 | ||
|- | |- | ||
| [[dart]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2014-12-02 || [[Martin Grant]] || 25 | | [[dart]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2014-12-02 || [[Ivan Fomichev]], [[Mark Niemiec]], [[Martin Grant]], [[Michael Simkin]] || 25 | ||
|- | |- | ||
| [[crab]] || data-sort-value="d 0.25" | [[c/4 diagonal]] || 2014-12-26 || [[Martin Grant]] || | | [[crab]] || data-sort-value="d 0.25" | [[c/4 diagonal]] || 2014-12-26 || [[Brett Berger]], [[Martin Grant]], [[Tanner Jacobi]] || 14 | ||
|- | |- | ||
| [[Parallel HBK]] || data-sort-value="oblique" | [[(6,3)c/245912]] || 2014-12-31 || [[Michael Simkin]] || 38,380 | | [[Parallel HBK]] || data-sort-value="oblique" | [[(6,3)c/245912]] || 2014-12-31 || [[Michael Simkin]] || 38,380 | ||
|- | |- | ||
| [[30P5H2V0]] || data-sort-value="o 0.4" | [[2c/5 orthogonal]] || 2015-01-01 || [[Martin Grant]] || | | [[30P5H2V0]] || data-sort-value="o 0.4" | [[2c/5 orthogonal]] || 2015-01-01 || [[Martin Grant]], [[Matthias Merzenich]], [[Tanner Jacobi]] || 39 | ||
|- | |- | ||
| [[25P3H1V0.1]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2015-01-06 || [[Martin Grant]] || | | [[25P3H1V0.1]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2015-01-06 || [[Martin Grant]] || 19 | ||
|- | |- | ||
| [[x66]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-01-11 || [[Martin Grant]] || 12 | | [[x66]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-01-11 || [[Martin Grant]], [[Tanner Jacobi]] || 12 | ||
|- | |- | ||
| [[weekender]] || data-sort-value="o 0.285714" | [[2c/7 orthogonal]] || 2015-01-25 || [[Martin Grant]] || | | [[weekender]] || data-sort-value="o 0.285714" | [[2c/7 orthogonal]] || 2015-01-25 || [[Chris Cain]], [[Martin Grant]], [[Tanner Jacobi]] || 57 | ||
|- | |- | ||
| [[pufferfish spaceship | | [[pufferfish spaceship]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-02-11 || [[Chris Cain]] || 51 | ||
|- | |- | ||
| [[Gemini]] || data-sort-value="oblique" | [[(2560,512)c/16849793]] || 2015-02-16 || [[Dave Greene]] || 173,449 | | [[Gemini]] || data-sort-value="oblique" | [[(2560,512)c/16849793]] || 2015-02-16 || [[Dave Greene]] || 173,449 | ||
|- | |- | ||
| half-[[ | | half-[[x66]] with [[HWSS]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-03-08 || [[Adam P. Goucher]], [[Aidan F. Pierce]], [[Chris Cain]], [[Matthias Merzenich]] || 9 | ||
|- | |- | ||
| [[B29]] || data-sort-value="d 0.25" | [[c/4 diagonal]] || 2015-04-06 || [[Tanner Jacobi]] || 25 | | [[B29]] || data-sort-value="d 0.25" | [[c/4 diagonal]] || 2015-04-06 || [[Tanner Jacobi]] || 25 | ||
Line 118: | Line 123: | ||
| [[copperhead]] || data-sort-value="o 0.1" | [[c/10 orthogonal]] || 2016-03-05 || [[Aidan F. Pierce]] || 13 | | [[copperhead]] || data-sort-value="o 0.1" | [[c/10 orthogonal]] || 2016-03-05 || [[Aidan F. Pierce]] || 13 | ||
|- | |- | ||
| [[fireship]] || data-sort-value="o 0.1" | [[c/10 orthogonal]] || 2016-03-21 || [[Nico Brown]] || 18 | | [[fireship]] || data-sort-value="o 0.1" | [[c/10 orthogonal]] || 2016-03-21 || [[Nico Brown]], [[Tanner Jacobi]] || 18 | ||
|- | |- | ||
| [[25P3H1V0.2]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2017-12-15 || [[Martin Grant]] || 26 | | [[25P3H1V0.2]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2017-12-15 || [[Martin Grant]] || 26 | ||
Line 126: | Line 131: | ||
| [[2-engine Cordership]] || data-sort-value="d 0.0833" | [[c/12 diagonal]] || 2017-12-31 || [[Dave Greene]] || 9 | | [[2-engine Cordership]] || data-sort-value="d 0.0833" | [[c/12 diagonal]] || 2017-12-31 || [[Dave Greene]] || 9 | ||
|- | |- | ||
| [[46P4H1V0]] || data-sort-value="o 0.25" | [[c/4 orthogonal]] || 2019-02-04 || [[Tanner Jacobi]] || 79 | | [[46P4H1V0]] || data-sort-value="o 0.25" | [[c/4 orthogonal]] || 2019-02-04 || [[Martin Grant]], [[Tanner Jacobi]] || 79 | ||
|- | |- | ||
| [[spider]] || data-sort-value="o 0.2" | [[c/5 orthogonal]] || 2019-03-07 || [[Martin Grant]] || | | [[spider]] || data-sort-value="o 0.2" | [[c/5 orthogonal]] || 2019-03-07 || [[Martin Grant]] || 233 | ||
|- | |- | ||
| [[camelship]] || data-sort-value="oblique" | [[(3,1)c/3948264]] || 2019-05-04 || [[Dave Greene]] || 26,614 | | [[camelship]] || data-sort-value="oblique" | [[(3,1)c/3948264]] || 2019-05-04 || [[Dave Greene]] || 26,614 | ||
|- | |- | ||
| [[27P4H1V1]] || data-sort-value="d 0.25" | [[c/4 diagonal]] || 2019-10-28 || [[Goldtiger997]] || 31 | | [[27P4H1V1]] || data-sort-value="d 0.25" | [[c/4 diagonal]] || 2019-10-28 || [[Goldtiger997]], [[Tanner Jacobi]] || 31 | ||
|- | |- | ||
| [[loopship]] || data-sort-value="o 0.0499977" | [[1000130c/20003511 orthogonal]] || 2020-01-08 || [[Dave Greene]] || 56,643 | | [[loopship]] || data-sort-value="o 0.0499977" | [[1000130c/20003511 orthogonal]] || 2020-01-08 || [[Dave Greene]] || 56,643 | ||
|- | |- | ||
| [[56P6H1V0]] || data-sort-value="o 0.167" | [[c/6 orthogonal]] || 2020-03-25 || [[Martin Grant]] || | | [[56P6H1V0]] || data-sort-value="o 0.167" | [[c/6 orthogonal]] || 2020-03-25 || [[AforAmpere]], [[Aidan F. Pierce]], [[Goldtiger997]], [[Martin Grant]], [[Tanner Jacobi]] || 292 | ||
|- | |||
| [[58P5H1V1]] || data-sort-value="d 0.2" | [[c/5 diagonal]] || 2020-04-03 || [[Adam P. Goucher]], [[Blinkerspawn]], [[Goldtiger997]], [[Peter Naszvadi]], [[Tanner Jacobi]] || 100 | |||
|- | |||
| [[31P8H4V0]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2020-04-10 || [[Goldtiger997]] || 37 | |||
|- | |||
| [[70P2H1V0.1]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2020-07-18 || [[Martin Grant]] || 187 | |||
|- | |||
| [[44P5H2V0]] || data-sort-value="o 0.4" | [[2c/5 orthogonal]] || 2020-08-29 || [[Goldtiger997]] || 38 | |||
|- | |||
| [[55P9H3V0]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2020-09-19 || [[Goldtiger997]] || 231 | |||
|- | |||
| [[Speed Demonoid]] || data-sort-value="d 0.1992019" | [[1642811c/8246964 diagonal]] || 2020-09-26 || [[Dave Greene]] || 31,822 | |||
|- | |||
| [[57P5H2V0]] || data-sort-value="o 0.4" | [[2c/5 orthogonal]] || 2020-11-02 || [[Goldtiger997]] || 394 | |||
|- | |- | ||
| [[ | | [[turtle]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2020-12-04 || [[Goldtiger997]] || 241 | ||
|- | |- | ||
| [[ | | [[edge-repair spaceship 1]] || data-sort-value="o 0.333" | [[c/3 orthogonal]] || 2021-01-24 || [[bubblegum]], [[goldenratio]] || 17 | ||
|- | |- | ||
| | | {{LinkCatagolue|xq4_2534uof1u0u1fou4352zy087084048078zx3igi3x3igi3|patternname=72P4H1V0|style=raw}}<ref name="post124810" /> || data-sort-value="o 0.25" | [[c/4 orthogonal]] || 2021-03-08 || [[Tanner Jacobi]], [[Goldtiger997]] || 213 | ||
|} | |} | ||
Line 150: | Line 169: | ||
A 3-glider synthesis of a [[pentadecathlon]] was found in April {{year|1997}} by [[Heinrich Koenig]], which came as a surprise because it was widely assumed that such a small synthesis would already be known. | A 3-glider synthesis of a [[pentadecathlon]] was found in April {{year|1997}} by [[Heinrich Koenig]], which came as a surprise because it was widely assumed that such a small synthesis would already be known. | ||
Along similar lines, a 3-glider synthesis of | Along similar lines, a 3-glider synthesis of a messy [[glider-producing switch engine]] was found in October {{year|2014}} by [[Michael Simkin]],<ref>{{cite web|url=http://www.conwaylife.com/forums/viewtopic.php?p=13988#p13988|title=Re: Making switch-engines|work=ConwayLife.com forums|author=Michael Simkin|date=October 24, 2014|accessdate=February 21, 2018}}</ref> and a 3-glider synthesis of a [[clean]] [[switch engine]] was discovered in March {{year|2017}} by [[Luka Okanishi]].<ref>{{cite web|url=http://conwaylife.com/forums/viewtopic.php?f=&p=41558#p41557|title=Re: Thread For Your Accidental Discoveries|work=ConwayLife.com forums|author=Luka Okanishi|date=March 12, 2017|accessdate=February 21, 2018}}</ref> | ||
==2-glider syntheses== | ==2-glider syntheses== | ||
Line 194: | Line 213: | ||
|author = Tanner Jacobi | |author = Tanner Jacobi | ||
|date = September 9, 2019 | |date = September 9, 2019 | ||
}}</ref> | |||
<ref name="post104484">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Binary slow salvos | |||
|p = 104484 | |||
|author = Adam P. Goucher | |||
|date = September 19, 2020 | |||
}}</ref> | }}</ref> | ||
<ref name="post83979">{{LinkForumThread | <ref name="post83979">{{LinkForumThread | ||
Line 208: | Line 234: | ||
|author = Martin Grant | |author = Martin Grant | ||
|date = February 8, 2020 | |date = February 8, 2020 | ||
}}</ref> | |||
<ref name="post125259">{{LinkForumThread | |||
|format = ref | |||
|title = Re: 20-bit still life syntheses | |||
|p = 125259 | |||
|author = Martin Grant | |||
|date = March 12, 2021 | |||
}}</ref> | }}</ref> | ||
<ref name="post37438">{{LinkForumThread | <ref name="post37438">{{LinkForumThread | ||
Line 222: | Line 255: | ||
|author = Goldtiger997 | |author = Goldtiger997 | ||
|date = May 24, 2017 | |date = May 24, 2017 | ||
}}</ref> | |||
<ref name="message799632200403648523">{{CiteDiscord | |||
|author = Adam P. Goucher | |||
|date = January 15, 2021 | |||
|channel = cgol | |||
|id = 799632200403648523 | |||
}}</ref> | |||
<ref name="post124810">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Small Spaceship Syntheses | |||
|p = 124810 | |||
|author = Goldtiger997 | |||
|date = March 8, 2021 | |||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
==External links== | ==External links== | ||
*[https://catagolue. | *[https://catagolue.hatsya.com/syntheses Catagolue synthesis database] | ||
*[http://codercontest.com/mniemiec/lifepage.htm Mark Niemiec's glider synthesis database] | *[http://codercontest.com/mniemiec/lifepage.htm Mark Niemiec's glider synthesis database] | ||
*[http://radicaleye.com/DRH/life.html Dean Hickerson's Life page] with four pages of glider syntheses | *[http://radicaleye.com/DRH/life.html Dean Hickerson's Life page] with four pages of glider syntheses | ||
Line 232: | Line 278: | ||
*[http://pentadecathlon.com/constructions/components/components.php Heinrich Koenig's component catalog] on pentadecathlon.com | *[http://pentadecathlon.com/constructions/components/components.php Heinrich Koenig's component catalog] on pentadecathlon.com | ||
{{LinkLexicon|lex_g.htm#glidersynthesis}} | {{LinkLexicon|lex_g.htm#glidersynthesis}} | ||
===Forum threads=== | ===Forum threads=== | ||
{{LinkForumThread|f=2|t=3267|title=Still Life Synthesis Thread}} | {{LinkForumThread|f=2|t=3267|title=Still Life Synthesis Thread}} |
Revision as of 03:19, 2 April 2021
Glider synthesis (or glider construction) is the construction of an object by means of glider collisions. It is generally assumed that the gliders should be arranged so that they could come from infinity - that is, gliders should not have had to pass through one another to achieve the initial arrangement (or else it is considered “not fully functional”). LWSSes, MWSSes and HWSSes can also be used in syntheses; these spaceships can themselves be easily synthesized from gliders at any point along their trajectory, so this conversion is often left as an implicit step.
Features of syntheses
Four main characterizing features of a synthesis are the geometry, construction time, glider cost, and number of stages.
The geometry is the number of directions of incoming gliders:
- four-directional: gliders collide from all four directions
- three-directional: gliders collide from all directions but one
- two-directional; further divisible in head-on and 90° syntheses. All two-glider syntheses are necessarily two-directional.
- unidirectional, which assumes the initial presence of a target (usually a still life or an oscillator) to be hit with gliders.
Since gliders are themselves glider-constructible, any multidirectional synthesis can be technically downgraded to a fewer-directional one, usually at the cost of increasing the construction time, cost, and/or number of stages needed for the synthesis. More challenging is finding a two- or three-directional synthesis for a particular object where few or no parts of the synthesis reactions extend outside the final pattern's bounding box in a particular direction. This is especially important for the synthesis of temporary bait objects, which will need to be placed sometimes quite close to other components without perturbing them. For especially tight locations, sometimes it will be useful to construct an LWSS (or another standard c/2 spaceship) some distance away from the synthesis nexus and let that collide with a glider in the final stages; this allows synthesis at a 45° angle, rather than a 90° angle as required for synthesis by gliders from separate directions.
The construction time is simply the number of generations it takes to complete a synthesis. For multi-stage syntheses, each stage has its own construction time.
The number of stages is a count of how many separate operations a synthesis can be divided into, with pauses of arbitrary length between the stages. Often a particular synthesis operation cannot be achieved by a direct collision of gliders, and a synthesis procedure instead requires first synthesizing a number of bait objects, and then hitting these with gliders to produce the final result.
The cost is the number of gliders expended over the course of the synthesis. Similar to the construction time, it can be defined also for individual synthesis stages. A *WSS is considered to cost 3 gliders. The discovery of the reverse caber tosser in 2018 proved that there is a universal constant upper bound on the cost to synthesise any synthesisable object; currently, the best known upper bound is 15 gliders.
Of particular interest is slow salvo synthesis: unidirectional synthesis where every stage has a glider cost of one. Perhaps surprisingly, anything that is glider synthesizable is also slow salvo synthesizable; a result that crucially depends on the existence of movable targets, one-time turners, and splitters.
Still life syntheses
In the 1990s, glider syntheses for all still lifes and known oscillators with at most 14 cells were found by David Buckingham. Almost all of these were successfully reduced to a synthesis cost of less than 1 glider per ON cell, or "1 glider per bit".[1]
A collaborative effort ending in May 2014 completed glider syntheses of all still lifes with 17 or fewer cells.[2][3][4] A second, longer effort claimed to have completed all the 18-bit still lifes in November 2014,[5][6] but it was later found that some of these syntheses were erroneous.[citation needed] The project was finally completed for real in October 2019.[7] The syntheses for 19-bit still lifes were completed in February 2020,[8] and 20-bit still lifes in March 2021.[9] Later optimization projects reduced the maximum cost of construction for 15-bit,[10][11] 16-bit,[12][13] and 17-bit[14] still lifes to less than one glider per bit, in November 2016, May 2017, and September 2019 respectively.
In September 2020, the 17-glider reverse caber-tosser proved that all synthesizable still lifes could theoretically be constructed with no more than one glider per bit.[15]
The following table displays statistics about the costs (excluding RCT constructions) for strict and pseudo still lifes with up to 20 cells as of January 31, 2021.[16]
Live cells | Strict still lifes | Pseudo still lifes | |||||
---|---|---|---|---|---|---|---|
Count ( A019473) |
Min. cost | Avg. cost | Max. cost | Count ( A056613) |
Min. cost | Max. cost | |
4 | 2 | 2 | 2.500 | 3 | 0 | – | – |
5 | 1 | 2 | 2.000 | 2 | 0 | – | – |
6 | 5 | 2 | 3.200 | 4 | 0 | – | – |
7 | 4 | 2 | 2.750 | 4 | 0 | – | – |
8 | 9 | 2 | 3.556 | 4 | 1 | 2 | 2 |
9 | 10 | 3 | 4.000 | 5 | 1 | 3 | 3 |
10 | 25 | 4 | 4.360 | 5 | 7 | 3 | 5 |
11 | 46 | 4 | 4.913 | 7 | 16 | 3 | 7 |
12 | 121 | 4 | 5.843 | 8 | 55 | 3 | 9 |
13 | 240 | 4 | 6.338 | 8 | 110 | 4 | 10 |
14 | 619 | 3 | 7.249 | 10 | 279 | 3 | 11 |
15 | 1,353 | 4 | 8.343 | 12 | 620 | 4 | 12 |
16 | 3,286 | 3 | 9.383 | 14 | 1,645 | 4 | 25[n 1][n 2] |
17 | 7,773 | 4 | 10.601 | 16 | 4,067 | 4 | 19[n 1][n 3] |
18 | 19,044 | 4 | 12.071 | 30[n 1][n 4] | 10,843 | 4 | 2 unsynthesized[n 5] |
19 | 45,759 | 4 | 13.580 | 72[n 1][n 6] | 27,250 | 4 | 4 unsynthesized[n 7] |
20 | 112,243 | 4 | 321 unsynthesized[n 8] | 70,637 | [n 9] |
- ↑ 1.0 1.1 1.2 1.3 15 gliders using the reverse caber-tosser
- ↑ All but 5 16-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.
- ↑ All but 7 17-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.
- ↑ All but 727 18-bit strict still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.
- ↑ All but 49 18-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.
- ↑ All but 3,405 19-bit strict still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.
- ↑ All but 105 19-bit pseudo still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.
- ↑ All but 14,330 20-bit strict still lifes can be constructed with strictly less than one glider per bit as of January 31, 2021.
- ↑ 20-bit pseudo still lifes are currently not fully tabulated on Catagolue due to a combination of size constraints and the ongoing status of the 20-bit strict still life synthesis project.[17]
Spaceship syntheses
Perhaps the most interesting glider syntheses are those of spaceships, because these can be used to create corresponding guns and rakes. Many of the c/2 spaceships that are based on standard spaceships have been synthesized, mostly by Mark Niemiec. In June 1998, Stephen Silver found syntheses for some of the Corderships (although it was not until July 1999 that Jason Summers used this to build a Cordership gun). Many larger Corderships also have known glider syntheses, and others could easily be generated using the same techniques. In general, larger Corderships have declined in importance after the discovery of four-, three- and two-engine versions.
In May 2000, Noam Elkies suggested that 60P5H2V0, a 2c/5 spaceship found by Tim Coe in May 1996 might be a candidate for glider synthesis. Initial attempts to construct a synthesis for this spaceship got fairly close, but it was only in March 2003 that Summers and Elkies managed to find a way to perform the crucial last step. Summers then used the new synthesis to build a c/2 forward rake for the 2c/5 spaceship; this was the first example in Life of a rake which fires spaceships that travel in the same direction as the rake but more slowly.
After the loafer was discovered and synthesized in 2013, a number of new spaceship syntheses were found during a short period of time in late 2014 and early 2015, including the dart, crab, 25P3H1V0.2, 30P5H2V0, x66, and weekender. Most of this was due to the work of Martin Grant.
Other syntheses of note
A 3-glider synthesis of a pentadecathlon was found in April 1997 by Heinrich Koenig, which came as a surprise because it was widely assumed that such a small synthesis would already be known.
Along similar lines, a 3-glider synthesis of a messy glider-producing switch engine was found in October 2014 by Michael Simkin,[19] and a 3-glider synthesis of a clean switch engine was discovered in March 2017 by Luka Okanishi.[20]
2-glider syntheses
- Main article: 2-glider collision
There are 71 distinct 2-glider collisions, of which 28 produce nothing, six produce a block, five produce a honey farm, three produce a B-heptomino, three produce a pi-heptomino, three produce a blinker, three produce a traffic light, two produce a glider, two produce a pond, two produce a loaf and a blinker, one produces a boat, one produces a beehive, one produces a loaf, one produces an eater 1, one produces lumps of muck, one produces a teardrop, one produces an interchange, one produces a traffic light and a glider, one produces an octomino, one produces a bi-block, one produces four blocks, one produces two blocks, one produces a blinker, loaf, tub and block, and one produces the so-called two-glider mess, a methuselah stabilizing after 530 generations and consisting of four gliders, eight blinkers (including a traffic light), four blocks, a beehive and a ship.
All 71 such syntheses can be seen below in a pattern put together by Jason Summers on January 29, 2005:
All 71 distinct 2-glider collisions, arranged by what they synthesize. (click above to open LifeViewer) RLE: here Plaintext: here |
See also
References
- ↑ Mark D. Niemiec (June 20, 2015). "Re: 4 glider syntheses". ConwayLife.com forums. Retrieved on February 21, 2018.
- ↑ Dave Greene (May 23, 2014). "Constructions Known for All Still Lifes up to 17 Bits". Game of Life News. Retrieved on September 17, 2014.
- ↑ Martin Grant (January 6, 2014). "17-bit SL Syntheses (100% Complete!)". ConwayLife.com forums. Retrieved on September 17, 2014.
- ↑ Martin Grant (May 17, 2014). Re: 17-bit SL Syntheses (discussion thread) at the ConwayLife.com forums
- ↑ Martin Grant (October 2, 2014). "18-bit SL Syntheses (100% Complete!)". ConwayLife.com forums. Retrieved on February 21, 2018.
- ↑ Martin Grant (November 12, 2014). Re: 18-bit SL Syntheses (discussion thread) at the ConwayLife.com forums
- ↑ Ian07 (October 9, 2019). Re: 18-bit SL Syntheses (100% Complete!) (discussion thread) at the ConwayLife.com forums
- ↑ Martin Grant (February 8, 2020). Re: 19-bit still life syntheses (discussion thread) at the ConwayLife.com forums
- ↑ Martin Grant (March 12, 2021). Re: 20-bit still life syntheses (discussion thread) at the ConwayLife.com forums
- ↑ BlinkerSpawn (October 27, 2016). "15 in 15: Efficient 15-bit Synthesis Project (DONE!)". ConwayLife.com forums. Retrieved on February 21, 2018.
- ↑ Martin Grant (November 19, 2016). Re: 15 in 15: Efficient 15-bit Synthesis Project (2 SLs remain) (discussion thread) at the ConwayLife.com forums
- ↑ Bob Shemyakin (December 20, 2016). "16 in 16: Efficient 16-bit Synthesis Project". ConwayLife.com forums. Retrieved on February 21, 2018.
- ↑ Goldtiger997 (May 24, 2017). Re: 15 in 15: Efficient 15-bit Synthesis Project (2 SLs remain) (discussion thread) at the ConwayLife.com forums
- ↑ Tanner Jacobi (September 9, 2019). Re: 17 in 17: Efficient 17-bit synthesis project (discussion thread) at the ConwayLife.com forums
- ↑ Adam P. Goucher (September 19, 2020). Re: Binary slow salvos (discussion thread) at the ConwayLife.com forums
- ↑ Adam P. Goucher. "Syntheses". Catagolue. Retrieved on January 31, 2021.
- ↑ Adam P. Goucher (January 15, 2021). Message in #cgol on the Conwaylife Lounge Discord server
- ↑ Goldtiger997 (March 8, 2021). Re: Small Spaceship Syntheses (discussion thread) at the ConwayLife.com forums
- ↑ Michael Simkin (October 24, 2014). "Re: Making switch-engines". ConwayLife.com forums. Retrieved on February 21, 2018.
- ↑ Luka Okanishi (March 12, 2017). "Re: Thread For Your Accidental Discoveries". ConwayLife.com forums. Retrieved on February 21, 2018.
External links
- Catagolue synthesis database
- Mark Niemiec's glider synthesis database
- Dean Hickerson's Life page with four pages of glider syntheses
- Martin Grant's synthesis component database, version 3
- Heinrich Koenig's component catalog on pentadecathlon.com
- Glider synthesis at the Life Lexicon
Forum threads
- Still Life Synthesis Thread (discussion thread) at the ConwayLife.com forums
- Synthesising Oscillators (discussion thread) at the ConwayLife.com forums
- Small Spaceship Syntheses (discussion thread) at the ConwayLife.com forums
- Soup-based syntheses (discussion thread) at the ConwayLife.com forums
- Randomly enumerating glider syntheses (discussion thread) at the ConwayLife.com forums
- 4 glider syntheses (discussion thread) at the ConwayLife.com forums
- Synthesis components (discussion thread) at the ConwayLife.com forums