Conway's Life: Work in Progress

Miscellaneous topics in Conway's Game of Life -- unfinished projects of all kinds and conditions

12 June 2016

New spaceship speed: 3c/7

Tim Coe has found a symmetrical spaceship with a new speed, 3c/7 (left, below) after a series of searches that took a total of "one or two months". At 29 cells wide, it is the minimum width odd symmetric spaceship -- an exhaustive width 27 search was run some time ago by Paul Tooke. The author seems to have officially chosen a name of "Spaghetti Monster" for the new 3c/7 spaceship.

Matthias Merzenich has pointed out that two of these spaceships can support a known 3c/7 wave (right, below).


Code: Select all
#C 3c/7 FSM spaceship: Tim Coe, 11 June 2016
#C Period-28 3c/7 wave found by Stephen Silver on Feb. 2, 2000
x = 187, y = 139, rule = B3/S23
10bo7bo65bo7bo$8b2ob2o3b2ob2o61b2ob2o3b2ob2o$8b2ob2o3b2ob2o61b2ob2o3b
2ob2o73bo7bo$11b2o3b2o67b2o3b2o74b2ob2o3b2ob2o$7bo5b3o5bo59bo5b3o5bo
70b2ob2o3b2ob2o$7bo13bo59bo13bo73b2o3b2o$8bo11bo61bo11bo70bo5b3o5bo$9b
2o7b2o63b2o7b2o71bo13bo$6bobobobo3bobobobo57bobobobo3bobobobo69bo11bo$
6bobob2o5b2obobo57bobob2o5b2obobo70b2o7b2o$6bobo11bobo57bobo11bobo67bo
bobobo3bobobobo$164bobob2o5b2obobo$11bo5bo67bo5bo72bobo11bobo$10b2o5b
2o65b2o5b2o$8b2o9b2o61b2o9b2o74bo5bo$8bo3bo3bo3bo61bo3bo3bo3bo73b2o5b
2o$10bo2bobo2bo65bo2bobo2bo73b2o9b2o$10bobo3bobo65bobo3bobo73bo3bo3bo
3bo$9bo9bo63bo9bo74bo2bobo2bo$7bo3bo5bo3bo59bo3bo5bo3bo72bobo3bobo$6b
4o9b4o57b4o9b4o70bo9bo$4b2obo2bo7bo2bob2o53b2obo2bo7bo2bob2o66bo3bo5bo
3bo$4b2o2b3o7b3o2b2o53b2o2b3o7b3o2b2o65b4o9b4o$7bobo2bo3bo2bobo59bobo
2bo3bo2bobo66b2obo2bo7bo2bob2o$5bob3o2bo3bo2b3obo55bob3o2bo3bo2b3obo
64b2o2b3o7b3o2b2o$5bo4bo7bo4bo55bo4bo7bo4bo67bobo2bo3bo2bobo$163bob3o
2bo3bo2b3obo$6bo15bo57bo15bo66bo4bo7bo4bo$6b2obo9bob2o57b2obo9bob2o$5b
o3b2o7b2o3bo55bo3b2o7b2o3bo66bo15bo$164b2obo9bob2o$5b2o4bo5bo4b2o55b2o
4bo5bo4b2o65bo3b2o7b2o3bo2$8b2ob2o3b2ob2o61b2ob2o3b2ob2o68b2o4bo5bo4b
2o$2bo5b2o3bobo3b2o5bo49bo5b2o3bobo3b2o5bo$bob2o5bobo3bobo5b2obo47bob
2o5bobo3bobo5b2obo64b2ob2o3b2ob2o$2o2bo3b2obo5bob2o3bo2b2o45b2o2bo3b2o
bo5bob2o3bo2b2o57bo5b2o3bobo3b2o5bo$2bob2ob6o3b6ob2obo49bob2ob6o3b6ob
2obo58bob2o5bobo3bobo5b2obo$7bo2bobo3bobo2bo59bo2bobo3bobo2bo62b2o2bo
3b2obo5bob2o3bo2b2o$4bobo2bo9bo2bobo53bobo2bo9bo2bobo61bob2ob6o3b6ob2o
bo$2b3o3bo11bo3b3o49b3o3bo11bo3b3o64bo2bobo3bobo2bo$2b3obobo11bobob3o
49b3obobo11bobob3o61bobo2bo9bo2bobo$3b3o17b3o51b3o17b3o60b3o3bo11bo3b
3o$160b3obobo11bobob3o$4bo19bo53bo19bo62b3o17b3o$2b2o21b2o49b2o21b2o$b
obo21bobo47bobo21bobo60bo19bo$b3o21b3o47b3o21b3o58b2o21b2o$159bobo21bo
bo$b2o23b2o47b2o23b2o57b3o21b3o$b3o21b3o47b3o21b3o$4bo4b3o5b3o4bo53bo
4b3o5b3o4bo60b2o23b2o$9bo2bo3bo2bo63bo2bo3bo2bo65b3o21b3o$2bobo4bo9bo
4bobo49bobo4bo9bo4bobo61bo4b3o5b3o4bo$3bo7b2o3b2o7bo51bo7b2o3b2o7bo67b
o2bo3bo2bo$6b5o7b5o57b5o7b5o63bobo4bo9bo4bobo$5b4o11b4o55b4o11b4o63bo
7b2o3b2o7bo$4b2o17b2o53b2o17b2o65b5o7b5o$6bob2o9b2obo57bob2o9b2obo66b
4o11b4o$5bob2obo7bob2obo55bob2obo7bob2obo64b2o17b2o$7b5ob3ob5o59b5ob3o
b5o68bob2o9b2obo$2b3o2b2o2b2o3b2o2b2o2b3o49b3o2b2o2b2o3b2o2b2o2b3o62bo
b2obo7bob2obo$4bo2b2o2b2obob2o2b2o2bo53bo2b2o2b2obob2o2b2o2bo66b5ob3ob
5o$3bo3b2o2b3ob3o2b2o3bo51bo3b2o2b3ob3o2b2o3bo60b3o2b2o2b2o3b2o2b2o2b
3o$3bo5bobob3obobo5bo51bo5bobob3obobo5bo62bo2b2o2b2obob2o2b2o2bo$3bo3b
5o5b5o3bo51bo3b5o5b5o3bo61bo3b2o2b3ob3o2b2o3bo$4bo3b2o9b2o3bo53bo3b2o
9b2o3bo62bo5bobob3obobo5bo$11bo2bo2bo67bo2bo2bo69bo3b5o5b5o3bo$11b2o3b
2o67b2o3b2o70bo3b2o9b2o3bo$13bobo71bobo79bo2bo2bo$169b2o3b2o$8b3o7b3o
61b3o7b3o76bobo$7bo3b2o3b2o3bo59bo3b2o3b2o3bo$8bo11bo61bo11bo71b3o7b3o
$8bo4bobo4bo61bo4bobo4bo70bo3b2o3b2o3bo$7bobobo5bobobo59bobobo5bobobo
70bo11bo$7bo3bo5bo3bo59bo3bo5bo3bo70bo4bobo4bo$7b2o3bo3bo3b2o59b2o3bo
3bo3b2o69bobobo5bobobo$11bo5bo67bo5bo73bo3bo5bo3bo$9bo9bo63bo9bo71b2o
3bo3bo3b2o$9b2o7b2o63b2o7b2o75bo5bo$10bo7bo65bo7bo74bo9bo$167b2o7b2o$
168bo7bo$9b3o5b3o63b3o5b3o$9b2o7b2o63b2o7b2o$8bo3bo3bo3bo61bo3bo3bo3bo
72b3o5b3o$9bo3bobo3bo63bo3bobo3bo73b2o7b2o$13bobo71bobo76bo3bo3bo3bo$
11bo5bo67bo5bo75bo3bobo3bo$171bobo$11b3ob3o67b3ob3o77bo5bo$11b2obob2o
67b2obob2o$9bobo5bobo63bobo5bobo75b3ob3o$8bob2o5b2obo61bob2o5b2obo74b
2obob2o$8bo11bo61bo11bo72bobo5bobo$7bo2b2o5b2o2bo59bo2b2o5b2o2bo70bob
2o5b2obo$8b2o9b2o61b2o9b2o71bo11bo$7bob2o7b2obo59bob2o7b2obo69bo2b2o5b
2o2bo$9b2o7b2o63b2o7b2o72b2o9b2o$6bo15bo57bo15bo68bob2o7b2obo$6b2o3bo
5bo3b2o57b2o3bo5bo3b2o70b2o7b2o$6b3o2bo5bo2b3o57b3o2bo5bo2b3o67bo15bo$
7bo13bo59bo13bo68b2o3bo5bo3b2o$9b2ob2ob2ob2o63b2ob2ob2ob2o70b3o2bo5bo
2b3o$10bob2ob2obo65bob2ob2obo72bo13bo$9b2ob2ob2ob2o63b2ob2ob2ob2o73b2o
b2ob2ob2o$10bo7bo65bo7bo75bob2ob2obo$10bobobobobo65bobobobobo74b2ob2ob
2ob2o$10bo7bo65bo7bo75bo7bo$168bobobobobo$8bo4bobo4bo61bo4bobo4bo7bo7b
o7bo7bo41bo7bo$8bo3bo3bo3bo61bo3bo3bo3bo6b3o5b3o5b3o5b3o$7b2obo7bob2o
59b2obo7bob2o4bo2b2o3b2o2bo3bo2b2o3b2o2bo5bo7bo7bo7bo7bo4bobo4bo$8bob
2o5b2obo61bob2o5b2obo4b2o2b2o3b2o2b2ob2o2b2o3b2o2b2o3b3o5b3o5b3o5b3o6b
o3bo3bo3bo$6bob3o7b3obo57bob3o7b3obo2b2o2b3ob3o2b2ob2o2b3ob3o2b2o2bo2b
2o3b2o2bo3bo2b2o3b2o2bo4b2obo7bob2o$5bo17bo55bo17bob3o9b3ob3o9b3ob2o2b
2o3b2o2b2ob2o2b2o3b2o2b2o4bob2o5b2obo$12bo3bo69bo3bo9b2o9b2o3b2o9b2o2b
2o2b3ob3o2b2ob2o2b3ob3o2b2o2bob3o7b3obo$11bobobobo67bobobobo39b3o9b3ob
3o9b3obo17bo$7b3o3bobo3b3o59b3o3bobo3b3o36b2o9b2o3b2o9b2o9bo3bo$7b4obo
3bob4o59b4obo3bob4o73bobobobo$9b2o7b2o63b2o7b2o71b3o3bobo3b3o$7bob2o7b
2obo59bob2o7b2obo69b4obo3bob4o$6b2ob2o3bo3b2ob2o57b2ob2o3bo3b2ob2o70b
2o7b2o$5b2o2b2o2bobo2b2o2b2o55b2o2b2o2bobo2b2o2b2o67bob2o7b2obo$8b3obo
3bob3o61b3obo3bob3o69b2ob2o3bo3b2ob2o$5b5o2bo3bo2b5o55b5o2bo3bo2b5o65b
2o2b2o2bobo2b2o2b2o$4bo7b2ob2o7bo53bo7b2ob2o7bo67b3obo3bob3o$4bo3b2o3b
obo3b2o3bo53bo3b2o3bobo3b2o3bo64b5o2bo3bo2b5o$4bobo2bo3bobo3bo2bobo53b
obo2bo3bobo3bo2bobo63bo7b2ob2o7bo$11b3ob3o67b3ob3o70bo3b2o3bobo3b2o3bo
$7b3ob3ob3ob3o59b3ob3ob3ob3o66bobo2bo3bobo3bo2bobo$13b3o71b3o79b3ob3o$
13b3o71b3o75b3ob3ob3ob3o$171b3o$11bo5bo67bo5bo79b3o$11bobobobo67bobobo
bo$169bo5bo$169bobobobo!
#C [[ AUTOFIT AUTOSTART GPS 4 ]]

