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.)

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 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:

`#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:

`#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.

## 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.

## 1 comment:

I just took xs17_gbaikoz1252 down to 10G by improving the cleanup.

Post a Comment