Conway's Life: Work in Progress

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

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, it appears that there's a way to build a (6,3) knightship 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.

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

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 demonstrated the universality of single-arm construction -- a single slow salvo aimed at simple targets can build anything that two arms or arbitrary glider collisions can build.

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 June 2014 no explicit example has been completed.

12) Spiral Growth
A spiral-growth pattern has been designed 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
It's now possible to use slow-salvo technology 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. (It's not really new, as mentioned in #2 above, but it will most likely be the first completed pattern to use this type of slow salvo for 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 oomplete.

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.

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.

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