This is the twenty-second spaceship velocity constructed in Conway's Life -- counting each of the four infinite families of spaceships (Gemini, HBK, Demonoid, Caterloopillar) as one velocity each.

10 March 2016

New c/10 "copperhead" spaceship

Reposted with permission from Alexey Nigin's blog:

The day before yesterday (March 6, 2016) ConwayLife.com forums saw a new member named zdr. When we the lifenthusiasts meet a newcomer, we expect to see things like “brand new” 30-cell 700-gen methuselah and then have to explain why it is not notable. However, what zdr showed us made our jaws drop.

It was a 28-cell c/10 orthogonal spaceship:

An animated image of the spaceship

To explain why this is such a groundbreaking discovery, I should first tell you that Life spaceships can be loosely divided into two categories. Engineered ships are the ones that consist of various small components. They often have adjustable speed. However, the population of tens of thousands to millions of cells causes these spaceships to have no practical value.

There is much more incentive in hunting for elementary spaceships, which can be used for complex constructions. They are found using programs such as gfind or WLS. The algorithms behind these programs are beyond the scope of my article, but the important thing is that the search time goes up exponentially as the period of the ship grows. It is most interesting to find spaceships of new speeds, and the number of speeds that low-period ships can have is unfortunately limited:

Orthogonal Diagonal
c/2 Yes Impossible
c/3 Yes Impossible
c/4 Yes Yes
c/5 Yes Yes
2c/5 Yes Impossible
c/6 Yes Yes
c/7 Yes Yes
2c/7 Yes Impossible
3c/7 No Impossible
c/8 No No
3c/8 No Impossible
This table does not include oblique speeds, which causes little inconvenience because no elementary oblique ships are known.

