Difference between revisions of "Glider synthesis"
m (added a few links, and improved the text a little (maybe))
|Line 1:||Line 1:|
'''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”). LWSS, MWSS and HWSS can also be used in syntheses
'''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”). LWSS, MWSSand HWSScan also be used in synthesescan be .
==Features of syntheses==
==Features of syntheses==
Revision as of 13:08, 25 November 2018
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, reaction speed, reaction multiplicity, and glider cost.
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 speed, multiplicity and cost of 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 catalysts, 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 ways 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 speed is simply the number of generations it takes to complete a synthesis. For multi-stage syntheses, each stage has its own speed.
The multiplicity is the number of stages a synthesis operates in. 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 catalysts, 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. Much as speed, it can be defined also for individual synthesis stages. A *WSS is considered to cost 3 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 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".
A collaborative effort ending in May 2014 completed glider syntheses of all still lifes with 17 or fewer cells. A second, longer effort completed all the 18-bit still lifes in November 2014. Later optimization projects reduced the maximum cost of construction for 15-bit and 16-bit still lifes to less than one glider per bit, in November 2016 and May 2017 respectively.
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 a 2c/5 spaceship (60P5H2V0) 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.
|Name||First synthesis||Best current synthesis|
|2-engine Cordership||2017-12-31||Dave Greene||9|
|copperhead||2016-03-05||Aidan F. Pierce||13|
|half-X66 with HWSS||2015-03-08||Chris Cain||9|
|loafer||2013-02-17||Adam P. Goucher||8|
|Pushalong 1||2015-06-12||Martin Grant||77|
|0hd Demonoid||2015-12-06||Chris Cain||12,016|
|Parallel HBK||2014-12-31||Michael Simkin||38,380|
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 anything using just three gliders would already be known.
Along similar lines, a 3-glider synthesis of an infinite growth pattern was found in October 2014 by Michael Simkin, and a 3-glider synthesis of a clean switch engine was discovered in March 2017 by Luka Okanishi.
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.
- "Re: 4 glider syntheses". ConwayLife.com forums. Mark D. Niemiec. Retrieved on February 21, 2018.
- "Constructions Known for All Still Lifes up to 17 Bits". Game of Life News. Dave Greene. Retrieved on September 17, 2014.
- "17-bit SL Syntheses (100% Complete!)". ConwayLife.com forums. Martin Grant. Retrieved on September 17, 2014.
- "18-bit SL Syntheses (100% Complete!)". ConwayLife.com forums. Martin Grant. Retrieved on February 21, 2018.
- "15 in 15: Efficient 15-bit Synthesis Project (DONE!)". ConwayLife.com forums. BlinkerSpawn. Retrieved on February 21, 2018.
- "16 in 16: Efficient 16-bit Synthesis Project". ConwayLife.com forums. Bob Shemyakin. Retrieved on February 21, 2018.
- "Re: Making switch-engines". ConwayLife.com forums. Michael Simkin. Retrieved on February 21, 2018.
- "Re: Thread For Your Accidental Discoveries". ConwayLife.com forums. Luka Okanishi. Retrieved on February 21, 2018.
- 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