Glider synthesis
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 32 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] Later optimization projects reduced the maximum cost of construction for 15-bit,[9][10] 16-bit,[11][12] and 17-bit[13] still lifes to less than one glider per bit, in November 2016, May 2017, and September 2019 respectively.
The following table displays the minimum, average, and maximum costs for strict still lifes with up to 20 cells as of February 8, 2020.[14]
Live cells | Count ( | Min. cost | Avg. cost | Max. cost |
---|---|---|---|---|
4 | 2 | 2 | 2.500 | 3 |
5 | 1 | 2 | 2.000 | 2 |
6 | 5 | 2 | 3.200 | 4 |
7 | 4 | 2 | 2.750 | 4 |
8 | 9 | 2 | 3.556 | 4 |
9 | 10 | 3 | 4.000 | 5 |
10 | 25 | 4 | 4.360 | 5 |
11 | 46 | 4 | 4.913 | 7 |
12 | 121 | 4 | 5.926 | 8 |
13 | 240 | 4 | 6.571 | 9 |
14 | 619 | 3 | 7.360 | 10 |
15 | 1,353 | 4 | 8.517 | 12 |
16 | 3,286 | 3 | 9.585 | 14 |
17 | 7,773 | 4 | 10.838 | 16 |
18 | 19,044 | 4 | 12.420 | 30[n 1] |
19 | 45,759 | 4 | 14.098 | 76[n 2] |
20 | 112,243 | 4 | 1230 unsynthesized[n 3] |
- All but 788 18-bit still lifes can be constructed with strictly less than one glider per bit as of August 15, 2020.
- All but 3,710 19-bit still lifes can be constructed with strictly less than one glider per bit as of August 15, 2020.
- All but 15,477 20-bit still lifes can be constructed with strictly less than one glider per bit as of August 15, 2020.
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 an infinite growth pattern was found in October 2014 by Michael Simkin,[15] and a 3-glider synthesis of a clean switch engine was discovered in March 2017 by Luka Okanishi.[16]
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:
<html><div class="rle"><div class="codebox"><div style="display:none;"><code></html>x = 379, y = 369, rule = B3/S23
154bo36bo18bo$58bo18bo19bo16bo19bo18bo19bo16bo18bo36bo$57bo18bo19bo16b
o19bo19b3o16bo17b3o16b3o15bo17bo$57b3o16b3o17b3o14b3o17b3o36b3o51bo18b
3o$226b3o4$190bo$58b3o17b3o89bo18b2o55bo$58bo19bo20bo17bo20bo13b2o15b
2o18bobo14b2o20bo16b2o$59bo19bo18b2o16b2o19b2o13bobo14bobo34bobo18b2o
16bobo$98bobo15bobo18bobo12bo53bo20bobo$bo4bo3bobo3bobobo2bo3bo3bo3bo
4bo4bobo2$bobo2bo2bo3bo4bo4bo3bo3bo3bobo2bo2bo2$bo2bobo2bo3bo4bo4bobob
o3bo3bo2bobo2bo2bobo2$bo4bo2bo3bo4bo4bo3bo3bo3bo4bo2bo4bo266bo$269bo
22bo21bo62bo$bo4bo3bobo5bo4bo3bo3bo3bo4bo4bobo182bo15bo21bo22bo22b3o
18bo22bo17bo$229bo15bo22b3o20b3o40bo22bo18b3o$86bo16bo17bo16bo16bo15bo
17bo16bo22b3o13b3o86b3o20b3o$66bo18bo16bo17bo16bo16bo15bo17bo16bo$65bo
19b3o14b3o15b3o14b3o14b3o13b3o15b3o14b3o$65b3o4$224b3o15b3o59b2o$76b3o
16b3o16b3o15b3o15b3o14b3o16b3o15b3o19bo17bo11b2o23b2o20bobo20b2o40b2o$
54b3o21bo18bo18bo17bo17bo16bo18bo17bo18bo17bo13b2o23b2o21bo21b2o12b2o
26b2o$56bo20bo18bo18bo17bo17bo16bo18bo17bo50bo24bo44bo15b2o24bo$55bo
285bo23$106bo157bo$74bo30bo157bo38bo$2bobo4bo6bo3bo4bo2bo3bo2bobobo2bo
bo28bo15bo15b3o119bobobo2bo28b3o14bo20bo$46bo26b3o12bo190bo21b3o$2bo3b
o2bo6bo3bobo2bo2bo2bo3bo6bo45b3o138bo4bo44b3o$46bo$2bobo4bo6bo3bo2bobo
2bobo4bobobo2bobo184bo4bo2$2bo3bo2bo6bo3bo4bo2bo2bo3bo6bo2bo183bo4bo$
305b3o$2bobo4bobobo2bo3bo4bo2bo3bo2bobobo2bo3bo61b2o119bo4bobobo44bo
21bo$108bobo146b2o23b2o22bo$66b2o21b2o17bo149b2o22bobo$65bobo21bobo
165bo$67bo21bo17$84bo15bo39bo153bo24bo19bo$bobo4bo7bobo4bobo3bo3bo28bo
20bo15bo39bo88bo3bo2bobobo20bo16bo15bo24bo19bo$61bo21b3o13b3o15bo21b3o
17bo99bo16bo16b3o22b3o17b3o$bo3bo2bo6bo3bo2bo3bo2bo2bo28b3o52bo41bo69b
o3bo2bo23b3o14b3o$116b3o39b3o$bobo4bo6bo3bo2bo6bobo196bobobo2bobobo2$b
o3bo2bo6bo3bo2bo3bo2bo2bo195bo3bo2bo2$bobo4bobobo3bobo4bobo3bo3bo85b3o
106bo3bo2bo$54b3o62bo17b2o16bo103bo35b2o35b2o$56bo21b2o15b2o23bo16bobo
14b2o102b2o16b2o17bobo11b2o22b2o$55bo23b2o15b2o39bo16bobo101bobo15bobo
16bo14b2o20bo$78bo16bo180bo32bo6$73b2o19b2o$74bo20bo152b2o$249bo7$64bo
233bo$63bo20bo194bo17bo$63b3o17bo166bo27bo18b3o$2bobo3bo6bo3bobo4bobob
o2bobo47b3o143bobo17bo28b3o$37bo211b3o$o7bo6bo3bo3bo2bo6bo195bo3bo$37b
o275b2o$o2bobo2bo6bo3bo3bo2bobobo2bobo193bobo82bo$256b2o$o4bo2bo6bo3bo
3bo2bo6bo2bo192bo3bo23bo$80bo$2bobo3bobobo2bo3bobo4bobobo2bo3bo20b2o
19b2o148bobo18bo42b2o$57bobo19bobo167b2o13b2o26bobo$59bo189bobo13b2o
27bo$264bo14$252b2o24b2o$253bo25bo$258bo15bo$257bo15bo26bo$61bo195b3o
13b3o23bo$obo5bobo5bo4bobobo34bo167bobo4bo63b3o$60b3o169bo45bo24b3o$o
3bo2bo3bo3bobo5bo204bo6bo41b2o24bo$232bo44bobo24bo$obo4bo3bo2bo3bo4bo
204bobo4bo19b2o37b2o$254bobo38bo$o3bo2bo3bo2bobobo4bo204bo6bo20bo2$obo
5bobo3bo3bo4bo204bo6bo2$53b2o$54b2o$53bo18$3bo3bo3bo3bo3bo2bobobo30bo
169bo6bobo3bo5bo18bo$56bo207bo$3bo3bo3bo3bo3bo2bo33b3o168bo5bo3bo2bobo
bobo17b3o2$3bobobo3bo3bo3bo2bobobo200bo5bo3bo2bo2bo2bo2$3bo3bo3bo4bobo
3bo204bo5bo3bo2bo5bo2$3bo3bo3bo5bo4bobobo32b3o165bobobo2bobo3bo5bo$59b
o203bo$60bo201b2o$262bobo17$67bo$66bo$4bo6bobo5bo4bobobo37b3o157bobobo
2bobobo4bo4bobo4bobo4bobo5bobo3bobo$251bo13bo13bo17bo$4bo5bo3bo3bobo3b
o203bo4bo7bobo3bo6bo3bo2bo6bo3bo2bo20bo$251bo13bo13bo16b3o$4bo5bo3bo2b
o3bo2bobobo199bo4bobobo2bo3bo2bobo4bo3bo2bobo4bo3bo2bobo2$4bo5bo3bo2bo
bobo2bo203bo4bo6bobobo2bo2bo3bo3bo2bo2bo3bo3bo2bo2$4bobobo2bobo3bo3bo
2bo203bo4bobobo2bo3bo2bo3bo2bobo4bo3bo3bobo3bo$58b2o239bo$57bobo238b2o
$59bo238bobo16$59bo$58bo$58b3o264bo$3bobobo4bo4bobobo2bobobo2bobo193bo
3bo4bo2bobobo2bobobo2bobo5bobo3bo3bo4bo4bo4bo4bobo3bobobo22bo$35bo221b
o66b3o$3bo7bobo5bo4bo6bo195bo3bobo2bo4bo4bo6bo6bo3bo2bo3bo3bobo3bobo2b
o2bo7bo$35bo221bo$3bobobo2bo3bo4bo4bobobo2bobo193bo3bo2bobo4bo4bobobo
2bobo4bo6bobobo2bo3bo2bo2bobo2bo2bobo2bobobo$57bo$3bo6bobobo4bo4bo6bo
2bo21b2o169bo3bo4bo4bo4bo6bo2bo3bo3bo2bo3bo2bobobo2bo4bo2bo4bo2bo26b3o
$56bobo265bo$3bobobo2bo3bo4bo4bobobo2bo3bo191bo3bo4bo4bo4bobobo2bo3bo
3bobo3bo3bo2bo3bo2bo4bo4bobo3bobobo23bo11$305b2o$306bo9$55bo16bo237bo$
2bobo5bobo3bo4bo2bobo27bo16bo155bobobo2bo14bobo3bo6bo3bobo4bobobo2bobo
26bo$6bo47b3o14b3o210bo24b3o$2bo6bo3bo2bobo2bo2bo3bo200bo4bo7bo4bo7bo
6bo3bo3bo2bo6bo$6bo277bo$2bobo4bo3bo2bo2bobo2bo3bo200bo4bo5bobobo2bo2b
obo2bo6bo3bo3bo2bobobo2bobo2$2bo6bo3bo2bo4bo2bo3bo200bo4bo7bo4bo4bo2bo
6bo3bo3bo2bo6bo2bo26b3o$310bo$2bo7bobo3bo4bo2bobo46bo155bo4bobobo10bob
o3bobobo2bo3bobo4bobobo2bo3bo26bo$50b2o20b2o$51b2o19bobo$50bo19$2bobo
5bo7bobo4bo7bobo4bobo3bo3bo2$2bo3bo3bo7bo3bo2bo6bo3bo2bo3bo2bo2bo28bo
239bo$77bo239bo$2bobo5bo2bobo2bobo4bo6bo3bo2bo6bobo28b3o237b3o$229bobo
4bobo3bobobo3bobo3bo5bo3bo3bo4bo3bobo$2bo3bo3bo7bo3bo2bo6bo3bo2bo3bo2b
o2bo$228bo3bo2bo3bo4bo4bo3bo2bobobobo3bo3bobo2bo2bo3bo$2bobo5bo7bobo4b
obobo3bobo4bobo3bo3bo$228bo3bo2bo8bo4bo3bo2bo2bo2bo3bo3bo2bobo2bo3bo$
77b3o$77bo150bo3bo2bo3bo4bo4bo3bo2bo5bo3bo3bo4bo2bo3bo$78bo$229bobo4bo
bo5bo5bobo3bo5bo3bo3bo4bo3bobo26b2o$307bobo$309bo7$276b2o37b2o$277bo
38bo6$112bo13bo$2bo6bobo5bo4bobobo9bobo4bo6bo3bo4bo2bo3bo2bobobo2bobo
32bo13bo$80bo30b3o11b3o$2bo5bo3bo3bobo3bo8bo4bo3bo2bo6bo3bobo2bo2bo2bo
3bo6bo$80bo$2bo5bo3bo2bo3bo2bobobo2bobobo2bobo4bo6bo3bo2bobo2bobo4bobo
bo2bobo2$2bo5bo3bo2bobobo2bo8bo4bo3bo2bo6bo3bo4bo2bo2bo3bo6bo2bo2$2bob
obo2bobo3bo3bo2bo13bobo4bobobo2bo3bo4bo2bo3bo2bobobo2bo3bo$107b2o21b2o
195bo$107bobo20bobo193bo$107bo22bo98bobobo9bobo3bo6bo3bobo4bobobo2bobo
7bo5bo2bobobo3bobo3bobo16b3o$278bo$233bo7bo7bo6bo3bo3bo2bo6bo9bobobobo
2bo6bo5bo$278bo$229bobobo2bobo2bo2bobo2bo6bo3bo3bo2bobobo2bobo7bo2bo2b
o2bobobo3bobo3bobo2$229bo11bo4bo2bo6bo3bo3bo2bo6bo2bo6bo5bo2bo10bo5bo$
324bo$229bobobo9bobo3bobobo2bo3bobo4bobobo2bo3bo5bo5bo2bobobo3bobo3bob
o13b2o$323bobo7$69bo$68bo$46bo21b3o34bo$3bo5bo3bo3bobo4bobo18bo58bo$
45b3o56b3o$3bobobobo3bo2bo6bo3bo2$3bo2bo2bo3bo3bobo3bo2$3bo5bo3bo6bo2b
o3bo19b3o$47bo24b2o17b3o177b2o32b2o$3bo5bo3bo3bobo4bobo21bo23bobo18bo
178bo33bo$72bo19bo!
#C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]]
#C [[ WIDTH 1200 HEIGHT 1200 ZOOM 3 ]]<html></code></div></div><canvas width="200" height="300" style="margin-left:1px;"><noscript></html> Please enable Javascript to view this LifeViewer. <html></noscript></canvas></div></html> |
All 71 distinct 2-glider collisions, arranged by what they synthesize. (click above to open LifeViewer) RLE: here Plaintext: here |
See also
- List of known glider syntheses
- Salvo
- Tutorials/Glider syntheses
- Shinjuku
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
- 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. "Syntheses". Catagolue. Retrieved on February 8, 2020.
- 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