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 run at a sufficiently high step size, 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.

A new feature of slsparse that could be used to build a somewhat smaller loopship:

automatically compiled 0-degree construction for sufficiently narrow on-lane constellations

The largest metacluster is actually narrow enough that some reconfiguration of one-time turners could allow the entire constellation to be constructed directly by 0-degree gliders, with no Snarkmaker/Snarkbreaker combinations necessary.

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 15 gliders. See this conwaylife.com forum posting for a sample RCT pattern with 17 gliders (a shillelagh). Following posts describe how it's possible to do the same kind of universal construction with just 16 gliders.

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:

a one-time circuit producing two gliders that stop the receding block-laying switch engine without releasing any gliders
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
a one-time circuit producing a specialized Cordership able to remove unused blocks from the block-laying switch engine's ash trail
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 Life Construction is Capped at 329...59...58...50...44... 43... 35...32...17...16...15

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 several times, as indicated by the series of numbers in this article's title.
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!
UPDATE 19 September 2020 and 11 November 2022: Design improvements by MathAndCode, Adam P. Goucher, and danielle make possible a reduced reverse caber tosser design requiring only 16 gliders, a 50% reduction from the previous fixed cost of 32 gliders.
UPDATE 15 September 2022: The fixed cost has now been reduced to 15 gliders.

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.