The table above shows that ships exist for most of possible speeds, and it seems obvious that the speeds for which there are no ships have been searched by numerous people with good knowledge of search programs, powerful computers and lots of patience. As for higher periods, even the smallest searches would take years on modern computers. It appears that low-hanging fruit have been harvested clean during the 46 years of Life research… or, more precisely, it appeared so before zdr’s post.

The idea we all missed is that if the ship is really microscopic, it can be found in reasonable time despite its high period. After zdr boldly went where no man has gone before, Josh Ball set up the corresponding search in gfind and refound the spaceship in a little over an hour. zdr said that their program found it in a matter of 19 seconds.

To be frank, similar event did happen before when the aforementioned Josh Ball pulled loafer out of a hat. However, zdr’s spaceship (which is now called Copperhead, as proposed by muzik) is much more awesome for a number of reasons:
  • Loafer is not so mind-bogglingly high-period.
  • Copperhead was much easier to find, so it is more surprising that nobody found it before.
  • Copperhead’s tail is relatively strong and can interact with other objects without breaking down.

The discovery of a new spaceship speed immediately opened a few new areas of research, which are being explored now.

Synthesis

Aidan F. Pierce came up with a Copperhead synthesis only 10 hours after the completion of the spaceship. The synthesis was inefficient, and a few people discovered better ones. The current best synthesis, made by Chris Cain, requires only 22 gliders. Its repeat time is 375 ticks, which means that a gun can start constructing the second spaceship 375 ticks after the first one. There is a 23-glider synthesis with a better repeat time of 373 ticks.

