Conway's Life: Work in Progress

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

16 June 2018

Fixed Cost Glider Construction, Part II

Design Summary for Fixed-Cost Glider Construction

The previous post summarized the new 329-glider reverse caber tosser universal constructor design, but didn't go into detail about what exactly makes the design universal. Here are (most of) the fiddly details.

The idea of a fixed-cost glider recipe for any possible glider-constructible object has gone through several iterations in the past few years. The first completed construction was a decoder that used a double sliding-block memory, and repeatedly divided the stored number by two or three, returning the remainder for each cycle. That information could then be used to run a construction arm, but an explicit construction arm was never created for that design.

A newer "reverse caber tosser" design is an alternate storage mechanism for data feeding a universal constructor. The reverse caber tosser was designed by Adam P. Goucher, with Martin Grant finding the key glider-reflection reaction. A very large integer can be encoded in the position of a very faraway Cordership (instead of a block). If the distance to the Cordership is measured using circuitry designed to be as simple as possible, a complete decoder and universal constructor can be created by colliding exactly 329 gliders.

Normally a construction arm has at least four possible "elbow operations": PULL and PUSH to change the location of the elbow, and two different FIRE recipes to produce either of the two possible glider colors.

The first simplification for the reverse caber tosser is the use of only one color of output glider. This limits the output to monochromatic single-parity slow salvos (see below) but significantly simplifies the circuitry.

Usually FIRE operations also leave an elbow behind for the next elbow operation to make use of. The second simplification in the decoder design is to use up an elbow with every FIRE operation.

This makes construction recipes very much less efficient, because each new output glider needs a fresh elbow block to be pulled in from "elbow storage" (a line of blocks created by a block-laying switch engine) before the DFIRE (destructive fire) operation can be sent. As the number of output gliders increases, the pull distance increases proportionally, making the recipe progressively less efficient.

However, once again in this case, using up elbows makes the decoder mechanism significantly simpler, and that's the only kind of efficiency that matters from the point of view of reducing the total 329-glider construction cost. The PULL and DFIRE combined salvo needs only three synchronized gliders. It appears that including an elbow-preserving FIRE option would require four gliders or more, with a correspondingly larger amount of circuitry that would then have to be constructed by the initial glider recipe.

Summary of required parts and mechanisms

  • The glider recipe builds the decoder/constructor plus a very faraway Cordership.
  • The recipe also builds a block-laying switch engine as a source of elbow blocks for the constructor arm.
  • Two gliders are sent toward the Cordership.
  • When they reach the Cordership, they are reflected 180 degrees and head back toward the decoder.
  • The two return gliders may reach the decoder at two possible timings (mod 256). Let's call these two timings "PULL" and "DFIRE".
  • Changing the position of the Cordership allows a free choice of "PULL" or "DFIRE" timings, for each of N sets of return gliders.
  • Adding another bit to the data stored in the Cordership's position requires increasing the Cordership's distance from the decoder by roughly a factor of two.
  • The return gliders always interrupt a suppressing glider stream, allowing a construction-arm shotgun to send a two-glider salvo southeast to the block-laying switch engine.
  • The two-glider salvo is the same one used in many previous construction arms including the Gemini spaceship.
  • When the salvo strikes a block -- an "elbow" of the construction arm -- the block moves forward by one diagonal.
  • If the gliders have the "DFIRE" timing, a third glider is also released, which destroys the elbow block but releases a sideways glider.
  • Because the block is used up, this is a "destructive FIRE" elbow operation, instead of the more normal "FIRE" which preserves the elbow.
  • "PULL" and "DFIRE" operations, when combined with an unlimited supply of elbow blocks, allow a series of same-color gliders to be released successively on any set of chosen lanes.
  • The gliders will all have the same phase, so this is a "monochromatic single-parity slow salvo".
  • It has been shown that monochromatic monoparity slow salvos are capable of constructing any pattern that can be constructed by colliding gliders together.

The Cordership eventually generates its last bit and comes to a crashing halt. In the sample pattern shown in the previous post, the block that the Cordership crashes into is generated by two loafers, to make it clear that this block is a placeholder, not an official part of the initial glider construction! In the actual construction process, that block would be built by the construction arm, according to PULL and DFIRE instructions coming from the Cordership.

