README.md 5.83 KB
Newer Older
Adam P. Goucher's avatar
Adam P. Goucher committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
This repository contains software for producing self-constructing circuitry
in Conway's Game of Life. The main program is `slsparse.cpp`, which takes
an annotated arrangement of still-lifes (in `infile.mc`) and produces a
glider stream which constructs the arrangement. The glider stream is saved
as both an output pattern, `outfile.mc`, and a textual list of spacings,
`outfile.txt`.

It operates by splitting the pattern into one or more well-separated
**metaclusters** which are processed individually. For each metacluster,
an efficient recipe is found by heuristic-driven dynamic programming. This
recipe is then reordered to reduce the length of the glider stream. Finally,
the glider streams for the separate metaclusters are concatenated in order
to produce a complete synthesis of the original pattern.

There is [a tutorial](http://conwaylife.com/wiki/Tutorials/slsparse) written
by Dave Greene, the content of which will not be needlessly duplicated here.
Several example projects are given in [an article he wrote][1], with the
largest and most ambitious being [a self-replicating metacell][2].

[1]: http://b3s23life.blogspot.com/2018/11/new-tools-for-self-construction.html
[2]: https://cp4space.wordpress.com/2018/11/12/fully-self-directed-replication/

This repository also contains a script, `isotropic_metafier.py`, to assemble
arbitrary patterns in arbitrary isotropic 2-state 9-neighbour cellular
automata out of these metacells.
Adam P. Goucher's avatar
Adam P. Goucher committed
26

27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
History
-------

In the 1970s, there were blueprints for building a self-replicating pattern
in Conway's Game of Life. However, all of these were so large and unweildly
that there has been no serious attempt to realise any of these early designs.
This changed in the 21^st century, when Dave Greene and Paul Chapman built
a configuration theoretically capable of universal construction by means of
_slow salvos_: volleys of well-separated gliders aimed at an initial target
to incrementally transform it into the desired output. In 2010, Andrew Wade
modified this design to form a complete self-constructing configuration,
_Gemini_, which slowly translates itself across the grid.

In April 2013, Mike Playle found a spectacularly small and fast signal
reflector, the _Snark_, which enabled the radical simplification of signal
processing circuits. Using the same search program, _Bellman_, Tanner Jacobi
was able to find another efficient component in March 2015, the _syringe_,
which can be used to duplicate gliders rather than just reflect them.

The last piece of the puzzle came in January 2016, when Simon Ekstrom
discovered that a single stream of gliders, compatible with the Snark and
the syringe, could be aimed at a block to produce an arbitrary slow salvo
of perpendicular gliders. This meant that universal construction would be
vastly simplified, but there was no systematic method of preparing recipes
for this construction arm. Moreover, the Snark and syringe involve complex
objects which are difficult to build with glider collisions, especially slow
salvos.

Meanwhile, Adam P. Goucher (the author of slmake) had been running a
distributed search called _Catagolue_, which has simulated the evolution of
approximately 11 trillion random initial configurations and collected over
250 trillion individual objects (of over 100 000 distinct types) produced
in this manner. With the help of results from Catagolue, Chris Cain and
Martin Grant were able to find slow-salvo recipes for both the Snark and the
syringe, the two most difficult components worth building.

However, there was still the problem that building a slow-salvo recipe for an
arbitrary design was an arduous manual task which took several minutes per
constituent object. The simplest designs involved about 50 such objects;
converting this to a tape would therefore often take many days of toil. An
automatic compiler was thus on the wishlist of many cellular automatists.

To address this, Goucher developed _lifelib_ using an algorithm inspired by
the best parts of apgmera (the search program used by Catagolue) and HashLife
(an algorithm conceived by Bill Gosper and implemented by Tom Rokicki in the
popular program _Golly_). This C++ library is a deep stack of abstractions,
with hashtables and inline assembly at the base, and high-level pattern
manipulation routines at the top. Using lifelib, two complementary programs
were written:

 - _HoneySearch_, a parallelised search program which runs on a computing
   cluster and finds simple slow-salvos for moving, converting, and copying
   objects;
 - _slmake_, a backtracking compiler which reduces a difficult construction
   to a slightly easier construction by trying any of several different
   simplifying strategies. By iterating this, it ultimately finds a slow
   salvo recipe capable of building the target configuration from a single
   block (the simplest and commonest individual object).

After running HoneySearch on a cluster over several days, culminating in
over 100 gigabytes of memory usage, enough results were produced and
distilled into the `data` directory (slightly less than a gigabyte of recipes
usable by slmake). This repository contains these data together with slmake
itself and several other helper programs.

Adam P. Goucher's avatar
Adam P. Goucher committed
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
Credits
-------

The contents of the `data` directory were prepared using a variety of search
tools by Dave Greene, [Simon Ekstroem][3], and myself; this was supplemented
by manual recipes by Chris Cain and Martin Grant, partially based on search
results from [Catagolue](https://catagolue.appspot.com/census/b3s23/C1).

[3]: https://github.com/simeksgol/GoL_single_channel

The mechanisms for efficiently moving the construction arm by a long distance
are based on the [2-engine][4] and [3-engine][5] Corderships discovered by
Aidan Pierce and Paul Tooke, respectively. Dave Greene helpfully compiled the
'launchpad seeds' involved.

[4]: http://conwaylife.com/wiki/2-engine_Cordership
[5]: http://conwaylife.com/wiki/3-engine_Cordership