Conway's Life: Work in Progress

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

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


I don't believe that there has yet been an official announcement (except for a minor footnote) that the entire 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.

21 December 2010

Geminoid Research

Since Andrew Wade built his amazing Gemini spaceship out of miscellaneous scraps from the Conway's Life junkyard (a feat somewhat equivalent to assembling a jet airplane out of Model T parts) I've been looking at possible ways to simplify the design. With a lot of help from Paul Chapman this summer, I think I'm finally making some progress.

Here's a diagram of a possible Geminoid replicator unit. The original Gemini's base units are about 3750x4700, with about 16,000 live cells. This version fits into 580x540, with less than two thousand ON cells. In place of the Gemini spaceship's twelve input channels, there is now just a single stream of gliders. Four channels are encoded in the stream, two channels for each construction arm. Click on the image to the right to see how multiple copies of this unit will fit together.

There is no destruction arm in this design, and that's definitely its biggest weakness; I have quite a bit of programming left to do to produce a search utility that can "seed" the empty spaces between the signal channels with still lifes that will cause a chain reaction that destroys the entire replicator unit. The reaction will be triggered by a single glider coming from the construction site at the intersection of the two arms. It's easy enough to come up with a collection of still lifes that will do this; the trick is to find a set that's reasonably close to minimal. My current goal is to find SODs (Seeds Of Destruction) that no more than double the original population.

The other item that needs special explanation is the encoding of four channels into one, and the special limitations placed on the construction-arm salvos by that architecture.

The original Gemini had twelve parallel channels corresponding to the four glider lanes that were used to construct the various salvo combinations that acted on the elbow to produce INC and DEC movements and fire EVEN and ODD gliders. The four-glider-lane shoulder architecture was taken from Paul Chapman's prototype universal constructor -- but the prototype was "the first thing that worked" and pretty far from optimal.

It turns out to be very easy to find sets of three lanes where combination salvos (one or more sets of one, two, or three synchronized gliders) will produce all the necessary INC/DEC/ODD/EVEN operations. Once you allow multiple "cycles" -- two or three sets of synchronized gliders, not just one set -- it's even possible to cut the number of lanes down to two, or even just one (!) These construction-elbow manipulation salvos are all the work of Paul Chapman and a custom search utility he wrote in the summer of 2010.

It seems amazing that there's a universal set of operations at all using a single glider lane. But with pairs of synchronized gliders on a the same lane there are dozens of operations available. Many of them need five cycles instead of three or four, but considering the minimal highway width that's not much of a handicap.

The lane set I chose for a redesigned Geminoid spaceship -- pairs of gliders on lanes -5 and 4, separated by 9 cells -- has the advantage of being completely symmetrical, meaning that LEFT and RIGHT gliders can be fired equally well just by using a mirror-image salvo. This will come in handy when it's time to trigger the destruction of the old copy of the Geminoid... Also, glider inserters are available that leave the lane nine cells away completely unaffected when placing a glider, so all possible glider sets are trivially constructible.

Run the pattern in the "Geminoid replicator unit" link, and advance or delay some of the gliders in the first cycle (set of four). The corresponding output gliders will be advanced or delayed by the same amount with no ill effects -- unless the distance between any two adjacent gliders drops below 497 ticks.

The unusual feature of this operation set is that gliders are required on both lanes for each cycle of each operation. The single channel is decoded into four channels with a simple set of parallel period quadruplers, which allows the decoder to be completely asynchronous -- but it means that leaving out a glider would have disastrous consequences for the decoding process. Thus there will have to be extensive use of NOP operations (in this case, four pairs of gliders that have no net effect on the construction-arm elbow). It's also quite likely that all the operations the Geminoid uses will be exactly four cycles in length, but this isn't quite necessary for all cases.

07 February 2009

First complete glider-to-Cordership converter

For years now I've been fruitlessly plotting to put together a Herschel layout utility for Golly, to help design multi-glider shotguns and other large-scale Herschel signal circuitry. One of my first uses for the utility will be to design a (relatively) compact Cordership gun that can be triggered by a single input glider.

It seems Calcyman has finally gotten tired of waiting for this wondrous device to appear, so he has built one himself: the world's very first complete glider-to-Cordership converter! (The link goes to the RLE pattern file; here's the MCell version.)

Input gliders at the lower left are converted into clean 3-engine Paul Tooke Corderships in 13,311 ticks -- as long as no two gliders are closer together than 708 ticks. The signal is split into three main parts. The one in the center triggers an improved Herschel-to-swimmer converter using a new 5-glider recipe (see my last post for the old 6-glider solution.)

The new reaction [RLE / MCL] uses the usual four gliders to create a switch engine, but a modified Fx119 Herschel circuit allows a single glider to suppress all the extra junk the switch engine creates, until it has moved far enough forward to pick up the swimmer track.