The construction arm also has to build a number of other "maintenance mechanisms":

  • a large structure made up of one-time glider splitters and glider turners, with four parts:
    1. a one-time circuit producing two gliders that stop the receding block-laying switch engine without releasing any gliders
    2. a one-time circuit producing a slow salvo of many gliders aimed at the ash from the stopped switch engine, rebuilding it into a clean one-time-use specialized Cordership eater
    3. a one-time circuit producing a specialized Cordership able to remove unused blocks from the block-laying switch engine's ash trail
    4. a one-time circuit producing a "meteor shower" slow salvo that completely cleans up the entire decoder/constructor mechanism.
  • a secondary "slow elbow" block at a safe distance from the construction arm (generated by colliding a series of monochromatic gliders into some of the block-laying switch engine's leftover ash).
  • a "hand block" to provide the construction arm with a usable target for incremental constructions

All of the above are necessary only if the pattern must be built with the absolute minimum of 329 gliders. If a larger number of gliders is allowed, on the rough order of 1000, then all this cleanup can be accomplished by adding gliders to the initial recipe instead. The resulting complete pattern would be many orders of magnitude smaller, though still very large. It might include several hundred more gliders in the initial recipe, but would be considerably more efficient at completing constructions.

For example, a more expensive Cordership-based block puffer could be constructed, and then could be shot down with gliders after it has produced exactly the right number of blocks. This would completely avoid any need to build the complex structures outlined in #1 through #3 above.

Similarly, building the "slow elbow" block as part of the construction recipe would cost only one or two gliders more than the minimum 329, but would reduce the size of the final pattern by a hundred or more orders of magnitude. That's not just a reduction by a factor of a hundred -- it's a factor of a googol, 10^100, and that's just a bare-minimum estimate. An even larger size reduction would result from adding two gliders to build the block that stops the incoming Cordership (the one built by loafers in the sample pattern).

When the constructor is in operation, it builds a series of one-time turners. The recipes are all monochromatic slow salvos. The purpose of the one-time turners is to to aim gliders at the hand block. These one-time turners fall into one of four categories, since they may change the parity and/or the color of the output glider relative to the input glider. This allows the "slow elbow" to convert a monochromatic single-parity slow salvo into a standard "P2 slow" salvo where the gliders may be either parity and either color.

13 June 2018

The Meaning of Life is 42 -- But the Cost of Living is Capped at 329

Code: Select all
#C universal constructor based on reverse caber tosser
#C Completed 10 June 2018
#C Original design by Adam P. Goucher
#C Original glider synthesis by Goldtiger997
x = 5379, y = 5173, rule = B3/S23
bo$2bo361bo$3o360bo$363b3o16$36bo$34bobo$35b2o$355bo$354bo$354b3o14$
29bo$30bo$28b3o2$335bo$335bobo$335b2o37$92bobo$93b2o$93bo2$356bo$72bo
283bobo$73b2o281b2o$72b2o2$337bo$336bo$336b3o891$1177bo$1178b2o$1177b
2o197$2925bo3b2o2bo$2925b2o3bo2bo$2926bo3bobo$2925bo5bo2$2926b2o$2925b
o2bo$2925bobo$2926bo65$1275bo$1276bo$1274b3o6$1265bo$1266b2o$1265b2o
15$1278bo$1279b2o$1278b2o$1291bo$1289bobo$1290b2o6$1287bobo$1277bobo8b
2o$1278b2o8bo$1278bo295$4459bo$4458bo$4458b3o$1848bo$1849bo$1847b3o14b
o$1865b2o$1864b2o$1717bo$1718b2o$1717b2o2$1865bobo2600bobo$1866b2o
2600b2o$1725bo140bo2602bo$1726bo$1724b3o11$1732bobo$1733b2o$1733bo13$
1749bo$1750b2o$1749b2o2$1761bobo$1762b2o$1762bo16$1765bobo$1766b2o$
1766bo4$1774bo$1772bobo$1773b2o23$1854bo$1855bo$1853b3o6$1794bo$1795b
2o$1794b2o32$1838bo$1839bo$1837b3o2$1851bo$1849bobo$1850b2o138$4513bob
o$4513b2o$4514bo4$4506bo$4506bobo$4506b2o38$1876bo2193bo$1874bobo2192b
o$1875b2o2192b3o412bo$4482b2o$4483b2o4$4063bobo$4063b2o$4064bo$2237bo$
2235bobo16bo$2236b2o17bo$2246bo6b3o$2247bo$2238bo6b3o$2239bo$2237b3o
23$4444bobo$4444b2o$4435bobo7bo$4435b2o$1822bo2613bo$1820bobo$1821b2o
2626bobo$4449b2o$4450bo13$1843bo$1844b2o$1843b2o466bo$2312b2o$2311b2o
4$1828bobo$1829b2o$1829bo$4095bo$4093b2o$4088bobo3b2o$4088b2o$1838bo
2250bo$1839b2o$1838b2o473bobo$2314b2o$2314bo2$4090bobo$4090b2o$4091bo
3$2222bo97bo$2223bo97bo$2221b3o95b3o$4092bobo$2234bobo1855b2o$2235b2o
1856bo$2235bo4$4069bo$4069bobo$4069b2o$2246bo$2247b2o$2246b2o2$4073bob
o$4073b2o$4074bo$4052bo$4050b2o$4051b2o5$4070bo13bo$2265bo1804bobo10bo
$2266b2o1802b2o11b3o$2265b2o6$2267bobo$2268b2o$2268bo4$2276bo$2266bo
10bo$2267bo7b3o$2265b3o55$2202bo$2203b2o$2202b2o$2215bo$2213bobo$2214b
2o6$2211bobo$2201bobo8b2o$2202b2o8bo$2202bo36$4205bo$4205bobo$4205b2o
4$4210bo$4209bo$4209b3o38$4154bobo$4154b2o$4155bo$4162bo$4162bobo$
4162b2o2$4153bo$4151b2o$2105bo2046b2o$2106bo$2104b3o11$4137bo$4137bobo
$4137b2o3$2103bobo$2104b2o$2104bo2040bo$4145bobo$4145b2o12$4122bo$
4121bo$4121b3o2$4117bo$4116bo$4116b3o$2123bobo$2124b2o$2124bo2001bo$
4126bobo$4126b2o16$2386bobo$2387b2o$2387bo13$3880bo$3879bo$3879b3o6$
3873bobo$3873b2o$3874bo$2493bo$2491bobo$2335bo156b2o$2336bo$2334b3o$
3861bo$2339bo1521bobo$2337bobo1521b2o$2338b2o$2484bo$2485b2o$2484b2o$
2355bo$2356bo$2354b3o14bo16bobo$2372b2o15b2o1441bo$2371b2o16bo1441bo$
3831b3o$2374bobo1467bo$2375b2o1467bobo$2375bo30bo1437b2o$2407b2o$2401b
o4b2o$2402bo$2400b3o18bo$2364bo57b2o$2365b2o54b2o$2364b2o2$3832bo$
3832bobo$3832b2o3$2311bo96bobo1455bo5bo$2312bo96b2o1454bo4b2o$2310b3o
96bo1455b3o3b2o2$2413bo$2326bobo85bo$2327b2o83b3o$2327bo3$2336bo$2337b
2o$2336b2o$2412bo1443bobo$2410bobo1443b2o$2411b2o1444bo4$2409bo$2407bo
bo$2408b2o5$2414bo$2415b2o$2414b2o$3887bo$3886bo$3869bo16b3o$3869bobo$
3869b2o7bo$3876b2o$3877b2o7bo$3884b2o$3885b2o62$3795bo$3793b2o$3794b2o
3$3798bobo$3798b2o$3799bo2$2145bo$2146bo$2144b3o4$3794bo$3794bobo$
3794b2o2$3789bo$3789bobo$2153bo1635b2o$2154b2o$2153b2o1644bo$3798bo$
3798b3o83$2750bo$2751bo$2742bo6b3o$2743bo$2734bo6b3o$2735bo$2733b3o35$
4006bo$4004b2o$4005b2o6$4008bo$4006b2o$4007b2o11$2572bo$2573bo$2571b3o
2$2577bo2216bo$2578bo2214bo$2576b3o2214b3o$3995bobo$2573bo1421b2o$
2568bo5b2o1420bo$2566bobo4b2o$2567b2o$3988bo$3987bo$3987b3o25$2856bobo
$2857b2o$2857bo2$2852bo$2853b2o$2852b2o3$3693bo$3693bobo$3693b2o3$
2857bo$2858bo$2856b3o2$2862bo$2863bo$2861b3o$3684bobo$3684b2o$2853bo
831bo$2851bobo$2852b2o128$3522bo$3521bo$3521b3o4$2581bo$2582bo$2580b3o
$2556bo$2557bo$2555b3o4$2580bo1181bobo$2559bo18bobo1181b2o$2557bobo19b
2o1182bo$2558b2o$2569bobo$2570b2o$2570bo212bobo$2784b2o$2784bo2$2779bo
$2780b2o$2779b2o3$4144bo$4144bobo$4144b2o11$2591bo$2589bobo$2590b2o5$
2601bo$2602b2o1187bo4bobo$2601b2o1188bobo2b2o$3791b2o4bo44$3441bo$
3441bobo$2629bo811b2o$2630b2o$2629b2o104$2797bo$2798bo$2796b3o4$2796bo
bo$2797b2o809bobo$2797bo810b2o8bo$3609bo6b2o$3617b2o21$3571bo$2759bo
811bobo$2760bo810b2o$2758b3o25$2767bo$2768bo$2766b3o41$3056bo$3054bobo
$3055b2o2$3061bo$3059bobo$3060b2o803bo$3863b2o$3051bo812b2o$3052bo$
3050b3o68$3774bo17bo$3772b2o17bo$3773b2o16b3o3$3781bobo12bo$3781b2o13b
obo$3782bo13b2o3$3777bobo$3777b2o$3778bo174$2677b2o$2676bobo$2678bo
813bo$3491b2o$3491bobo66$2747b2o$2748b2o$2747bo4$2737b3o$2739bo$2738bo
40$3692bo$3678b2o11b2o$3677b2o12bobo$3679bo266$2251b2o$2252b2o$2251bo
146b2o$2399b2o$2398bo2$2241b3o$2243bo135b3o12b2o$2227b2o13bo138bo13b2o
$2226bobo151bo13bo$2228bo$2384b2o17bo$2383bobo17b2o$2385bo16bobo$2227b
2o$2226bobo323b2o$2228bo194b3o127b2o1345bo$2425bo126bo1346b2o$2424bo
1474bobo2$4097b2o$2545b2o1550bobo$2544bobo21bo1528bo$2546bo21b2o$2567b
obo1322bo$3891b2o$2369b2o1520bobo211bo$2368bobo1733b2o$2370bo1733bobo
12$2372bo$2372b2o$2371bobo5$2343bo$2343b2o14bo$2342bobo14b2o5b3o$2358b
obo7bo$2367bo4$2344b2o$2343bobo$2345bo$3857b2o189b3o$3857bobo188bo$
3857bo191bo$3608b3o$2284bo511b2o810bo$2284b2o509bobo811bo$2283bobo511b
o$4076b3o$4076bo$2293b2o1782bo$2294b2o$2293bo2$2288b2o$2289b2o1562b2o$
2288bo1563b2o$3854bo$3857bo$3856b2o228bo$3856bobo13bo212b2o$3871b2o
212bobo$2271b2o1598bobo$2260b3o9b2o$2262bo8bo12b2o$2261bo21bobo$2285bo
1595b2o$3880b2o$2750b2o1130bo$2288b3o460b2o6bo1135b3o$2290bo459bo8b2o
810bo323bo$2289bo468bobo809b2o324bo$3570bobo$4082bo$4081b2o$4081bobo$
2272b3o1295b3o$2274bo1295bo$2273bo1297bo2$2262b2o$2263b2o$2262bo60bo$
2270b2o51b2o$2269bobo50bobo6bo$2271bo59b2o$2330bobo$2338b3o$2340bo$
2339bo$2319b3o$2321bo$2320bo$2769bo1072b2o$2769b2o1070b2o$2768bobo
1072bo5$3848b2o$3848bobo$3848bo28$2207b3o$2209bo$2208bo4$2212b2o$2211b
obo$2213bo3$3858bo$3857b2o$3857bobo85$2573bo4b2o$2573b2o2bobo1184b2o$
2572bobo4bo1183b2o$3765bo6$2952b3o$2954bo$2953bo4$3775b2o$3775bobo$
3775bo5$2953b2o$2952bobo$2954bo832b2o$3786b2o214b2o$3788bo213bobo$
4002bo3$2587b3o$2589bo1416bo$2588bo1416b2o$4005bobo2$4015b2o$4014b2o$
4016bo$4012bo$4011b2o$2603bo1186b2o219bobo$2603b2o1185bobo$2602bobo
1185bo7$3788b3o$3788bo$3789bo40$2146b2o12bo$2147b2o11b2o$2146bo12bobo
73$4216bo$4206bo8b2o$4205b2o8bobo$4205bobo6$4203b2o$4203bobo$4203bo$
4215b2o$4214b2o$4216bo4$4143bo$4142b2o$4142bobo35$1848b2o$1847bobo$
1849bo15$4151b2o$4141b2o7b2o$4140b2o10bo$4142bo2$4132bo$1849b2o2280b2o
$1850b2o2279bobo$1849bo2$2109b3o18b2o$2111bo19b2o$2110bo19bo4$4156b3o$
4156bo$4157bo3$2105b3o$1760bo346bo$1760b2o344bo2052b2o$1759bobo2397bob
o$4159bo21$1728bo$1728b2o46b2o$1727bobo47b2o$1776bo5$1737b2o$1736bobo$
1738bo2660b2o$4398b2o$4400bo10$1791b2o$1790bobo$1792bo4$1784bo$1784b2o
$1783bobo156$4503b2o$4502b2o$4504bo7$1912b2o$1913b2o$1912bo40$1863b3o$
1865bo$1864bo$4428b2o$1864bo2562b2o$1864b2o2563bo$1863bobo2$1855b3o$
1857bo2571b2o$1856bo2572bobo$4418b3o8bo$4418bo$4419bo38$4460b2o$4440b
2o18bobo$4440bobo17bo$4440bo3$4453bo$4452b2o$4452bobo14$1824b2o$1823bo
bo$1825bo2621bo$4446b2o$4446bobo3$1832bo$1832b2o$1831bobo2$1825b2o$
1824bobo$1826bo2609bo$4435b2o24b3o$4435bobo23bo$4462bo2$1843b2o$1842bo
bo$1844bo4$1836b2o$1835bobo$1837bo$1825b3o$1827bo$1826bo$4428b3o$4428b
o$4429bo5$1840b3o$1842bo$1841bo$4443b3o$4443bo$4444bo25$2711b2o218b3o$
2712b2o217b3o$2711bo218bo2$2933b2o1833b2o$2926b3o3bo1835bobo$2925bob2o
4b2o1833bo$2925bo6bo$2926bobobo$1903b2o$1904b2o$1903bo2$4362b2o$4362bo
bo$4362bo5$1940b2o$1939bobo$1941bo7$1935b2o$1934bobo$1936bo$1920b2o$
1921b2o$1920bo2489b2o$4409b2o$4411bo385bo$4796b2o$4796bobo6$1917b3o$
1919bo$1911b2o5bo$1910bobo$1912bo$4403bo$4402b2o$4402bobo6$4408b3o125b
2o$4408bo127bobo$4409bo126bo47$2641b2o$2640bobo$2642bo29$1359b3o$1361b
o$1360bo11$4614b2o$4614bobo$4614bo49$1295b3o$1297bo$1296bo3$1270b2o$
1271b2o$1270bo$1283b3o$1285bo$1284bo4$1288b2o$1287bobo$1289bo$1262b2o$
1261bobo$1263bo4$1255bo$1255b2o$1254bobo289$5377b2o$5376b2o$5378bo!
#C [[ WIDTH 592 HEIGHT 500 X 5 Y -60 PAUSE 2 AUTOSTART ]]
#C [[ T 800 STEP 5 ]]
#C [[ T 2500 GPS 60 X 410 Y 456 Z 2 ]]
#C [[ T 2600 STEP 4 ]]
#C [[ T 2700 STEP 3 ]]
#C [[ T 2800 STEP 2 ]]
#C [[ T 2900 STEP 1 ]]
#C [[ T 3000 STEP 2 ]]
#C [[ T 3100 STEP 3 ]]
#C [[ T 3200 STEP 4 ]]
#C [[ T 3300 STEP 5 ]]
#C [[ T 7850 GPS 60 STEP 50 X 555 Y 628 Z -1.5 ]]
#C [[ T 28000 X 225 Y 300 Z -4 ]]
#C [[ PAUSE 5 LOOP 28050 ]]

There has been speculation for at least a couple of years** about the simplest possible form of universal constructor, where an arbitrarily complex construction recipe is encoded in the position of a single faraway object. The position of the object is measured by the simplest possible decoder mechanism, resulting in a series of bits that can then be interpreted to produce a slow salvo.

It has already been shown that slow salvos can construct any pattern that is constructible by gliders. So with the correct placement of the faraway object, the complete pattern is capable of building any possible glider-constructible pattern of any size. The same pattern is also capable of building a self-destruct mechanism that completely removes all trace of the universal constructor, after its work is done -- leaving only the constructed pattern and nothing else. A counterintuitive consequence is that any glider-constructible object, no matter what size, can be built with a specific fixed number of gliders.

And now the actual number has been calculated, and it's surprisingly small: the current upper limit is 329 gliders. This may be reduced somewhat if a more efficient universal constructor is designed or an improved synthesis is found.

Watch this space for a full summary of the tasks that the universal constructor has to accomplish to be enable this 329-glider recipe to to construct any arbitrary pattern.

** It seems likely that someone came up with this idea long before 2015 -- i.e., the inevitability of a fixed-cost construction with N gliders, for any possible glider-constructible object. Really it's more or less implied by the sliding-block memory units described in Winning Ways. But I don't know of anywhere that the fixed upper-limit cost of construction was mentioned explicitly. It would be interesting to see what early estimates of that upper limit might have been... it seems likely they were significantly higher than three digits!

10 March 2018

It Happened One Knight

On 6 March 2018 the first member of a new class of Conway's Life spaceships was discovered. This is Sir Robin, the first elementary spaceship that travels in an oblique direction. Its displacement is two cells horizontally and one cell vertically (or vice versa) every six generations, which is the fastest possible knightship speed. The name is a reference to Monty Python's "Brave Sir Robin", who bravely runs away as fast as possible.

Code: Select all
#C (2,1)c/6 knightship found by Adam P. Goucher,
#C based on a front end originally found by Josh Ball,
#C rediscovered and extended by Tomas Rokicki,
#C using a SAT solver-based search
x = 79, y = 31, rule = B3/S23
8bo$6bo2bo$4b2obo3bo$4bo2bo3bo$3o2bobo$o4bobobo$3bo2bo3bo$bobo6bo$2b2o
6bo2$4b2ob2o4bob4o11bo$4b2ob2ob2ob3o2b2obob2o4bobo$4b2o4bo3bobobo6b2o$
4b3o5bo4bobo6bob2o2b2o$6bo7bo5bo5bob3obo$6b2o2bobob4ob2o3bo3b2o2b2o$
11b2obobo10bo3b3o22bo$17bo2bo6bob3obo24bo$13b3o5bo3bo2bo3b2o9bo8b3o3bo
$18b4o3bo5bo2bo4bob2obo5b3o5bo$21bo3bo5bo3b2o2b2o3b2o3b2ob2obobo$23bob
o5bo4b2obo5bob2obo2bo2b2o6bobo$24b2o11bo2bo4b2obobob2o2b2o5b2o2bo2b2o$
32b2obobo3b2o2b2o3bob2o2b2o5b2o2bo2b3o$32b2obobo4bobo3bo2b3o2bob2obo3b
2obob4o3bo$37b2o4bo13bo4bo2b3o5b3obo$38bobo4bo11bobo2bo3bob2o4bo3bo$
41bobo2bo14b2o6bo3bo$39b2o2b2o15b2o3b3o4b2o$43b3o18bo3bob3o$65b2obo3bo!
#C [[ GRID THEME 7 TRACKLOOP 6 -1/3 -1/6 THUMBSIZE 2 HEIGHT 480 ZOOM 7 GPS 12 AUTOSTART ]]

The new knightship was found by Adam P. Goucher based on initial results by Tom Rokicki, after about a month of automated searching. The program that completed the knightship was icpx, a "multithreaded hybrid of LLS and gfind".

A detailed summary of the discovery process is now available.

15 October 2016

14-, 15-, and 16-bit still life syntheses

A week or so ago, a better recipe was found for the last still life on Mark Niemiec's list of expensive 14-bit syntheses. Now all 14-bit still lifes can be constructed with less than 14 gliders -- less than 1 glider per bit, as the old saying goes.

Catagolue results continue to be very useful in finding new recipes.


Code: Select all
#C 12-glider synthesis for the last 14-bit still life,
#C snake bridge snake / 12.105, which had previously cost at least
#C one glider per bit.
#C Goldtiger997, 6 October 2016, optimized by Mark Niemiec on 7 October.
x = 79, y = 71, rule = LifeHistory
7.A$.A6.A$2.A3.3A$3A2$16.A$14.A.A$15.2A6$36.A$34.A.A$35.2A8$30.3A$32.
A$31.A4$31.3A$33.A11.2D.D$32.A12.D.2D$43.2D$39.2D.D$39.D.2D6$52.A$51.
2A$20.2A5.3A21.A.A$21.2A6.A$20.A7.A22$3.3A$5.A70.2A$4.A4.2A65.A.A$10.
2A64.A$9.A!
#C [[ AUTOFIT AUTOSTART GPS 25 LOOP 150 ]]

UPDATE: The next challenge along these lines was to similarly reduce 15-bit still life costs to below 1 glider per bit. The process started later in the same forum thread, and was completed on November 19, 2016, with the following 14-glider synthesis:

Code: Select all
#C 14-glider synthesis for the last 15-bit still life
#C which had previously cost at least one glider per bit.
#C Extrementhusiast, 19 November 2016
x = 48, y = 38, rule = B3/S23
17bobo$17b2o$18bo$4bobo$5b2o$5bo$18bo$18bobo$18b2o2$obo$b2o39b2o$bo40b
o3b2o$20b3o21bo2bo$20bo22b2obo$21bo6bo16bo$8b2o18bobo14bobo$7bobo18b2o
16b2o$9bo2$5b2o$4bobo$6bo9b2o$10b2o3bobo$11b2o4bo$10bo4$8b3o$7bo2bo$
10bo$6bo3bo$10bo$7bobo$32b3o$32bo$33bo!
#C [[ AUTOFIT AUTOSTART GPS 25 LOOP 150 ]]

UPDATE 2: The next project involved a similar reduction for 16-bit still life recipes. The official project kickoff was on December 16, 2016, when 443 of the 3,286 16-bit still lifes had no synthesis in less than 16 gliders in Chris Cain's database. It concluded successfully on May 24, 2017.

12 June 2016

New spaceship speed: 3c/7

Tim Coe has found a symmetrical spaceship with a new speed, 3c/7 (left, below) after a series of searches that took a total of "one or two months". At 29 cells wide, it is the minimum width odd symmetric spaceship -- an exhaustive width 27 search was run some time ago by Paul Tooke. The author seems to have officially chosen a name of "Spaghetti Monster" for the new 3c/7 spaceship.

Matthias Merzenich has pointed out that two of these spaceships can support a known 3c/7 wave (right, below).


Code: Select all
#C 3c/7 FSM spaceship: Tim Coe, 11 June 2016
#C Period-28 3c/7 wave found by Stephen Silver on Feb. 2, 2000
x = 187, y = 139, rule = B3/S23
10bo7bo65bo7bo$8b2ob2o3b2ob2o61b2ob2o3b2ob2o$8b2ob2o3b2ob2o61b2ob2o3b
2ob2o73bo7bo$11b2o3b2o67b2o3b2o74b2ob2o3b2ob2o$7bo5b3o5bo59bo5b3o5bo
70b2ob2o3b2ob2o$7bo13bo59bo13bo73b2o3b2o$8bo11bo61bo11bo70bo5b3o5bo$9b
2o7b2o63b2o7b2o71bo13bo$6bobobobo3bobobobo57bobobobo3bobobobo69bo11bo$
6bobob2o5b2obobo57bobob2o5b2obobo70b2o7b2o$6bobo11bobo57bobo11bobo67bo
bobobo3bobobobo$164bobob2o5b2obobo$11bo5bo67bo5bo72bobo11bobo$10b2o5b
2o65b2o5b2o$8b2o9b2o61b2o9b2o74bo5bo$8bo3bo3bo3bo61bo3bo3bo3bo73b2o5b
2o$10bo2bobo2bo65bo2bobo2bo73b2o9b2o$10bobo3bobo65bobo3bobo73bo3bo3bo
3bo$9bo9bo63bo9bo74bo2bobo2bo$7bo3bo5bo3bo59bo3bo5bo3bo72bobo3bobo$6b
4o9b4o57b4o9b4o70bo9bo$4b2obo2bo7bo2bob2o53b2obo2bo7bo2bob2o66bo3bo5bo
3bo$4b2o2b3o7b3o2b2o53b2o2b3o7b3o2b2o65b4o9b4o$7bobo2bo3bo2bobo59bobo
2bo3bo2bobo66b2obo2bo7bo2bob2o$5bob3o2bo3bo2b3obo55bob3o2bo3bo2b3obo
64b2o2b3o7b3o2b2o$5bo4bo7bo4bo55bo4bo7bo4bo67bobo2bo3bo2bobo$163bob3o
2bo3bo2b3obo$6bo15bo57bo15bo66bo4bo7bo4bo$6b2obo9bob2o57b2obo9bob2o$5b
o3b2o7b2o3bo55bo3b2o7b2o3bo66bo15bo$164b2obo9bob2o$5b2o4bo5bo4b2o55b2o
4bo5bo4b2o65bo3b2o7b2o3bo2$8b2ob2o3b2ob2o61b2ob2o3b2ob2o68b2o4bo5bo4b
2o$2bo5b2o3bobo3b2o5bo49bo5b2o3bobo3b2o5bo$bob2o5bobo3bobo5b2obo47bob
2o5bobo3bobo5b2obo64b2ob2o3b2ob2o$2o2bo3b2obo5bob2o3bo2b2o45b2o2bo3b2o
bo5bob2o3bo2b2o57bo5b2o3bobo3b2o5bo$2bob2ob6o3b6ob2obo49bob2ob6o3b6ob
2obo58bob2o5bobo3bobo5b2obo$7bo2bobo3bobo2bo59bo2bobo3bobo2bo62b2o2bo
3b2obo5bob2o3bo2b2o$4bobo2bo9bo2bobo53bobo2bo9bo2bobo61bob2ob6o3b6ob2o
bo$2b3o3bo11bo3b3o49b3o3bo11bo3b3o64bo2bobo3bobo2bo$2b3obobo11bobob3o
49b3obobo11bobob3o61bobo2bo9bo2bobo$3b3o17b3o51b3o17b3o60b3o3bo11bo3b
3o$160b3obobo11bobob3o$4bo19bo53bo19bo62b3o17b3o$2b2o21b2o49b2o21b2o$b
obo21bobo47bobo21bobo60bo19bo$b3o21b3o47b3o21b3o58b2o21b2o$159bobo21bo
bo$b2o23b2o47b2o23b2o57b3o21b3o$b3o21b3o47b3o21b3o$4bo4b3o5b3o4bo53bo
4b3o5b3o4bo60b2o23b2o$9bo2bo3bo2bo63bo2bo3bo2bo65b3o21b3o$2bobo4bo9bo
4bobo49bobo4bo9bo4bobo61bo4b3o5b3o4bo$3bo7b2o3b2o7bo51bo7b2o3b2o7bo67b
o2bo3bo2bo$6b5o7b5o57b5o7b5o63bobo4bo9bo4bobo$5b4o11b4o55b4o11b4o63bo
7b2o3b2o7bo$4b2o17b2o53b2o17b2o65b5o7b5o$6bob2o9b2obo57bob2o9b2obo66b
4o11b4o$5bob2obo7bob2obo55bob2obo7bob2obo64b2o17b2o$7b5ob3ob5o59b5ob3o
b5o68bob2o9b2obo$2b3o2b2o2b2o3b2o2b2o2b3o49b3o2b2o2b2o3b2o2b2o2b3o62bo
b2obo7bob2obo$4bo2b2o2b2obob2o2b2o2bo53bo2b2o2b2obob2o2b2o2bo66b5ob3ob
5o$3bo3b2o2b3ob3o2b2o3bo51bo3b2o2b3ob3o2b2o3bo60b3o2b2o2b2o3b2o2b2o2b
3o$3bo5bobob3obobo5bo51bo5bobob3obobo5bo62bo2b2o2b2obob2o2b2o2bo$3bo3b
5o5b5o3bo51bo3b5o5b5o3bo61bo3b2o2b3ob3o2b2o3bo$4bo3b2o9b2o3bo53bo3b2o
9b2o3bo62bo5bobob3obobo5bo$11bo2bo2bo67bo2bo2bo69bo3b5o5b5o3bo$11b2o3b
2o67b2o3b2o70bo3b2o9b2o3bo$13bobo71bobo79bo2bo2bo$169b2o3b2o$8b3o7b3o
61b3o7b3o76bobo$7bo3b2o3b2o3bo59bo3b2o3b2o3bo$8bo11bo61bo11bo71b3o7b3o
$8bo4bobo4bo61bo4bobo4bo70bo3b2o3b2o3bo$7bobobo5bobobo59bobobo5bobobo
70bo11bo$7bo3bo5bo3bo59bo3bo5bo3bo70bo4bobo4bo$7b2o3bo3bo3b2o59b2o3bo
3bo3b2o69bobobo5bobobo$11bo5bo67bo5bo73bo3bo5bo3bo$9bo9bo63bo9bo71b2o
3bo3bo3b2o$9b2o7b2o63b2o7b2o75bo5bo$10bo7bo65bo7bo74bo9bo$167b2o7b2o$
168bo7bo$9b3o5b3o63b3o5b3o$9b2o7b2o63b2o7b2o$8bo3bo3bo3bo61bo3bo3bo3bo
72b3o5b3o$9bo3bobo3bo63bo3bobo3bo73b2o7b2o$13bobo71bobo76bo3bo3bo3bo$
11bo5bo67bo5bo75bo3bobo3bo$171bobo$11b3ob3o67b3ob3o77bo5bo$11b2obob2o
67b2obob2o$9bobo5bobo63bobo5bobo75b3ob3o$8bob2o5b2obo61bob2o5b2obo74b
2obob2o$8bo11bo61bo11bo72bobo5bobo$7bo2b2o5b2o2bo59bo2b2o5b2o2bo70bob
2o5b2obo$8b2o9b2o61b2o9b2o71bo11bo$7bob2o7b2obo59bob2o7b2obo69bo2b2o5b
2o2bo$9b2o7b2o63b2o7b2o72b2o9b2o$6bo15bo57bo15bo68bob2o7b2obo$6b2o3bo
5bo3b2o57b2o3bo5bo3b2o70b2o7b2o$6b3o2bo5bo2b3o57b3o2bo5bo2b3o67bo15bo$
7bo13bo59bo13bo68b2o3bo5bo3b2o$9b2ob2ob2ob2o63b2ob2ob2ob2o70b3o2bo5bo
2b3o$10bob2ob2obo65bob2ob2obo72bo13bo$9b2ob2ob2ob2o63b2ob2ob2ob2o73b2o
b2ob2ob2o$10bo7bo65bo7bo75bob2ob2obo$10bobobobobo65bobobobobo74b2ob2ob
2ob2o$10bo7bo65bo7bo75bo7bo$168bobobobobo$8bo4bobo4bo61bo4bobo4bo7bo7b
o7bo7bo41bo7bo$8bo3bo3bo3bo61bo3bo3bo3bo6b3o5b3o5b3o5b3o$7b2obo7bob2o
59b2obo7bob2o4bo2b2o3b2o2bo3bo2b2o3b2o2bo5bo7bo7bo7bo7bo4bobo4bo$8bob
2o5b2obo61bob2o5b2obo4b2o2b2o3b2o2b2ob2o2b2o3b2o2b2o3b3o5b3o5b3o5b3o6b
o3bo3bo3bo$6bob3o7b3obo57bob3o7b3obo2b2o2b3ob3o2b2ob2o2b3ob3o2b2o2bo2b
2o3b2o2bo3bo2b2o3b2o2bo4b2obo7bob2o$5bo17bo55bo17bob3o9b3ob3o9b3ob2o2b
2o3b2o2b2ob2o2b2o3b2o2b2o4bob2o5b2obo$12bo3bo69bo3bo9b2o9b2o3b2o9b2o2b
2o2b3ob3o2b2ob2o2b3ob3o2b2o2bob3o7b3obo$11bobobobo67bobobobo39b3o9b3ob
3o9b3obo17bo$7b3o3bobo3b3o59b3o3bobo3b3o36b2o9b2o3b2o9b2o9bo3bo$7b4obo
3bob4o59b4obo3bob4o73bobobobo$9b2o7b2o63b2o7b2o71b3o3bobo3b3o$7bob2o7b
2obo59bob2o7b2obo69b4obo3bob4o$6b2ob2o3bo3b2ob2o57b2ob2o3bo3b2ob2o70b
2o7b2o$5b2o2b2o2bobo2b2o2b2o55b2o2b2o2bobo2b2o2b2o67bob2o7b2obo$8b3obo
3bob3o61b3obo3bob3o69b2ob2o3bo3b2ob2o$5b5o2bo3bo2b5o55b5o2bo3bo2b5o65b
2o2b2o2bobo2b2o2b2o$4bo7b2ob2o7bo53bo7b2ob2o7bo67b3obo3bob3o$4bo3b2o3b
obo3b2o3bo53bo3b2o3bobo3b2o3bo64b5o2bo3bo2b5o$4bobo2bo3bobo3bo2bobo53b
obo2bo3bobo3bo2bobo63bo7b2ob2o7bo$11b3ob3o67b3ob3o70bo3b2o3bobo3b2o3bo
$7b3ob3ob3ob3o59b3ob3ob3ob3o66bobo2bo3bobo3bo2bobo$13b3o71b3o79b3ob3o$
13b3o71b3o75b3ob3ob3ob3o$171b3o$11bo5bo67bo5bo79b3o$11bobobobo67bobobo
bo$169bo5bo$169bobobobo!
#C [[ AUTOFIT AUTOSTART GPS 4 ]]

This is the twenty-second spaceship velocity constructed in Conway's Life -- counting each of the four infinite families of spaceships (Gemini, HBK, Demonoid, Caterloopillar) as one velocity each.

10 March 2016

New c/10 "copperhead" spaceship

Reposted with permission from Alexey Nigin's blog:

The day before yesterday (March 6, 2016) ConwayLife.com forums saw a new member named zdr. When we the lifenthusiasts meet a newcomer, we expect to see things like “brand new” 30-cell 700-gen methuselah and then have to explain why it is not notable. However, what zdr showed us made our jaws drop.

It was a 28-cell c/10 orthogonal spaceship:

An animated image of the spaceship

To explain why this is such a groundbreaking discovery, I should first tell you that Life spaceships can be loosely divided into two categories. Engineered ships are the ones that consist of various small components. They often have adjustable speed. However, the population of tens of thousands to millions of cells causes these spaceships to have no practical value.

There is much more incentive in hunting for elementary spaceships, which can be used for complex constructions. They are found using programs such as gfind or WLS. The algorithms behind these programs are beyond the scope of my article, but the important thing is that the search time goes up exponentially as the period of the ship grows. It is most interesting to find spaceships of new speeds, and the number of speeds that low-period ships can have is unfortunately limited:

Orthogonal Diagonal
c/2 Yes Impossible
c/3 Yes Impossible
c/4 Yes Yes
c/5 Yes Yes
2c/5 Yes Impossible
c/6 Yes Yes
c/7 Yes Yes
2c/7 Yes Impossible
3c/7 No Impossible
c/8 No No
3c/8 No Impossible
This table does not include oblique speeds, which causes little inconvenience because no elementary oblique ships are known.

The table above shows that ships exist for most of possible speeds, and it seems obvious that the speeds for which there are no ships have been searched by numerous people with good knowledge of search programs, powerful computers and lots of patience. As for higher periods, even the smallest searches would take years on modern computers. It appears that low-hanging fruit have been harvested clean during the 46 years of Life research… or, more precisely, it appeared so before zdr’s post.

The idea we all missed is that if the ship is really microscopic, it can be found in reasonable time despite its high period. After zdr boldly went where no man has gone before, Josh Ball set up the corresponding search in gfind and refound the spaceship in a little over an hour. zdr said that their program found it in a matter of 19 seconds.

To be frank, similar event did happen before when the aforementioned Josh Ball pulled loafer out of a hat. However, zdr’s spaceship (which is now called Copperhead, as proposed by muzik) is much more awesome for a number of reasons:
  • Loafer is not so mind-bogglingly high-period.
  • Copperhead was much easier to find, so it is more surprising that nobody found it before.
  • Copperhead’s tail is relatively strong and can interact with other objects without breaking down.

The discovery of a new spaceship speed immediately opened a few new areas of research, which are being explored now.

Synthesis

Aidan F. Pierce came up with a Copperhead synthesis only 10 hours after the completion of the spaceship. The synthesis was inefficient, and a few people discovered better ones. The current best synthesis, made by Chris Cain, requires only 22 gliders. Its repeat time is 375 ticks, which means that a gun can start constructing the second spaceship 375 ticks after the first one. There is a 23-glider synthesis with a better repeat time of 373 ticks.

Incremental 22-glider synthesis of the copperhead

The synthesis can be substantially improved if we find this spaceship crawling out of a random soup. Adam P. Goucher has written a wonderful program called apgsearch, which is perfectly suited for this task. While the current version may be too slow to find a soup in reasonable time, highly anticipated version 3.0 can probably do the trick. Once it is found, it will appear here.

Guns

Once the synthesis was complete, building a gun was nothing but corollary-sniping. The first copperhead gun was created by myself, and a video of it is available here. It was put together in a hurry and is therefore extremely inefficient. In particular, skilled gun builders can spot a silly mistake in the Northeast.

gmc_nxtman then made another gun with an almost optimal period of 376 ticks.

Eaters

simeks found two eaters for this ship, the better of which is shown below:

A copperhead eater

It is now time to search for a good copperhead-to-something-useful converter. The only existing one is clumsy and slow.

Sawtooths

Sawtooths often work by sending a flotilla of fast ships towards a slower ship. The more is the difference in speed, the less is the expansion factor of a sawtooth. Since expansion factor is proportional to how boring the sawtooth is, increasing the speed difference is a good thing. Dean Hickerson collided c/2 standard spaceships with c/10 copperhead to get a sawtooth with expansion factor 6:

Hickerson's sawtooth

He then made another sawtooth with expansion factor 10/3.

Puffers and rakes

Suppose a c/10 flotilla is hit by a glider. The glider turns into loads of mess, but all copperheads somehow survive and move on. The mess releases a glider, which flies into strategically placed second flotilla that is identical to the first one. Gliders continue to bounce back and forth between flotillas leaving mess behind them, and a c/10 puffer is complete!

Unfortunately, this cool technique doesn’t work out easily in our case. There are no interesting interactions between a glider and a single copperhead, and it is unclear how one can place two or more copperheads so close to each other that a glider interacts with all of them. Assuming we figure it out, we can try to make a rake by perturbing the mess with copperheads so that it evolves into gliders, but that seems even less likely.

However, all this hand-waving can be turned it real puffers if we find…

Tagalongs

Tagalongs are small things that are attached to the back of a spaceship and move with it. Here is an example tagalong, called the Schick engine:

Schick engine pulled by two LWSSs

Finding a tagalong for the copperhead (or two copperheads) will be really nice. We can also try searching for pushalongs, but they are generally rarer.

Other patterns

There are a few other areas of Life exploration where the copperhead can be useful. For example, universal constructors often need to create an elbow still life very far away. It can be done by producing a copperhead, waiting for some time, and then shooting the copperhead down with a LWSS. At the moment I do not see why the copperhead can be better than the loafer in this aspect, but who knows?