Difference between revisions of "Glider synthesis"

From LifeWiki
Jump to navigation Jump to search
(12 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{EmbedViewer
|pname = loafer_synth
|position = right
|caption = An 8-glider synthesis of a [[loafer]]<br>
|viewerconfig = #C [[ ZOOM 8 ]]
}}
{{Glossary}}
{{Glossary}}
'''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]]es, [[MWSS]]es and [[HWSS]]es 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.
'''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]]es, [[MWSS]]es and [[HWSS]]es 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==
==Features of syntheses==
Four main characterizing features of a synthesis are the ''geometry'', ''reaction speed'', ''reaction multiplicity''<!--or is there a more standard term?-->, and ''glider cost''.
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:
The '''geometry''' is the number of directions of incoming gliders:
Line 10: Line 16:
* two-directional; further divisible in head-on and 90° syntheses. All two-glider syntheses are necessarily two-directional.
* 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.
* 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.
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 '''speed''' is simply the number of [[generation]]s it takes to complete a synthesis. For multi-stage syntheses, each stage has its own speed.
The '''construction time''' is simply the number of [[generation]]s it takes to complete a synthesis. For multi-stage syntheses, each stage has its own construction time.


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 [[catalyst]]s, and then hitting these with gliders to produce the final result.
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. Much as speed, 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 35 gliders.
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 35 gliders.


Of particular interest is [[salvo|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 target]]s and [[splitter]]s.
Of particular interest is [[salvo|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 target]]s, [[one-time]] [[turner]]s, and [[splitter]]s.


==Still life syntheses==
==Still life syntheses==
In the 1990s, glider syntheses for all [[still life]]s and known [[oscillator]]s with at most 14 [[cell]]s were found by [[:Category:Patterns found by David Buckingham|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|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|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 |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 |accessdate=September 17, 2014}}</ref>  A second, longer effort 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|accessdate=February 21, 2018}}</ref>  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|accessdate=February 21, 2018}}</ref> and 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|accessdate=February 21, 2018}}</ref> still lifes to less than one glider per bit, in November 2016 and May 2017 respectively.
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 |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 |accessdate=September 17, 2014}}</ref>  A second, longer effort 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|accessdate=February 21, 2018}}</ref>  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|accessdate=February 21, 2018}}</ref> 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|accessdate=February 21, 2018}}</ref> and 17-bit<ref name="post82560" /> still lifes to less than one glider per bit, in November 2016, May 2017, and September 2019 respectively.


