Miscellaneous topics in Conway's Game of Life -- unfinished projects of all kinds and conditions

11 July 2019

Less Than Two Gliders Per Cell, For All Constructible Still Lifes

On 19 June 2019 a surprising milestone was reached. Goldtiger997 made a final improvement to a 17-bit still-life synthesis -- ID xs17_03p6413z39c -- to bring the cost down to 33 gliders. (It's since been reduced further, to 29 gliders, and eventually down to only 9 gliders as part of the long-running "17-in-16" project.)

This made it possible to announce a surprising result: there's a strict upper bound for the cost in gliders for any strict still life, assuming it can be constructed by colliding gliders at all. If a glider-constructible still life contains N ON cells, then it can be constructed with less than 2N gliders.

A Mix of Theory and Practice

For still lifes larger than 17 bits, this result is supplied by the strange and wonderful RCT method. The RCT (reverse caber tosser) is a pattern that is constructible with only 35 gliders, that reads the very faraway position of an approaching object to produce a stream of bits, which are then interpreted as a construction recipe fed to a universal construction arm. Cleanup of the RCT's mechanism would also have to be done to produce a full synthesis, which makes it tricky to create these 35-glider recipes in practice; no working examples have yet been completed.

The situation is much more straightforward for still lifes with up to 17 ON cells. Extensive soup searches recorded by Catagolue, and related technical advances, have allowed much more efficient recipes to be found for a large number of still lifes. In fact, almost all still lifes up to 17 bits can now be constructed with fewer than 1 glider per ON cell, let alone 2 gliders per ON cell.

We've Come a Long Way, Conway

For example, just a few years ago the best known recipe for an 8x6 17-bit still life with ID xs17_gbaikoz1252 was around 73 gliders:

Code: Select all
#C Incremental 73-glider synthesis of xs17_gbaikoz1252.
#C Adapted from Mark Niemiec's database,
#C http://conwaylife.com/ref/mniemiec/17/17-1202.rle
x = 185, y = 236, rule = B3/S23
143bo$143bobo$143b2o$140bo$138bobo$139b2o2$143bo$141b2o$142b2o2$133bob
o15bo$133b2o15bo$96bo33bo3bo15b3o$91bo3bo15b2o15bobo10b2o$92b2ob3o12bo
2bo15b2o9bo2bo$91b2o17bo2bo26bo2bo9bo$10bo100b2o17bo10b2o9b2o$11b2obo
115b2o20bobo$10b2o2bobo112bobo34b2ob2o$14b2o12b2o18b2o18b2o18b2o18b2o
28b2o27bobobobo$27bo2bob2o13bo2bob2o13bo2bob2o13bo2bob2o13bo2bob2o23bo
2bob2o5b3o15bo2bob2o$23bo4bobobo15bobobo15bobobo15bobobo15bobobo25bobo
bo6bo18bobo$22b2o5b2obobo14b2obobo14b2obo16b2obo16b2obo26b2obo7bo18b2o
$22bobo8b2o18b2o17bob2o16bob2o16bob2o26bob2o$2b2o68bo2bo16bo2bo16bo2bo
26bo2bo$3b2o68b2o18b2o18b2o28b2o$2bo2$151b2o$151bobo$53bo97bo$50bo2bob
o$48bobo2b2o$49b2o6$50b3o$50bo$51bo11$19bo42bo$19bobo38b2o$19b2o40b2o$
94bo$95bo4bo$93b3o3bo$6b2ob2o15b2ob2o15b2ob2o15b2ob2o15b2ob2o8b3o4b2ob
2o4b2o9b2ob2o4b2o19b2ob2o4b2o$7bobobobo13bobobo15bobobo15bobobo15bobob
o15bobobo3bo11bobobo3bo21bobobo3bo$7bo2bob2o13bo2bobobo12bo2bobobo12bo
2bobo14bo2bobo14bo2bobo3bo10bo2bobo3bo20bo2bobo3bo$8bobo17bobo2b2o13bo
bo2b2o13bobobo15bobobo15bobobo4bo10bobobo4bo20bobobo4bo$9b2o12bo5b2o
18b2o18b2ob2o15b2ob2o5bo9b2ob2o2b2o11b2ob2o2b2o3bo17b2ob2o4bo$21b2o75b
2o40bo28bo$22b2o74bobo39b3o27bo$56bobo77b2o33bo$15b2o39b2o37b3o37bobo
32b2o$16b2ob3o35bo39bo39bo3b2o$15bo3bo76bo45b2o$20bo34b3o83bo$55bo$56b
o2$58b3o$58bo$59bo13$6b2ob2o4b2o29b2ob2o4b2o29b2ob2o4b2o29b2ob2o4b2o$
7bobobo3bo31bobobo3bo31bobobo3bo31bobobo3bo$7bo2bobo3bo30bo2bobo3bo30b
o2bobo3bo30bo2bobo3bo$8bobobo4bo30bobobo4bo30bobobo4bo30bobobo4bo$9b2o
b2o4bo30b2ob2o4bo30b2ob2o4bo30b2ob2o4bo$19bo39bo39bo39bo$20bo39bo39bo
39bo$21bo39bo39bo39bo$20b2o3bo36bo39bo39bo$24bo38bo39bo39bo$24b3o35b2o
38b2o3bo34b2o$20b2o84bo$19bobo84b3o$21bo3b2o75b2o$26b2o73bobo$25bo77bo
3b2o$108b2o$107bo10$59bo$59bobo$59b2o$54bo$54bobo$54b2o5bobo$61b2o$53b
o8bo55bo$54b2o60bobo$53b2o62b2o$120bo$61bo25bo19bo11bo17bo$60b2o23b3o
17b3o11b3o13b3o$6b2ob2o4b2o9b2ob2o4b2o9b2ob2o4b2o3bobo13b2ob2o3bo11b2o
b2o3bo21b2ob2o3bo$7bobobo3bo11bobobo3bo11bobobo3bo21bobobo3bo11bobobo
3bo10bobo8bobobo3bo6b3o$7bo2bobo3bo10bo2bobo3bo10bo2bobo3bo20bo2bobo3b
o10bo2bobo3bo10b2o8bo2bobo3bo4b3o$8bobobo4bo10bobobo4bo10bobobo4bo20bo
bobo4bo10bobobo4bo9bo10bobobo4bo$9b2ob2o4bo10b2ob2o4bo10b2ob2o4bo20b2o
b2o4bo10b2ob2o4bo20b2ob2o4bo$19bo19bo19bo29bo19bo29bo$20bo19bo19bo29bo
19bo29bo$21bo10b2o7bo10b2o7bo20b2o7bo10b2o7bo20b2o7bo$22bo9b2o8bo9b2o
8bo19b2o8bo9b2o8bo19b2o8bo$9b2o12bo19bo19bo29bo19bo29bo$6bo2bobo3b2o5b
2o8b2o8b2o8b2o8b2o18b2o8b2o8b2o8b2o18b2o8b2o$4bobo2bo4b2o16b2o18b2o28b
2o18b2o28b2o$5b2o9bo3$160bo$158b2o$159b2o4$143bobo$143b2o$144bo2$66bo$
67bo29bo29bo$65b3o28bobo27bobo$96bobo27bobo$62b3o32bo29bo$64bo$13bo49b
o$6bo5bo$7bo4b3o$5b3o$b3o$3bo126bo$2bo128bo$129b3o2$42bo29bo29bo29bo$
41bobo27bobo27bobo27bobo$42b2o28b2o28b2o28b2o3$169b2o$169bo$170b3o$17b
o29bo29bo29bo29bo34bo4bo$15b3o27b3o27b3o27b3o27b3o37b3o$6b2ob2o3bo21b
2ob2o3bo21b2ob2o3bo21b2ob2o3bo21b2ob2o3bo31b2ob2o3bo$7bobobo3bo6b3o12b
obobo3bo6b3o12bobobo3bo6b3o12bobobo3bo6b3o12bobobo3bo6b3o22bobobo3bo6b
3o$7bo2bobo3bo4b3o13bo2bobo3bo4b3o13bo2bobo3bo4b3o13bo2bobo3bo4b3o13bo
2bobo3bo4b3o23bo2bobo3bo4b3o$8bobobo4bo20bobobo4bo20bobobo4bo20bobobo
4bo20bobobo4bo30bobobo4bo$9b2ob2o4bo20b2ob2o4bo20b2ob2o4bo20b2ob2o4bo
20b2ob2o4bo30b2ob2o4bo$19bo29bo29bo29bo29bo39bo$20bo29bo29bo29bo29bo
39bo$12b2o7bo20b2o7bo20b2o7bo20b2o7bo20b2o7bo30b2o7bo$12b2o8bo19b2o8bo
19b2o8bo19b2o8bo19b2o8bo29b2o8bo$23bo29bo29bo29bo29bo39bo$12b2o8b2o18b
2o8b2o18b2o8b2o18b2o8b2o18b2o8b2o28b2o8b2o$12b2o28b2o28b2o28b2o28b2o
38b2o6$102bo$101bo$101b3o9$79bo$77b2o10bo$78b2o7b2o$88b2o$92bo$92bobo$
92b2o$5bo3b2o28b2o38b2o65bo$3bobo3bo25b2o2bo28b3o4b2o2bo15bo49bo$4b2o
4b3o22b2o3b3o27bo4b2o3b3o12bobo47b3o$b2o9bo4bo24bo4bo21bo12bo4bo7b2o$o
bo12b3o27b3o37b3o32b2o18b2o6b2o10b2o$2bo3b2ob2o3bo21b2ob2o3bo31b2ob2o
3bo31b2obo2bo13b2obo2bo5bobo5b2obo2bo$7bobobo3bo6b3o12bobobo3bo6b3o11b
3o8bobobo3bo6b3o22bobobobo13bobobobo4bo8bobobobo$7bo2bobo3bo4b3o13bo2b
obo3bo4b3o14bo8bo2bobo3bo4b3o23bo2bob2o13bo2bob2o13bo2bobo$8bobobo4bo
20bobobo4bo19bo10bobobo4bo30bobo17bobo17bobo$9b2ob2o4bo20b2ob2o4bo30b
2ob2o4bo30b2o18b2o18b2o$19bo29bo39bo$20bo29bo39bo$12b2o7bo20b2o7bo30b
2o7bo7bo$12b2o8bo19b2o8bo29b2o8bo6bobo$23bo29bo39bo5b2o$12b2o8b2o18b2o
8b2o28b2o8b2o$12b2o28b2o38b2o$97b2o3bo$88bo9b2obo$77bo10b2o7bo3b3o$77b
2o8bobo$76bobo!

#C [[ AUTOSTART X 137 Y 3 Z 2 PAUSE 2 GPS 25 LOOP 150 ]]

Thanks to soup search data from Catagolue, that same still life can now be constructed with just 10 gliders:

Code: Select all
#C 10-glider continuous synthesis of xs17_gbaikoz1252
#C http://catagolue.appspot.com/object?apgcode=xs17_gbaikoz1252&rule=b3s23
x = 30, y = 37, rule = B3/S23
3bo$4bo$2b3o4$13bo$12bo$12b3o3$2bo24bo$obo24bobo$b2o24b2o11$15bo$14bo
$4bo5bo3b3o8bo$4b2o4b2o12b2o$3bobo3bobo12bobo6$11bo8b2o$11b2o6b2o$10b
obo8bo!
#C [[ AUTOSTART PAUSE 2 GPS 25 T 150 X -5 Y 10 Z 12 PAUSE 2 LOOP 151 ]]

At the time of writing (mid-July 2019), there are still several dozen 17-bit still lifes that cost 1 glider per bit or more to synthesize -- but that number has been dropping quickly. All smaller still lifes have been below this limit for some time now, as described here.

UPDATE 9/9/2019: Construction recipes with 16 gliders or fewer have now been found for all 17-bit still lifes.

Some Related Open Questions

It is technically possible that all constructible still lifes have recipes with fewer gliders than the number of ON cells. However, the number of distinct still lifes increases rapidly as the number of bits increases, and the number of unsolved still lifes in the 20-cell to 34-cell range is far too large to manage with current construction methods. The number of strict 34-bit still lifes has not even been calculated yet, but it should be quite close to 35 billion, and it will include a large number of objects that are difficult to construct because they are so delicately balanced.

Notice for example that quad pseudo is 34 bits. It's technically a pseudo still life, not a strict one -- but just barely, since it can't be subdivided into two stable subpatterns, or even three. This kind of interdependence between different parts of an object becomes more common as the number of bits increases, and a larger area is out of reach of influence by colliding gliders around the object's perimeter. It seems possible that some object along these lines will turn out to be too delicately balanced, and it will be impossible to meet the less-than-one-glider-per-bit requirement.

It's also possible that some still life will have so many mutually supporting parts that it's impossible to find any glider construction at all, no matter how expensive. However, experience so far seems to indicate that if a non-glider-constructible still life exists, it will be significantly larger than 34 bits.