Incremental 22-glider synthesis of the copperhead

The synthesis can be substantially improved if we find this spaceship crawling out of a random soup. Adam P. Goucher has written a wonderful program called apgsearch, which is perfectly suited for this task. While the current version may be too slow to find a soup in reasonable time, highly anticipated version 3.0 can probably do the trick. Once it is found, it will appear here.

Guns

Once the synthesis was complete, building a gun was nothing but corollary-sniping. The first copperhead gun was created by myself, and a video of it is available here. It was put together in a hurry and is therefore extremely inefficient. In particular, skilled gun builders can spot a silly mistake in the Northeast.

gmc_nxtman then made another gun with an almost optimal period of 376 ticks.

Eaters

simeks found two eaters for this ship, the better of which is shown below:

A copperhead eater

It is now time to search for a good copperhead-to-something-useful converter. The only existing one is clumsy and slow.

Sawtooths

Sawtooths often work by sending a flotilla of fast ships towards a slower ship. The more is the difference in speed, the less is the expansion factor of a sawtooth. Since expansion factor is proportional to how boring the sawtooth is, increasing the speed difference is a good thing. Dean Hickerson collided c/2 standard spaceships with c/10 copperhead to get a sawtooth with expansion factor 6:

Hickerson's sawtooth

He then made another sawtooth with expansion factor 10/3.

Puffers and rakes

