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.
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.
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.
No comments:
Post a Comment