The other two signals trigger two mirror-symmetric Cordership-wing constructors. Each of these builds a new switch engine next to the original swimmer, which then replaces the swimmer-lane support structure on that side. Once both wings are in place, the swimmer becomes the central engine of a free-flying Cordership.

I'm working on tightening up this pattern somewhat; Calcyman's new suppression reaction disposes of glider #1 from the old H-to-S, but the embarrassing #6b is still in there. The wing constructors use parts from an old universal shotgun-building toolkit, which tends to produce fairly large and sprawling patterns -- so it may make sense to adjust these at the same time.

[Further bulletins as events warrant.]

17 June 2007

A New Kind of Signal (though not a useful one yet)

This is a speculative project that has been in the works for a long time: an odd-period Herschel loop that includes a switch-engine stage. I wanted to see what David Bell's "swimmers" looked like when incorporated into a stable Herschel track. The current version isn't exactly pretty, but it does work. Here's the RLE pattern file.

What Went Wrong This Time?

The center of this circuit is an extensible Herschel fanout device based on paired F171 conduits. Theoretically adding another synchronized signal is simply a matter of adding another pair of F171s to the beginning of the series, and running a Hersrch search to produce an appropriately-timed output. F171 is a relatively slow conduit, so you do get a little extra time for adjustments with each new pair.

But it turned out not to be enough; it gets increasingly hard to reach around the edges of the conduits that have already been placed. After using the last four outputs (circuits 6, 5, 4, and 3, working backwards -- the two ends of the F171 chains, and the two extensible tandem-glider outputs) it was impossible to route the previous tandem-glider signal around to get it where I wanted it fast enough. The signal could be hurried into the general neighborhood, but it didn't quite hit any of the spacetime locations I needed. I tried most if not all of the likely Herschel-to-glider converters that could produce either of the two gliders coming in from the southwest.

I should probably have tried simply skipping the output of one F171-pair and checking to see if 342 ticks was enough extra time to allow a connection from one link further back. Something to try next time around --

In this case, the failure of the extensible fanout meant that other types of Herschel fanout devices (circuits 1 and 2 in the labeled MCell "envelope" diagram at right) had to be bolted on instead, before the split that feeds the two F171 chains. This allowed plenty of time to route two signals around to feed the SW shotgun, though the design uses up a lot more space and the conversion takes longer.

As usual, the layout was done from the inside out, so to speak, with the H-to-G converters in the deepest part of the fanout tree "solved" first. Also as usual, toward the outer edges expert Herschel plumbers may detect hints of increasing impatience with high-level architectural issues...

Not Good Enough Yet

Unfortunately I'm going to have to rebuild the whole thing eventually, because of a mistake I made in the layout very early on. Basically I thought I had a clean way to get a Herschel to the northeasternmost H-to-G converter (circuit #6) in the right number of ticks, but there was a flaw in the only conduit that fit there: it worked only half the time (i.e., it needed a blinker as one of its suppressing catalysts, to keep the Herschel signal from interfering with other catalysts later on; otherwise it produced an extra blinker).

So to make this odd-period loop work, there's a huge extra Herschel conduit bolted on to the top of the converter (circuit 6b) to suppress the extra blinker. 6b is a large slow glider-to-Herschel converter -- this was the easiest way to get a spare Herschel out without changing the rest of the circuits.

The repeat rate of the full circuit was going to be up in the 600-tick range in any case, because of the boojum-transmitter adjustment I used in circuit #2... and because the swimmer-to-Herschel stage at the other end of the channel uses basically the same slow glider-to-Herschel mechanism, except it reflects an extra glider back to clean up a junk block.

In any case, two Herschels are doing the job of delivering the last glider to the northeast in the switch-engine recipe, where one Herschel should really be plenty... kind of spoils the whole construction. I'm not sure the idea of "elegance" really applies to these extended Herschel-track experiments -- but anyway it isn't quite up to my arbitrary standards for these things.

General notes on multi-Herschel constructions

Laying out these things is a balancing act between ridiculously large solutions and ridiculous amounts of time spent working out the bugs in more compact circuitry. It's easy to produce any glider timings you want, for example, if you leave enough space for a boojum-reflector timing adjustment on every signal path; known Herschel conduits can give you output gliders with any timing mod 8, relatively quickly (usually three or four conduits, sometimes two -- assuming the output lane is an reasonable distance ahead of the input Herschel.)

But when adjustments are necessary, it tends to affect the compression of the circuitry: if the adjusted boojum-reflected glider is sent into a tandem-glider transceiver, the repeat time will get worse the more the reflector is moved back. If the glider goes into a standard G-to-H, then you're immediately stuck with the repeat time of the G-to-H (currently I think this is still at least 497 ticks). Thus a "good" circuit design should probably try to avoid adjustable components -- ideally the signal-splitter outputs should be routed fairly directly toward their goals. Too bad it never actually seems to work that way...

