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

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.

No comments: