Conway's Life: Work in Progress

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

10 November 2018

New Tools for Self-Construction

Time for a new post on self-constructing circuitry! I've been updating the same old post since 2014, but I think there's now some news that warrants a new article.

Self-Construction Just Got A Lot Easier

For the last several years Adam P. Goucher has been incrementally working out the construction details for a "0E0P metacell". A metacell is a piece of Life circuitry that simulates the behavior of a single cell in Life, or in many cases some other CA rule, depending on how it's programmed.

"0E0P" is short for "[state] zero equals zero population", meaning that no support circuitry is needed: when one of these 0E0P metacells turns off, it self-destructs completely! This means that when the metacell needs to turn back on again, it must be re-constructed from the ground up by its neighbors.

One of the important effects of this design is that metacell patterns, when viewed from very far away (e.g., at a size where an entire metacell takes up a single pixel in the display) will be indistinguishable from normal patterns that use the same rule -- except that the metacell patterns will run 2^36 times more slowly, of course.

Automatically Generated Construction Recipes

A key breakthrough enabling the construction of the 0E0P metacell was a publicly available search program written by Goucher, capable of finding a single-channel construction recipe for any constellation of still lifes -- provided the still lifes aren't too close together, and that recipes are known for each of them in isolation. This search program was originally called "slmake" but is now renamed to "slsparse" due to its ability to analyze a large constellation and automatically separate it into several well-separated sub-constellations, or "metaclusters" (when that's possible).

The first few self-constructing patterns -- Gemini, 10hd and 0hd Demonoids, linear propagator, and the first spiral-growth pattern -- all had slow-salvo recipes that were mostly compiled by hand. This was usually one of the most time-consuming parts of the construction process, and once a recipe was compiled it was often very difficult to make small adjustments to the design without recompiling everything from the ground up. Now that slsparse is available, it's much easier to produce new pattern variants and entirely new designs.

Here are three recently completed self-constructing spaceships that owe their existence to compilation with slsparse -- with images of each, since for a change they all look like something other than plain long straight lines from a distance.

Fast HashLife-friendly Orthogonoid

Older version with slow elbow push:

Lower-population version with Cordership elbow push:

The older Orthogonoid has a fairly continuous recipe, so it's a little easier to see what direction it's going. The newer recipe consists mostly of long gaps between gliders, waiting for Corderships to reach their target locations.
  • The blue arrow marks a slow salvo that has almost caught up with a three-engine Cordership, which it will convert into the main body of Orthogonoid circuitry.
  • The purple arrow marks a single-channel salvo just starting the long trip after a two-engine Cordership, which it will convert into an elbow block and then create the seed for a new three-engine Cordership heading at right angles to the first, to the northwest.
  • The green arrows show the direction the recipe travels.
  • The red arrows on the west side show the future path of an MWSS and glider that do the cleanup of previous circuitry that's no longer in use. The MWSS is constructed by the short segment of single-channel recipe that is just reaching the elbow ahead of the leftmost green arrow; it's a copy of a short final section of the last largest segment of the recipe.

Features of slsparse used to build the new Orthognoid include

  • automatic compilation of very widely separated metaclusters

    This allows the MWSS-to-glider circuit to be moved a long distance from the glider-to-MWSS circuit, which allows the structure of the spaceship to be much more visible from a distance -- and incidentally reduces the number of required hashtiles enough that Golly can now "run away" with the pattern.

  • automatically compiled elbow push and hand push, with different Corderships

    For historical reasons, slsparse currently uses 3-engine Corderships to move "hand" target blocks long distances at right angles to the construction lane. The more recently discovered two-engine Corderships are used to push elbow blocks long distances along the construction lane.

  • automatically compiled non-Spartan objects

    There's lots more available than the old standard Spartan still lifes -- even without counting the bespoke object collection, which allows for the construction of extra-difficult and extra-useful structures such as syringes and Snarks. For example, an aircraft carrier used to change a glider's color as part of the elbow Snark's self-destruct circuitry. This isn't strictly Spartan, but with slsparse the state of the art has moved well past that artificial limitation.

Hashlife-friendly Demonoid