Another Approach (that doesn't seem to work)

I'd also like to have one more look at the idea of using junk still-lifes or oscillators to keep the switch engine going in its early cycles, on the way from the construction site into the diagonal track. Currently two of the six gliders in the recipe just suppress the switch engine's exhaust, doing the same job that the boats do in the permanent track. A simple block, blinker, or beehive can do the same job, and get cleanly destroyed in the process; they can be placed any time after the initial construction gliders go by but before the switch engine hits the key spot with its exhaust.

#C Four gliders plus two blocks produce a 'swimmer'
#C -- the blocks must be placed after the gliders go past.
#C Theoretically Herschel-to-block converters might make this
#C as efficient as the six-glider version, but Herschel tracks
#C close to the swimmer lane tend to get in the way of
#C the incoming gliders; an all-glider solution was much easier.
x = 69, y = 71, rule = B3/S23

I spent a lot of time fiddling around with Herschel-to-junk converters a few months back, but discovered as usual that being able to adjust the timing of the suppressing signal -- i.e., building the suppressing junk at any of a moderate range of times during the construction -- wasn't worth losing the wider range of adjustability in the delivery location: when you're placing stationary junk you have to hit the right location exactly and you have to worry about the converter catalysts getting in the way, where with a glider you can place the H-to-G converter anywhere along the input diagonal.

Five Types of Interchangeable Signals

It seems a little odd that there aren't more kinds of asynchronous signal tracks by now. For tracks where converters to and from other signal types have been explictly constructed, we've got gliders, *WSSes, Herschels, 2c/3 diagonal wires, and now switch engines. How many have I left out? Even if we say that the tracks can contain low-period oscillators, I don't think there are very many more types (?)

I'd say that things like Caterpillar blinker trails and telegraph wires don't count (yet) because they move each time they're used, and nobody has bothered to set up a way to send a signal through only when an input comes in. Theoretically a telegraph could transmit information asynchronously, but not if it's being powered by high-period guns as in the current model (a signal is sent every cycle, but it's modified slightly depending on the input.)

I do have a rough design for an asynchronous telegraph that avoids sending ten pulses per signal (or a reverse signal) to reset the wire. But it would end up similar in size and latency to the current model, and at this rate it will be several years to never before that sees the light of day. Converters using Corderships or 2c/5 spaceships as signals would be at a similar order of size and level of effort.

Maybe someone can supply p15 converters to get a signal out of an orthogonal pi-heptomino track made of pentadecathlons --

#C pi-heptomino conduits: Dean Hickerson, 17 February 1997
#C Herschel-to-pi stage by Paul Callahan (part of Fx176)
x = 151, y = 75, rule = B3/S23

Getting the signal started is no problem, using a stable Herschel-to-pi stage, but I don't think anyone has found a good converter for the end yet. Should be possible to engineer a multi-stage one, at least, where some useful junk is destroyed and re-created. Obviously it would be p15 or p30, not stable, but it would still be fun to see a really big pi orbital working.

A Small Direct Converter (if wishes were horses)

When Brice Due was working on a revision of ptbsearch last year, I held out some hopes that a compact H-to-S (Herschel-to-swimmer) converter might happen show up, once the search code started keeping an eye out for "tamable" switch engines along with other more likely transients (Herschels, B-heptominos, R-pentominoes, and so forth.)

Come to think of it, one could also keep an eye out for transient patterns that could trigger a 2c/3 signal -- a direct H-to-2c/3 would save even more spaghetti wiring than an H-to-S would... though a direct 2c/3-to-H is probably a harder problem, maybe more something for a 'dr'-type search on a new supercomputer, or a distributed computing system.

Distributed Searches?

Periodically I try to work on finding a way to usefully distribute an exhaustive ptbsearch search (or dr or wls -- pick your poison). But so far I've more or less hit a wall and bounced off, every time. The most promising line of research seems to be finding a way to short-circuit repeated searches in one area, probably using hash tables and lots of RAM.

To make this a little less vague: you often notice that a search problem splits into separate sub-searches, where you end up going through all the permutations of Solution A | B | C ..., say in one corner of the search area, and Solution Z | Y | X ... in another corner. Since the local conditions are identical and [A|B|C...][Z|Y|X...] works equally well in any combination, it might really only be necessary to go through A, B, C... once and Z, Y, X... once, and record the results of the search in a hash table somehow.

Might work even better to short-circuit searches that _don't_ produce solutions; how much of a WLS search involves going over the same ground over and over, for example? My perception is that a majority of WLS's time is wasted chasing its tail in this way -- but quite possibly that's just an artifact of my relative inability to set up successful WLS searches!

Anyway, maybe one of these days we'll get there. A non-engineered "Conway-space" H-to-S would go a long way toward allowing Herschel circuitry to be packed into tighter spaces: at the moment, the new F171 is the best diagonal conduit available. Oherwise, parallel circuits that run diagonally tend to have to travel Manhattan-style, with a lot of 90-degree turns and sharp corners that get in each others' way -- or they have to convert signals to tandem gliders and back, which is also fairly awkward (mostly because of chirality limitations in the standard transmitter).