==Spaceship syntheses==
==Spaceship syntheses==
Perhaps the most interesting glider syntheses are those of [[spaceship]]s, because these can be used to create corresponding [[gun]]s and [[rake]]s. Many of the [[:Category:Spaceships with speed c/2|c/2]] spaceships that are based on standard spaceships have been synthesized, mostly by [[:Category:Patterns found by Mark Niemiec|Mark Niemiec]]. In June [[:Category:Patterns found in 1998|1998]], [[:Category:Patterns found by Stephen Silver|Stephen Silver]] found syntheses for some of the [[Cordership]]s (although it was not until July [[:Category:Patterns found in 1999|1999]] that [[:Category:Patterns found by Jason Summers|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.
Perhaps the most interesting glider syntheses are those of [[spaceship]]s, because these can be used to create corresponding [[gun]]s and [[rake]]s. Many of the [[c/2]] spaceships that are based on standard spaceships have been synthesized, mostly by [[Mark Niemiec]]. In June {{year|1998}}, [[Stephen Silver]] found syntheses for some of the [[Cordership]]s (although it was not until July {{year|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 [[:Category:Patterns found in 2000|2000]], [[Noam Elkies]] suggested that a [[:Category:Spaceships with speed 2c/5|2c/5]] spaceship ([[60P5H2V0]]) found by [[:Category:Patterns found by Tim Coe|Tim Coe]] in May [[:Category:Patterns found in 1996|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 [[:Category:Patterns found in 2003|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 [[Conway's Game of Life|Life]] of a rake which fires spaceships that travel in the same direction as the rake but more slowly.
In May {{year|2000}}, [[Noam Elkies]] suggested that [[60P5H2V0]], a [[2c/5]] spaceship found by [[Tim Coe]] in May {{year|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 {{year|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 [[Conway's Game of Life|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 [[:Category:Patterns found by Martin Grant|Martin Grant]].
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]].


{| class="wikitable sortable"
{| class="wikitable sortable"
Line 63: Line 69:
| [[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
|-
|-
| [[Pushalong 1]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-06-12 || [[Martin Grant]] || 77
| [[Pushalong 1]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-06-12 || [[Martin Grant]] || 58
|-
|-
| [[30P4H2V0.4]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-09-10 || [[Tanner Jacobi]] || 85
| [[30P4H2V0.4]] || data-sort-value="o 0.5" | [[c/2 orthogonal]] || 2015-09-10 || [[Tanner Jacobi]] || 85
Line 79: Line 85:
| [[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 || [[Martin Grant]] || 88
| [[46P4H1V0]] || data-sort-value="o 0.25" | [[c/4 orthogonal]] || 2019-02-04 || [[Tanner Jacobi]] || 88
|-
|-
| [[spider]] || data-sort-value="o 0.2" | [[c/5 orthogonal]] || 2019-03-07 || [[Martin Grant]] || 584
| [[spider]] || data-sort-value="o 0.2" | [[c/5 orthogonal]] || 2019-03-07 || [[Martin Grant]] || 537
|}
|}


Line 87: Line 93:
[[Image:glider_synth_pentadecathlon.png|framed|right|A 3-glider synthesis of a [[pentadecathlon]].]]
[[Image:glider_synth_pentadecathlon.png|framed|right|A 3-glider synthesis of a [[pentadecathlon]].]]


A 3-glider synthesis of a [[pentadecathlon]] was found in April {{year|1997}} by [[:Category:Patterns found by Heinrich Koenig|Heinrich Koenig]], which came as a surprise because it was widely assumed that such as 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 an [[infinite growth]] pattern was found in October {{year|2014}} by [[:Category:Patterns found by Michael Simkin|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|accessdate=February 21, 2018}}</ref> and a 3-glider synthesis of a [[clean]] [[switch engine]] was discovered in March {{year|2017}} by [[:Category:Patterns found by Luka Okanishi|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|accessdate=February 21, 2018}}</ref>
Along similar lines, a 3-glider synthesis of an [[infinite growth]] pattern 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|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|accessdate=February 21, 2018}}</ref>


==2-glider syntheses==
==2-glider syntheses==
Line 96: Line 102:
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 [[Polyomino#Octominoes|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]].
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 [[Polyomino#Octominoes|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 [[:Category:Patterns found by Jason Summers|Jason Summers]] on January 29, [[:Category:Patterns found in 2005|2005]].
All 71 such syntheses can be seen below in a pattern put together by [[Jason Summers]] on January 29, {{year|2005}}.


[[Image:2glidersyntheses.png|framed|center|All 71 distinct 2-glider collisions, arranged by what they synthesize.<br />'''Download [[RLE]]:''' [http://www.conwaylife.com/patterns/twoglidersyntheses.rle click here] ]]
[[Image:2glidersyntheses.png|framed|center|All 71 distinct 2-glider collisions, arranged by what they synthesize.<br />'''Download [[RLE]]:''' [http://www.conwaylife.com/patterns/twoglidersyntheses.rle click here] ]]


==See also==
==See also==
*[[:Category:Pattern_constructible_by_a_given_number_of_gliders|List of known glider syntheses]]
*[[:Category:Patterns_constructible_by_a_given_number_of_gliders|List of known glider syntheses]]
*[[Salvo]]
*[[Salvo]]
*[[Tutorials/Glider syntheses]]
*[[Shinjuku]]


==References==
==References==
<references />
<references>
<ref name="post82560">{{LinkForumThread
|format = ref
|title  = Re: 17 in 17: Efficient 17-bit synthesis project
|p      = 82560
|author = Tanner Jacobi
|date  = September 9, 2019
}}</ref>
</references>


==External links==
==External links==

Revision as of 23:03, 15 September 2019

x = 34, y = 31, rule = B3/S23 33bo$31b2o$32b2o$9bo$bo8bo$2bo5b3o$3o3$5bo$6bo$4b3o$24bobo$25b2o$25bo 2$27bobo$27b2o$28bo$31b3o$31bo$32bo7$5b2o$6b2o$5bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ ZOOM 8 ]]
An 8-glider synthesis of a loafer

(click above to open LifeViewer)
RLE: here Plaintext: here

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 35 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] A second, longer effort completed all the 18-bit still lifes in November 2014.[4] Later optimization projects reduced the maximum cost of construction for 15-bit,[5] 16-bit,[6] and 17-bit[7] still lifes to less than one glider per bit, in November 2016, May 2017, and September 2019 respectively.

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.

Name Speed First synthesis Best current synthesis
Date Discoverer Fewest gliders
60P5H2V0 2c/5 orthogonal 2003-03-17 Noam Elkies 61
loafer c/7 orthogonal 2013-02-17 Adam P. Goucher 8
dart c/3 orthogonal 2014-12-02 Martin Grant 25
crab c/4 diagonal 2014-12-26 Martin Grant 18
Parallel HBK (6,3)c/245912 2014-12-31 Michael Simkin 38,380
30P5H2V0 2c/5 orthogonal 2015-01-01 Martin Grant 65
25P3H1V0.1 c/3 orthogonal 2015-01-06 Martin Grant 47
x66 c/2 orthogonal 2015-01-11 Martin Grant 12
weekender 2c/7 orthogonal 2015-01-25 Martin Grant 79
puffership c/2 orthogonal 2015-02-11 Chris Cain 60
Gemini (2560,512)c/16849793 2015-02-16 Dave Greene 173,449
half-X66 with HWSS c/2 orthogonal 2015-03-08 Chris Cain 9
B29 c/4 diagonal 2015-04-06 Tanner Jacobi 25
Pushalong 1 c/2 orthogonal 2015-06-12 Martin Grant 58
30P4H2V0.4 c/2 orthogonal 2015-09-10 Tanner Jacobi 85
0hd Demonoid 65c/438852 diagonal 2015-12-06 Chris Cain 12,016
copperhead c/10 orthogonal 2016-03-05 Aidan F. Pierce 13
fireship c/10 orthogonal 2016-03-21 Nico Brown 18
25P3H1V0.2 c/3 orthogonal 2017-12-15 Martin Grant 26
Orthogonoid 16c/217251 orthogonal 2017-12-30 Dave Greene 37,625
2-engine Cordership c/12 diagonal 2017-12-31 Dave Greene 9
46P4H1V0 c/4 orthogonal 2019-02-04 Tanner Jacobi 88
spider c/5 orthogonal 2019-03-07 Martin Grant 537

Other syntheses of note

A 3-glider synthesis of a pentadecathlon.

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,[8] and a 3-glider synthesis of a clean switch engine was discovered in March 2017 by Luka Okanishi.[9]

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.
Download RLE: click here

See also

References

  1. Mark D. Niemiec. "Re: 4 glider syntheses". ConwayLife.com forums. Retrieved on February 21, 2018.
  2. Dave Greene. "Constructions Known for All Still Lifes up to 17 Bits". Game of Life News. Retrieved on September 17, 2014.
  3. Martin Grant. "17-bit SL Syntheses (100% Complete!)". ConwayLife.com forums. Retrieved on September 17, 2014.
  4. Martin Grant. "18-bit SL Syntheses (100% Complete!)". ConwayLife.com forums. Retrieved on February 21, 2018.
  5. BlinkerSpawn. "15 in 15: Efficient 15-bit Synthesis Project (DONE!)". ConwayLife.com forums. Retrieved on February 21, 2018.
  6. Bob Shemyakin. "16 in 16: Efficient 16-bit Synthesis Project". ConwayLife.com forums. Retrieved on February 21, 2018.
  7. Tanner Jacobi (September 9, 2019). Re: 17 in 17: Efficient 17-bit synthesis project (discussion thread) at the ConwayLife.com forums
  8. Michael Simkin. "Re: Making switch-engines". ConwayLife.com forums. Retrieved on February 21, 2018.
  9. Luka Okanishi. "Re: Thread For Your Accidental Discoveries". ConwayLife.com forums. Retrieved on February 21, 2018.

External links

Template:LinkWeisstein