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