Slow salvo from 31c/240 spaceship project
-- click the image to get the pattern RLE.
-- click the image to get the pattern RLE.
Quick Review
A "slow salvo" is a series of gliders all traveling the same direction. A "slow salvo construction" involves aiming a carefully designed slow salvo at a target object, and incrementally converting that target into some new object using a series of controlled collisions. Such a slow salvo is often described as a "recipe" for the new object.
Some recipes may recreate the original target in a new location. Slow salvos can be proven to be universal, so other recipes might produce output gliders at 90 degrees from the original salvo, or larger spaceships, or any possible glider-constructible object.
In a slow salvo, arbitrarily long delays can be added between any two gliders. In other words, slow-salvo glider collisions must always settle into stable ash before the next glider arrives. In this context, "stable ash" might mean actual period-1 still lifes, but in "P2 slow salvos", low-period oscillators such as blinkers, beacons, or toads are also allowed as intermediate targets.
In the P2 case, of course, gliders can only be delayed by an even number of ticks. P3, P4, P5, P6, etc. slow salvos are technically possible, with restrictions analogous to the P2 case, but they don't seem to offer any practical advantages over P2 slow salvos.
New Developments
Here's a list of known uses for slow-salvo technology, in rough chronological order:
1) Conway's Universality Proof for B3/S23
Unidirectional salvos were a significant component of John Conway's proof of construction universality in Life. The original proof was completed shortly after Gosper's glider gun was discovered (in 1970). Only an outline of the proof was ever published, many years later, in Volume 2 of Winning Ways for Your Mathematical Plays (1982). Part of the idea was to aim one or more "flotillas" -- long series of gliders all traveling in the same direction -- at a faraway simple object, or a faraway opposing flotilla produced by "double side-tracking". The glider collisions would gradually convert the target object into a complex piece of period-30N circuitry capable of performing calculations... including, eventually, the calculations needed to construct copies of the original flotillas.
These were unidirectional salvos, but not necessarily slow salvos. Some of Conway's construction recipes required multiple nearby gliders to be precisely synchronized with each other.
2) Schroeppel's Speculations on Sparse Life Universe Fate
By 1992 Rich Schroeppel and others had worked out the likely long-term fate of an infinite Life universe in which each cell had a very low but nonzero probability of being ON initially. After a few ticks, such a universe would consist predominantly of blocks and blinkers, since these only require three initial ON cells near each other to persist. Gliders would be very much rarer since they need five coordinated ON cells to get started -- but whenever a rare one did appear, it would travel until it eventually collided with something.
A glider hitting a blinker, or a block that has already been struck by another glider, can cause a chain reaction that releases multiple additional gliders. Schroeppel showed that arbitrarily long unidirectional salvos would eventually be created by chains of these kinds of collisions. Any glider could follow any other glider on nearby lanes, with few or no limitations -- except that most sets of closely-spaced gliders were much less likely.
Following Conway's universal-construction ideas, Schroeppel conjectured that a replicator would eventually appear that consisted of a long unidirectional flotilla of gliders aimed at a single faraway block. Here again this flotilla may have been visualized as containing some synchronized gliders, as long as they could be produced by gliders interacting with common random ash objects.
However, the key term "slow-unidirectional-salvo" appeared more than once in 1992. Also, Schroeppel's replicator blueprint used gliders of only a single color, analogous to the squares a bishop can reach on a chessboard. It appears that these monochromatic gliders were known or assumed to comprise a universal construction toolkit; this has recently (quite possibly not for the first time) been proved by construction. The concept of "slow synthesis" was introduced by Alan Wechsler and discussed in depth by Mark Niemiec in 1996.
3) Nick Gotts and Sparse Life
Nick Gotts introduced the term "slow salvo" into more general use in 1997, leaving "unidirectional" unstated (since that's implied by the definition of "salvo" in any case). Building on Schroeppel's earlier investigations, Gotts showed the feasibility of using pure slow salvos to construct arbitrarily complex objects, including rare infinitely growing objects. One early result was a 53-glider slow-salvo recipe for a block-laying switch engine. The primary research focus was on the emergence of increasing levels of complexity starting from random initial conditions, as opposed to universal construction or replicator design.
The appearance of actual construction recipes made it clearer that a complete universal toolkit could be built up from slow salvos alone, aimed at some very simple object -- a block, or pretty much any small common ash object. Such objects could be placed at arbitrary distances by various "pusher" reactions, or by collisions between fast and slow glider-constructible spaceships. (Various c/12 Corderships were known by 1997.) This avoided a lot of worries about the slow and complicated side-tracking guns that had been part of earlier universality arguments.
4) The Prototype Universal Constructor
In 2004 Paul Chapman built a prototype Conway's Life universal constructor. It was designed to read recipe data from a static tape and convert it into a slow salvo. Theoretically it was capable of being programmed to construct anything glider-constructible, up to and including itself. It did not include any mechanism for duplicating construction data to a new copy of itself, however, so it was not a candidate replicator.
The prototype was programmed to slow-construct a single eater. A small modification allowed the pattern to loop indefinitely, constructing an oblique line of eaters. But it was apparently too difficult to program -- no other slow-salvo recipes have ever been generated for it in its original form (!).
5) Spartan Universal Computer-Constructor
In 2009 Adam P. Goucher incorporated Chapman's prototype universal constructor into a single programmable pattern that was both a universal constructor and a universal computer. Here again, universal construction ability was theoretically provided by a single construction arm... but in practice, the UCC was never programmed to construct even as much as a line of eaters.
6) O(sqrt(log t)) Diametric Growth Pattern
In April 2010, just one month B.G. (Before Gemini), Adam Goucher also completed a pattern that grows at the slowest possible rate for a Conway's Life pattern -- or any other 2D Euclidean CA rule, for that matter. Of course it's possible to slow it down further by adding various delay mechanisms, but the new version would still have an O(sqrt(log t)) growth rate. Anything slower than that is provably impossible. Osqrtlogt.mc can be downloaded from within Golly 2.6 via Help > Online Archives > Very Large Patterns.
This rather mysterious and under-documented pattern uses two slow salvos, 28 gliders and 10 gliders respectively, to read and write bits in an unbounded triangular grid. Basically it counts in binary, using two-dimensional arrangements of boats on the Life plane separated by 16 full diagonals. The pattern uses copies of various pieces of the prototype constructor. The slow salvos were constructed manually using the original P1 block-move table, so they are very far from optimal! A tighter bit spacing could now be found with many fewer gliders.
Honeyfarm targets for the salvos are created by a secondary arm that produces single gliders perpendicular to the primary slow-salvo shotgun direction. This initial collision is very similar to the construction method used by the (completely independently designed) Gemini spaceship -- see below.
7) The Gemini Spaceship
In May 2010 Andrew Wade's self-constructing Gemini spaceship was published, again based on Chapman's 2004 prototype. The Gemini broke new ground in many areas, including the use of two construction arms firing coordinated 90-degree slow salvos to build Herschel-based signal circuitry. The Gemini's construction gliders are paired so that each glider in one slow salvo is synchronized with a glider in the other salvo. But as usual, successive gliders coming from the same direction don't have to be synchronized with each other -- only with their opposite number in the other salvo.
In most cases, construction by two perpendicular slow salvos is clearly much more efficient than construction with a single slow salvo. On the other hand, it takes extra circuitry to process the information for two separate slow salvos, and nontrivial signal-crossing problems can also show up in many cases. Single-salvo construction tends to minimize the complexity of the circuitry required for a universal constructor, at the cost of increasing the amount of construction data -- see #22.
8) Universal Construction with Intermittent P30 Glider Streams
Between 2009 and 2011, Frank Hoetmer put together a universal construction toolkit using collisions between slow salvos of *WSSes and gliders. The *WSSes and gliders were produced from 180-degree collisions of long streams of gliders. The two colliding streams were on fixed lanes, and were reflected with p30 technology, so the only variation available was the presence or absence of gliders in each p30 stream. Surprisingly, this turns out to be enough to allow construction universality, including the construction of new precisely-timed p30 gun/reflector components far away from the originals.
Like the Gemini spaceship, this was an independent project that showed up "out of the blue" and broke a lot of new ground. Intermittent P30 construction is impressively difficult -- among other things, very large recipes are needed, and child replicator components have to be constructed in exactly the right phase relative to the parent. As a result, this line of research was not continued once Geminoid technology became available.
9) Pianola Breeders
In 2010, Paul Tooke simplified and extended the Gemini's construction mechanism, producing a number of slow-salvo-constructed patterns with superlinear growth, including a Gemini-based slide-gun puffer and a series of Pianola breeders, which moved the Gemini's two construction arms to a permanent stationary platform, using fourteen glider-loop channels instead of twelve.
10) Serizawa Geminoids and "Armless" Universal Constructors
The extra complexity of multiple-arm circuitry has meant that since the original Gemini appeared, no two-arm constructor designs have been completed using Conway's Life rules. However, a self-constructing two-armed pattern has recently been completed in Serizawa, another CA rule. Design features from this pattern can be applied to many other rules; among other things, it made possible a new "armless" universal constructor design in Conway's Life that set new records for small size and population.
11) Linear Replicators in Conway's Life
The linear Life replicator, or "GoL propagator", demonstrated the universality of single-arm construction -- a single slow salvo aimed at simple targets can build anything that two arms can build. It is conjectured that either one or two slow construction arms can build anything that can be constructed with any number of colliding gliders (and/or spaceships). A proof is now within easy reach.
12) Freeze-Dried Seeds for Slow Salvos
With linear-replicator technology as a model, "freeze-dried" slow salvos -- a variant of Nick Gotts' chain reactions, but with the seed still lifes deliberately built by a universal constructor -- can be designed that allow the construction of spaceships with very small step sizes, such as (1,0) or (1,1) -- or (2,1), a true (very slow) knightship. As of January 2017 no explicit example has been completed.
13) Spiral Growth
A spiral-growth pattern was constructed using four copies of a single-arm universal constructor. More recently, a spiral-growth pattern smaller by a factor of 100 was completed, followed by one that's 5000 times smaller than that. The last pattern in the series uses an inline, 0-degree "Snarkmaker" recipe to build small lossless elbows using single-channel technology. See #23 below.
14) Slow-Salvo Construction of Loafers
In September 2013 universal-constructor based loafer seed factory was constructed, using an early version of the two-channel Demonoid (#22 below) construction arm design. This was along the same lines as Paul Tooke's Pianola breeders (#9), which were adapted from the Gemini's twelve channels.
15) 31c/240 Spaceships
In 2013 a new reburnable fuse was discovered that produced two gliders every 240 ticks, while the reaction moved forward 31 cells and the fuse moved forward 9 cells. 9 and 31 are relatively prime, and it turned out that the fuse could be modified in various ways to produce any possible slow salvo.
A new search utility has been written to locate the most efficient recipes for lightweight, middleweight and heavyweight spaceships, which can move fast enough to overtake the front of the fuse and close the loop by building more blocks to support the 31c/240 "Herschel climber" reaction -- very much along the same lines as the original Caterpillar spaceship, but with a new mechanism and new speed.
16) Caterpillar's Smaller Siblings
It appears that the original Caterpillar can now be made significantly smaller using slow-salvo technology. For example, the Caterpillar builds a large number of HWSSes that travel forward to build new blinker trails ahead of its 17c/45 pi climbers. Each HWSS recipe requires a rake about 8000 cells high, made up of two separate sets of forerakes and backrakes running on blinker trails. The rakes' gliders collide a long distance from the trails, forming the large oblique triangles that make up most of the Caterpillar's body.
Spaceship constructions that are done entirely with a slow salvo seem likely to need rakes that are only a few hundred cells high instead of several thousand, and that can be packed very closely one after another. Even when the construction site is 1500 cells from the rakes, with a slow salvo there's no need to wait thousands of ticks between rakes to allow perpendicular glider streams to converge.
17) Half-Baked Knightships
Slow-salvo technology has now been used to construct a (6,3) knightship based on interactions between chains of half-bakery reactions. The new feature of this design is that slow-salvo gliders are generated on only one color -- every other lane -- of the Life grid. As mentioned in #2 above, this is not a new idea, but the half-baked knightships are the first completed patterns to use this type of slow salvo for actual constructions.
18) Parallel HBK gun
A gun was created for the parallel version of the half-baked knightship. To date (July 2017) this gun is the only other use of the original Gemini spaceship's slow-glider-pair construction technique, besides Paul Tooke's Pianola breeders and (in a very limited sense) Adam P. Goucher's O(sqrt(log t)) pattern.
19) High-period 2c/7 "distaff" rake
In May 2014, building on 2c/7 puffer results from the previous December, Ivan Fomichev used a long chain of weekender conduits to generate gliders for a modified slow-salvo construction of a single LWSS ("modified" because it starts from two targets produced by glider-weekender collisions). The LWSS is then sent forward to the beginning of the chain to close the cycle and produce an adjustable high-period rake.
20) 'Engineless Caterpillar' (Caterloopillar) project
Starting in September 2014, Hartmut Holzwart proposed a slow-salvo-based version of David Bell's idea for an "engineless Caterpillar", from a decade ago. Michael Simkin has since worked out the necessary mechanisms for an adjustable "strange-loop" Caterpillar-like spaceship. an adjustable-period Caterpillar design that doesn't need a period-specific "climber" reaction. Instead, streams of gliders are generated by repeatable interactions between stable objects and backward-traveling fleets of passing *WSSes. These streams of gliders can be used to perform slow-salvo constructions of fleets of spaceships traveling the opposite direction, which collide with other still lifes at the front to build more backward-traveling fleets, thus closing the cycle. To allow the period to be as adjustable as possible, only P1 slow-salvo recipes can be used. If a blinker, toad or other P2 object were allowed as an intermediate target, the adjustability would be limited to either odd periods or even periods.
The current model can be fairly easily recalibrated to move at any sufficiently slow speed. For example, it can move at c/10, c/11, c/12, or any slower c/{integer}. The price of this adjustability is that only stable intermediate targets can be used; otherwise, very different construction recipes would be needed for even periods vs. odd periods. Slow construction of edge-shooter spaceship seeds, or any other stable seed object, appears to still be perfectly possible with this restriction. In fact, some preliminary searches seemed to show that P1 slow monochromatic gliders (all gliders the same color) would be sufficient, so an engineless caterpillar with an even step length would be technically possible -- e.g., moving 38 instead of 59 cells with each cycle. However, such a spaceship would be considerably longer due to less efficient slow salvo recipes.
21) (23,5)c/79 Caterpillar
Also starting in September 2014, building on discussion from the previous year, Brett Berger ('biggiemac' on the forums) steadily generated mechanisms and techniques for constructing the first oblique caterpillar knightship, based on a known (23,5)c/79 Herschel reaction. The spaceship was completed on December 28th of the same year. Constructions are a mix of slow-salvo transformations and synchronized collisions.
Unlike the engineless Caterpillar which is designed so that the period can be either odd or even, this spaceship's rate of travel is fixed and slow salvo gliders will always be the same distance apart. This means that p2 intermediate targets can be used. For example, there's a line of traffic lights near the top of the triangle in the current front-end design; every other traffic light is in a different phase, but the glider that collides with it is always in the correct phase to convert the traffic light to a beehive to support the oncoming Herschel climber.
22) Demonoid (diagonal Geminoid) spaceships
Starting in late 2012, a number of designs were proposed for a self-constructing Geminoid variant where the two halves of the spaceship would be glide-reflected mirror images of each other, instead of exact copies. This would limit the travel direction to an exact diagonal, but would cut the amount of circuitry roughly in half (because it would no longer be necessary to support input from two different directions).
Over the next three years, the amount of required circuitry was gradually decreased until a complete Demonoid needed only 48 still lifes to be built with a slow salvo, including all the self-destruct circuitry to clean up after each construction arm when its work is done.
As usual, this self-constructing spaceship has a trivial glider synthesis -- so trivial that for the first time in Life history, a gun for the 0hd Demonoid was built before the spaceship existed, and the very first 0hd Demonoid was fired by the gun.
In June 2017, a Demonoid using a single-channel recipe (see below) was constructed with only 19 still lifes per construction arm, and even more compact Demonoids were shown to be possible.
23) Single-channel construction arms Research by Simon Ekström in December 2015 proved that a universal construction arm was possible with a stream of gliders on just a single lane, with gliders separated by at least 90 ticks. Unlike in the 0hd Demonoid where gliders could follow each other as closely as 15 ticks apart on the construction lane, a single-channel recipe can be safely reflected by a Snark reflector, or even a syringe followed by signal-splitting Herschel circuitry.
This was a really radical simplification. Any spare glider output in any Herschel circuit with 90-tick recovery time could now be set up to function as a construction arm, with the addition of a single block anywhere along the output lane.
24) Pan-directional construction elbows An idea that began its development in the 10hd and 0hd Demonoids has been almost fully realized in recent single-channel libraries of elbow operations: recipes are now known that can send a glider or spaceship directly from the construction elbow in any of eight directions. The first use was in a Snark-chain-constructing triple wickstretcher. Two of these directions are used in the single-channel Demonoid. First, as in the wickstretcher, 0-degree gliders are send ahead of the construction elbow to build a Snark reflector exactly on the construction lane, as a lossless elbow. This allows the construction arm to reach around two corners instead of one, to build the next copy of the constructor/reflector. Second, backward LWSSes and MWSSes are fired from the same construction arm after the temporary Snark is removed, to destroy the previous constructor/reflector and complete the spaceship.
25) Orthogonoid spaceship
In June 2017 the first self-constructing spaceship with a slow orthogonal direction of travel was completed, using streams of MWSSes to store construction data instead of streams of gliders. It makes use of a temporary lossless elbow in its construction arm. Removing the Snark elbow allows the construction arm to function inexpensively as a destruction arm, at 90 degrees from its original direction of operation.
26) Hydra
In November 2017, Oscar Cunningham completed (+/-2sL) a single-channel self-constructing pattern called "Hydra", due to its ability to grow new "heads" at the corners of an expanding spiral pattern. Hydra is fairly similar to the 2017 spiral-growth pattern, but instead of adding an inline lossless elbow (a Snark) at every construction cycle, the Hydra adds a lossless glider splitter at the end of every active signal branch, creating more and more signal branches over time.
27) Quadratic-Growth Replicator
Adam Goucher's 0E0P metacell achieves quadratic growth as a by-product of its metacell functionality, by emulating an appropriate Life-like cellular automaton. The "ground state" for this very large unit cell is empty space, meaning that each set of megacells must create new neighboring copies of their entire structure and construction-recipe data, at every location where a birth is required. As a result, the 0E0P metacell is one of the largest Conway's Life structures ever assembled, and even though it was designed to be as "HashLife-friendly" as possible, Golly is not currently capable of simulating it through a complete cycle in any reasonable amount of time.
28) Strict Volatility-1 Oscillator
Self-constructing (and -destructing) mechanisms can easily produce an oscillator of any sufficiently high period, where every cell turns OFF at some time during the cycle. A first attempt to build one of these used freeze-dried slow salvos to shoot down and then rebuild reflector/constructors at each of four corners of a large diamond. Each freeze-dried salvo seed is activated by a single glider, to produce the entire destruction salvo, followed by the reconstruction salvo.
29) Self-Constructing Camelship
Chris Cain built a (3,1) camelship using as a template a later version of the volatility-1 oscillator (without the freeze-dried slow salvos).
30)Loopship The loopship is the first self-constructing spaceship that contains a construction recipe to build a memory loop big enough to hold that same construction recipe. The Geminis, Demonoids, or Orthogonoids all just reflect a recipe back and forth between two universal constructors. Here the idea is to "catch and release" the recipe instead. The loopship cheats a little bit by re-using some of the corner circuitry for multiple glide-reflected copies of the memory loop. A recipe capable of building a memory loop for itself in empty space, with no glide-reflect tricks or scaffolding, will be needed to complete a simpler quadratic-growth replicator (see below), self-synthesizing spaceship, RRO, or other similar structures.
31)Remini
The "Remini", or "retro Gemini", is an experimental self-constructing puffer assembled by Michael Simkin in April 2019. It uses the same single-channel/slow-salvo construction mechanism as the 0E0P metacell (see above), but it is built from classic period-30 circuitry instead of stable Spartan circuits. The presence or absence of gliders in an intermittent p30 stream turns out to be enough to allow for universal control of a construction-arm elbow. The Remini is an implementation of modern single-channel construction methods using components available in the 1970s.
32)Oblique Loopship and RRO
Constructed by Goldtiger997 -- Pattern of the Year for 2021.
33)Smaller Faster Quadratic Growth
Pavel Grankovskiy used single-channel construction arms to build a quadratic-growth replicator in Conway's Life, small and simple enough (at least relative to the 0E0P metacell!) that Golly can successfully run it through multiple cycles.
34) QuickSilver Demonoid
To be continued --
