Sorry to be coming to the party late. I only just found out this effort was going on. Great work, everybody!
From June 19:
calcyman wrote:Now all synthesisable still-lifes can be synthesized in less than 2 gliders per bit!...
Macbi wrote:All synthesisable strict still-lifes. We don't know that we can place every 8-bitter next to every 9-bitter in any orientation with only 34 gliders.
Synthesis of pseudo-still-lifes is usually much simpler than synthesizing still-lifes, because, in most cases, for an n-bit pseudo-still-life, all you need to do is create a stil-life of size at most n-4, and add another of size at most n/2 adjacent to it. All still-lifes up to 8 bits can be added fairly cheaply.
There are basically two situations that are more difficult: a large still-life that has a difficult-to-access bonding site (such as the cis-shillelagh), or pairs of still-lifes that are bonded along some other surface than domino-on-domino.
For all pseudo-still-lifes up to 16 bits, there are only 5 that cost >1 glider per bit: 23, 18, 25, 20, and 27 respectively (top row below); two in the first category, and three in the latter.
I never computed the exact costs for all the 17-bit ones, but all of those should cost no more than 1 glider/bit except ones in the above categories. I've manually examined all with non-standard bonding geometries, and even most of those come in at no more than one glider/bit, except five costing 23, 18, 18, 22, and 25 respectively (second row below). There are also three new geometries that first occur at 17 bits, but all of those are relatively easy to synthesize.
Of course, an exhaustive computer search should be performed to be sure, but I wouldn't expect any surprises.
Quasi-still-lifes are even easier to construct (if anyone cares). In most cases, one can simply construct each still-life separately, so if the pieces don't exceed 1 glider/bit, neither will the result. There are a few exceptions that can't be synthesized this way, typically when one piece doesn't have a suitable way of edge-shooting it (e.g. hook w/tail prongs first) or when adjacent pieces are separated by an empty diagonal but no clear orthogonal line. There are only one 15-bit one (28 gliders, 3rd line), four 16-bit ones (32, 17, 20, and 20 gliders, 4th line), and four 17-bit ones (36, 33, 31, and 46 gliders, 5th line) that exceed one glider/bit.
Code: Select all
x = 66, y = 69, rule = B3/S23
30bo$3boo13boo10b3o12boobo11boobo$bbobo12bobo13boboo9bob3o9boboo$bo14b
o15bo3bo8bo5bo12boo$o14bo5boo9boobo10b3obo10boobo$oboboboo7bobobobbo
13b3o9boboo9boobbo$booboobo8booboo17bo25boo10$3boo10boobooboo7booboo
10boobo11boobo$bbobo11bobo3bo8bobobboo8bob3o9boboo$bo14bobbobo9bobbobo
8bo5bo12boo$o6boo8boboboo9bobobbo8b3obobo8boobo$obobobobo9bo14bobboo
10boboo8bobobbo$booboo55bobboo10$oobboobo$o3boboo$bo$bbo$3bobo$4boo10$
oobboo12boo12bo13bo$o3bobobo8bobo11bobobbo8bobobbo$bo5boo7bo15bobbobo
8bobbobo$bbo12bo5boo13bo13bo$3bobo9boo5bo8bo15bo$4boo15bo8bobobbo10bob
obbo$18bobo10bobbobo10bobbobo$18boo15bo15bo8$oobboo9boo16boo10boo$o3bo
bo8bobboobboo8bobo11bo$bo5bobo6boobo3bo7bo5boo7boboobboo$bbo5boo12bo7b
o7bo8bobo3bo$3bobo15bo8boo5bo14bo$4boo12bobo15bo14bo$18boo13bobo12bobo
$33boo13boo!