(The image at right is not exactly to scale, but it's close enough that it should be recognizable.)

Features of slsparse that appear in the new Demonoid include

  • long-distance elbow pull

    A counterpart to the 2-engine Cordership push is a long-distance elbow pull recipe, also recently added to slsparse. A faraway elbow is converted to a return glider, which allows for much quicker movement toward the recipe source than would be possible with a long series of classical elbow-block PULL operations.

  • Snarkbreaker

    slsparse now knows a single-channel recipe that can add an additional lossless elbow to a construction arm -- a "Snarkmaker" -- and another recipe that can remove the added Snark when it is no longer needed ("Snarkbreaker"). This allows a single-channel arm to safely reach locations that are otherwise inaccessible, such as a construction area that overlaps the single-channel lane.

The above recipes were actually compiled by hand into the current HashLife-friendly Demonoid, because the relevant features hadn't been added to slsparse yet. The long-distance Cordership elbow push had also not been added yet, so the elbow movement was done inefficiently with a long series of PUSH operations, which accounts for a large fraction of the gliders needed in the recipe.

Challenge: Install the latest slsparse and use it to build a lower-population Demonoid than the current model, with wider separation (but still a power of two, to keep HashLife happy!) between the back-and-forth glider streams. Reasonably up-to-date installation and usage instructions can be found in this walkthrough on the LifeWiki.

------------------------------------------------

In this Demonoid design, only the Snarkbreaker is needed, and at the moment slsparse doesn't know how to do a Snarkbreaker without a matching Snarkmaker preceding it (see below). So the Snarkbreaker was added into the Demonoid recipe by hand after the compilation was completed.

Another trick used in the Demonoid that slsparse doesn't know about yet is

  • destruction of old circuitry by *WSS produced directly from construction elbow

  • This destruction method is much more efficient than bending the construction arm around two 90-degree corners to reach the location of the old circuitry. At the moment slsparse is primarily concerned with construction and not destruction.

Loopship

Features of slsparse used in building the loopship:

  • automatically compiled on-lane construction

    For the largest metacluster, slsparse automatically sends two Snarkmakers to move the construction arm sideways to a safe distance to complete the construction -- followed by two Snarkbreakers to return the arm to its original state.

Other mechanisms used in the loopship

  • destruction by GoL-destroy search result

    A separate search program called GoL-destroy written by Simon Ekström finds ways to interleave random still lifes into signal circuitry, out of the way of the actual signal paths, in such a way that the entire structure collapses cleanly down to zero population when it is hit by a single self-destruct signal. slsparse can compile these additional still lifes just as easily as the original circuitry.

  • one-time turners

    A few classical one-time converters -- glider to MWSS, MWSS to glider, and glider to 2 glider -- were also included in the design, just for variety, though they're probably slightly less efficient than the best solution that a GoL-destroy search could come up with.

The loopship's recipe gliders traverse parts of their path three times in a row, and some of those gliders (or rather a copy of them) travel the exact same path a fourth time, ahead of the full recipe. This happens along the zigzag central spine of the loopship.

A "working copy" of the recipe is split off from each loop to do the actual construction. The working copy first builds two Corderships and sends them off at 90 degrees to the left and right, to the next new loopship corners. After the necessary long pause, it follows those Cordership with cleanup salvos.

After that, the remainder of the working copy builds two temporary lossless elbows (Snarks) and constructs the biggest part of the loopship circuitry, which is a Scorbie Splitter combined with two Snark reflectors plus self-destruct circuitry. As the spaceship travels, a copy of this circuitry will appear at each 90-degree bend along the central spine.

An accurate diagram would show all these paths stacked exactly on top of each other, like the illustration at left.

However, it may be easier to visualize what's happening in the loopship, with a diagram has successive traverses offset slightly, as shown at right.


The above diagrams represent one full period of the loopship, made up of two mirror-image half periods. Adding another half period would look something like this:

The actual loopship has significantly different shapes at different times in its construction cycle. Here's a snapshot diagram where

  • the two Corderships (orange dots) are each in the process of being chased down by a salvo of zero-degree gliders. The southeast salvo will convert the Cordership's leftover debris into a Snark, and the northwest salvo will reduce that Cordership to a single block.

  • the remainder of the recipe traveling northeast will construct a new splitter-plus-Snarks constellation (a future blue dot halfway between the two Corderships).
  • a copy of the full recipe is heading southwest around the left-hand loop (green arrows).

  • a cleanup MWSS and glider (red dots) have almost reached the splitter-plus-Snark (blue dot) and Snark (purple dot) to the south, which are no longer in use.

The Switching System

There are a few details of the loopship's operation that aren't covered by the diagram. In particular, an extra signal makes its way around the loop twice, following a chain of one-time turners. This is what triggers the two self-destruct signals, and also turns off one of the branches of each Scorbie Splitter so that the full recipe doesn't get copied again, to attempt a second disastrous trip around the delay loop.

Final Challenges

The loopship is considerably bigger than it needs to be... and making it smaller requires only one minor adjustment to the recipe. It's quite possible to make this change without doing any recompiling with slsparse. Details of some open problems are posted on the loopship forum thread.

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, some of which are already out of date now that a universal construction method has been found with as few as 35 gliders. See this conwaylife.com forum posting for a high-level walkthrough of how the 35-glider recipe might work.

The "reverse caber tosser" idea, with two gliders reflected back 180 degrees by a Cordership (or Corderpuffer, anyway) still remains intact -- and so does the three-glider PUSH/DFIRE salvo and the idea of using a block-laying switch engine as a source of elbow blocks. However, all of the PUSH/DFIRE salvos are now produced by glider-producing switch engines. These various switch engines are almost the only things that need to be constructed. In the 50-glider UC model, no stationary circuitry is needed at all. The 35-glider model needs a single block as a catalyst, to cleanly generate a return glider to retrieve the next bit from the approaching Corderpuffer.

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. However, 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 cost of the construction. 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.

More recent fixed-cost construction designs include the proposal that the Cordership should be replaced with a c/12 puffer that is cheaper to synthesize -- 7 gliders instead of 9. This leaves a much larger mess to clean up, but it's still doable... and reducing the initial cost is the only thing that matters for this particular project.

The Cordership, or puffer, 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/puffer 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/puffer.

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, 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 Answer to Life's Ultimate Question is 42 -- But the Cost of Living is Capped at 329...59...58...50...44... 43... 35

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 initial upper limit was 329 gliders, based on the pattern shown above. This has since been reduced to only 59 and then 58 gliders, with a proposal to simplify further and bring the total down to 43.
See the follow-up article for a full summary of the tasks that the universal constructor has to accomplish to be enable the 329-glider recipe to to construct any arbitrary pattern. The plans for the 58-, 43-, and 35-glider recipes are similar, but greatly simplified by the fact that the streams of gliders can all be generated by faraway glider-producing switch engines instead of local glider guns and reflectors. With the 58-glider recipe, no stationary circuitry is needed at all; a single block is needed as a catalyst in the 43- and 35-glider recipes.
** 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, let alone two!

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.