Suppose a c/10 flotilla is hit by a glider. The glider turns into loads of mess, but all copperheads somehow survive and move on. The mess releases a glider, which flies into strategically placed second flotilla that is identical to the first one. Gliders continue to bounce back and forth between flotillas leaving mess behind them, and a c/10 puffer is complete!

Unfortunately, this cool technique doesn’t work out easily in our case. There are no interesting interactions between a glider and a single copperhead, and it is unclear how one can place two or more copperheads so close to each other that a glider interacts with all of them. Assuming we figure it out, we can try to make a rake by perturbing the mess with copperheads so that it evolves into gliders, but that seems even less likely.

However, all this hand-waving can be turned it real puffers if we find…

Tagalongs

Tagalongs are small things that are attached to the back of a spaceship and move with it. Here is an example tagalong, called the Schick engine:

Schick engine pulled by two LWSSs

Finding a tagalong for the copperhead (or two copperheads) will be really nice. We can also try searching for pushalongs, but they are generally rarer.

Other patterns

There are a few other areas of Life exploration where the copperhead can be useful. For example, universal constructors often need to create an elbow still life very far away. It can be done by producing a copperhead, waiting for some time, and then shooting the copperhead down with a LWSS. At the moment I do not see why the copperhead can be better than the loafer in this aspect, but who knows?

17 June 2014

New Wrinkles in the Slow-Salvo Construction Game

Slow-salvo constructions are starting to gain some traction as more uses are found for them. Most recently, a (6,3) knightship has been built in Conway's Life using a small synchronized glider salvo that activates long chains of half-bakeries, which cooperate to create a slow salvo that then re-creates the synchronized gliders at the correct offset. (See item #15 below.)

sample slow salvo
Slow salvo from 31c/240 spaceship project
-- 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 #20.

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) 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.

10) 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.

11) 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 September 2015 no explicit example has been completed.

12) Spiral Growth
A spiral-growth pattern has been constructed using four copies of a single-arm universal constructor.

13) 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.

14) 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.

15) 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.

16) Quadratic-Growth Replicators
It appears to be possible to use slow-salvo constructions as part of a quadratic-growth replicator in Conway's Life, small enough that Golly can successfully run it through multiple cycles. A diamond-shaped design looks likely to be workable, but at present only the very early design stages are complete.

17) 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.

18) 'Engineless Caterpillar' 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, still under construction, 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.

19) (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.

20) 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.

26 November 2013

New Technology from the Replicator Project

Now that the Conway's Life replicator pattern is in working order, what might the next step be?

