slmake

From LifeWiki
Revision as of 00:21, 24 March 2019 by Calcyman (talk | contribs)
Jump to navigation Jump to search
slmake
Homepage Click here
Purpose Slow glider construction
Created by Adam P. Goucher
Platform Unix / Cygwin

slmake is a search program first published by Adam P. Goucher in May 2017.[1] It accepts as input a constellation of sufficiently widely separated still lifes, and produces a glider stream that will perform a complete slow glider construction of that constellation, starting from a single block. The name of the current version of the program is actually slsparse, due to the added capability of automatically partitioning very large sparse patterns into multiple widely-separated constellations, and devising recipes for each of the partitions. However, 'slmake' is still commonly used to refer to the entire program package, and it remains the name of the GitLab repository.

It is built atop lifelib, relying on a large (200 megabytes compressed; 800 megabytes uncompressed) collection of precompiled slow salvo recipes found by breadth-first search. In addition to this, there are several 'bespoke' syntheses for unnatural objects such as Snarks and eater2s, which were the result of collaborative human engineering by Chris Cain and others. As such, it is capable of finding recipes not only for Spartan stable circuitry, but also for other useful non-Spartan circuits containing Snarks, syringes, and H-to-MWSS converters, provided that they are separated from other nearby objects by a sufficient amount of empty space.

Strategies

Instead of building the recipe in the order of construction, slmake works in reverse by taking the input pattern and reducing it to a slightly simpler problem. Proceeding inductively, slmake reduces the problem to a single block. In order to prevent it from getting caught in a loop ad infinitum, slmake uses six strategies which guarantee that the descent will terminate (successfully or otherwise):

  • split: two objects, one of which is a block, are created from a single object;
  • reduce: a single object is created from a simpler object (typically beehive, tub, or block);
  • bespoke: a bespoke object (typically a Snark or eater2) is constructed in place;
  • tree: by moving a block, the problem is reduced to one with a smaller minimum spanning tree;
  • deep: slmake does a 1-step lookahead to see if it can apply another strategy;
  • uncover: objects are moved out of the way of a bespoke object to enable its synthesis.

The slsparse executable separates the input pattern into metaclusters, each of which is separately slow-salvo constructed using the above combination of strategies. These slow salvos are further compiled into single-channel constructions which emit 90-degree slow gliders from an elbow block. For long-distance elbow and hand movements, slsparse will build temporary 2-engine Corderships and/or 3-engine Corderships if doing so yields a shorter overall recipe; this was integral to ensuring that the 0E0P metacell's tape could fit within its confines.

If a metacluster is on the channel itself, then slsparse will resort to either using 0-degree gliders (if the metacluster is sufficiently narrow) or building a temporary pair of Snarks to shift the channel, thereby reducing the problem to the previous case.

Optimisations

After constructing each slow-salvo recipe, slmake will attempt to reorder the sequence of gliders to defragment the recipe. This will result in a shorter single-channel construction, on the basis that the number of elbow moves is minimised.

Applications

One of slmake's primary uses is to make self-constructing patterns much easier to design and build. Dave Greene used this software to generate the construction recipes involved in the Orthogonoid, Hydra, and HashLife-friendly Demonoid.

Tutorials

A walkthrough of how to use slmake / slsparse to assemble a simple self-constructing spaceship is available under Tutorials/slsparse.

References

  1. Adam P. Goucher (2017-05-05). Re: Slow-salvo recipes (discussion thread) at the ConwayLife.com forums

External links