The phase-shifted linear replicator isn't really a very satisfactory design. Each parent pattern can produce only one child pattern, which then blocks it from any further replication. It seems as if a quadratic-growth, space-filling replicator would be much more in keeping with von Neumann's (and Conway's) original purpose.

One major limitation of essentially linear designs like the Gemini spaceship and Geminoid replicator is that replication and movement perpendicular to the long stream of gliders is fairly easy, but it's very hard to make a new copy in the other direction -- just because it means constructing the far end of the new copy millions of cells away.

It's certainly not impossible to reach that far out into empty space with a constructor arm, but it's bound to be very slow -- either in terms of the absolute number of ticks, or in the amount of time that it takes to simulate a construction cycle. Even Golly's Hashlife algorithm has difficulty with very long streams of information-carrying gliders traveling next to each other in opposite directions -- the number of combinations goes up exponentially, and beyond a certain point no reasonable amount of memory can hold all the different hashtiles.

Luckily it may be possible to solve both of these problems at once with a diamond-shaped replicator. The memory loop would travel around the outside of a hollow square.

Hand blocks (or elbow blocks, if the UCs at the corners have two arms) can be trivially constructed in the correct starting locations by colliding LWSSes from one corner with gliders from an adjacent corner; glider pairs or slow salvos following the first glider will immediately have a target to work with.

To give Hashlife as much help as possible, it will make sense to adjust the reflection timings at the four corners so that the memory loop takes 2^N ticks per cycle; the spatial periodicity should also be a power of two.

The result will be a space-filling Life replicator with the same quadratic growth rate as Langton's Loops. It will be interesting to see how much memory will be needed to allow Golly to "run away" with the replicator simulation.

In the diagram at right, blue diamonds represent glider memory loops containing construction information. (A closed loop may not actually be needed, but that's another story.) Green objects are universal constructors and reflectors. The yellow arrows are eater groups that can absorb child replicators' attempts to build on top of a quiescent parent replicator. The white lines show the paths of starter LWSSes and construction gliders. The red numbers show replicators' generation number.

The New Technology

A number of the new construction and destruction mechanisms from the Geminoid project may be useful here:

12 January 2013

Replicator Redux

The Story So Far

Self-replication in Conway's Life has been a topic for discussion and research from the very beginning, over forty years ago now (!). The original purpose of Conway's Life was to find a simplification of John von Neumann's self-replicating machine designs, which used a CA rule with 29 states. A couple of non-constructive universality proofs for B3/S23 Life were completed very early on, though they were never published in detail -- and my sense is that actual self-replicating patterns along the lines of these proofs would require something on the order of a planet-sized computer and a geological epoch or two to simulate a replication cycle.

The technology to build a Conway's Life replicator out of stable parts has been available since at least 2004. A working pattern could certainly have been put together in a few years by a full-time Herschel plumber, with a high-energy glider physicist or two as consultants. But unfortunately there seem to be very few multi-year grants available for large-scale CA pattern-building -- even for such obviously worthwhile Holy-Grail quests as this one!

In 2009, Adam P. Goucher put together a working universal computer-constructor that could be programmed to make a complete copy of itself. The pattern, however, is so huge and slow that it would have taken an enormous amount of work to program it to self-replicate -- it would have been easier to come up with a new replicator design from scratch. Clearly, in hindsight, everyone was waiting for something better to come along.

Lightning Strikes

In 2010, something better did come along: Andrew Wade's Gemini spaceship magically appeared on the scene, and things suddenly got much easier for would-be replicator designers. Self-constructing circuitry was no longer just a theoretical possibility but an accomplished fact -- and the Gemini made it look downright easy. Not that it was easy: Andrew Wade solved an impressive array of signal-crossing, synchronization and construction problems to make the Gemini fly.

The key insight was that it's much more efficient to store information about glider constructions directly in the distances between gliders. Previous efforts had tried to reduce complexity by relying on a limited instruction set of operations to operate a construction arm. Working examples can be found in Golly's Patterns/Life/Signal-Circuitry/constructor patterns.

But in these old prototypes, a lot of circuitry was needed to convert the coded instructions into the glider salvos that manipulate the construction elbow -- so the total size of self-constructing circuitry plus construction data was still very large. To build the Gemini, Wade borrowed the old construction arm with very few alterations, but took the radical step of simply throwing away most of the decoding circuitry (!).

Instead, he ran the Gemini's construction elbows directly with streams of gliders: if a glider was needed on lane L at time T, then there would be a glider in the Lane L data stream timed to produce a copy at the right spacetime location -- automatically, with no extra synchronization circuitry needed.

... It's actually a little more complicated than that -- most of the guns at the prototype construction-arm "shoulder" produce not single gliders but pairs of synchronized gliders. Sometimes two of these salvo shotguns combine to put gliders close behind each other on the same lane. This would not be possible if the Gemini had a separate channel for each glider lane, and the reflector arrays would have had to be even longer -- eighteen channels instead of twelve.

Still, the basic idea was there. The Gemini showed how to store precise timings for glider collisions on a linear data tape, and transfer that information efficiently to the construction area.

Limitations and Possibilities

However, a Gemini spaceship is not a replicator, any more than a glider or other small spaceship is! A replicator is a pattern that makes copies of itself: the total number of copies of the pattern has to increase over time. If a pattern is "used up" in some way by the copying process, and is not capable of completing another cycle of replication after the first, then to be a true replicator it would have to produce two or more children simultaneously. Otherwise the pattern falls into some other category.

Because there is only ever one primary copy of the glider streams that carry the construction data, a pair of Gemini replicator units can be programmed to produce an extremely slow puffer or a self-constructing spaceship, but can't make a complete copy of the entire Gemini pattern. Some new circuitry will have to be added to make a Geminoid design into a true replicator.

The twelve parallel channels and many signal crossings in the original Gemini spaceship would have made rewiring it into a replicator fairly difficult. New Geminoids have only a single channel and no signal crossings. It should be relatively trivial to duplicate the construction recipe into a new copy of the pattern, and also keep the old copy if necessary, to make a true replicator rather than a self-constructing spaceship.

What Counts As A Replicator, Anyway?

There are several possible types of Geminoid replicator. One of the easiest would be a one-dimensional parity-rule replicator. This is by far the most common type of natural replicator in Lifelike rules, and can be adapted to a Geminoid design by building in a self-destruct mechanism that is triggered by the presence of a neighbor pattern.

The only unsatisfactory thing about parity-rule replicators is their sawtooth growth pattern: eventually the population will exceed any given N, but it will also periodically return to a small constant value -- often just two replicators, or four. This doesn't quite match the standard vision of a replicator that copies itself relentlessly and eventually fills all available space, with a steadily growing population.

Another fairly straightforward category is a simple one-dimensional linear growth replicator. Each parent replicator will produce exactly one child pattern, which will then block the parent from making further copies of itself while constructing the next replicator in a growing line. If the parent pattern repeatedly returns to its initial state -- so it's still perfectly capable of making another copy of itself if its child pattern is removed -- it fits the technical definition of a replicator. This is a good design to start with, not least because no self-destruct circuitry is needed!

In the longer term it should be possible to design a Geminoid-based replicator with some form of exponential population growth in a two-dimensional pattern, similar for example to Langton's Loops. This will have to be a much larger pattern, however. Gemini-like long narrow designs, with replication going on simultaneously at both ends, doesn't allow for easy construction of right-angle copies. A diamond-shaped version, with many back-and-forth reflections of the data tape, will probably be needed instead. So this is something to work up to gradually!

Radical Reductions, Continued

In the summer of 2010, with the Gemini for inspiration, Paul Chapman wrote a search utility to find a simpler set of elbow instructions -- the Gemini's minimal elbow-move instruction set involved salvos of three or four gliders on six possible lanes, performing just four operations -- INC, DEC, BLACK, and WHITE (the last two refer to the color of the emitted construction glider). Reducing the number of lanes cuts down enormously on the amount of synchronization circuitry. There turned out to be a wealth of possibilities using sets of three gliders on three glider lanes, and plenty of options to choose from even with just a pair of synchronized gliders on two lanes.

My last post on this weblog describes some Geminoid designs that are much more compact than the original Gemini spaceship. Below is a variant with a single construction arm, and no self-destruct circuitry: it's perfectly possible to do all the cleanup with "software" -- more gliders in the same input channel, after the construction of the new replicator unit is all finished, which bend the Geminoid's single arm in the other direction to clean up the previous replicator unit.

It's even possible to program the constructor arm to build a constellation that can be triggered by a single glider to generate a huge cleanup "meteor shower". So the very last input to a replicator unit would generate a signal that would destroy that same replicator unit, completely and immediately. (In the current design, the Gemini's destructor arm cleans up an old empty replicator unit left over from the previous construction cycle.)

two prototype Geminoid replicator units
two copies of a prototype Geminoid replicator unit --
normally these would be separated by a long distance diagonally.
Click on the image to get the pattern file; larger image here.

I've posted some of these prototypes on a "Geminoid Challenge" thread in the conwaylife.com forums, and am slowly working on more efficient variants.

The other half of this project involves finding more efficient ways to construct Geminoid circuitry using just a single construction arm. An arm run by glider pairs turns out to be much more versatile than the old prototype four-instruction arm. Not only are there many more INC and DEC operators available, but it's also possible to find efficient recipes for a number of other useful actions: turn one elbow into two, use the second elbow for a while and then delete it, create debris off to the side of an elbow to make one or more new "hand" target blocks, build an LWSS directly or indirectly and then collide it with a glider to produce a new hand a long distance away -- and so on. I'll be posting samples of these new "elbow recipes" in the Geminoid Challenge thread.

03 November 2012

Resurrection

I don't believe that there has yet been an official announcement (except for a minor footnote) that the entire pentadecathlon.com site is now irrevocably defunct. As such, Dave Greene suggested that we relocate LifeNews by merging it with Conway's Life: Work in Progress. There is going to be a programme of archiving the old LifeNews entries and making them available somewhere on the Internet.

Until then, the LifeNews triumvirate humbly apologises for any inconvenience.