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

22 January 2007

Stable pseudo-Heisenburp device and other P1 wiring projects

I've been experimenting recently with what might be called "staged-recovery" Herschel conduit constructions. Reactions using only stable (P1) catalysts are often imperfect -- that is, there's no known way to accomplish many signal-processing tasks without either

  (a) temporarily destroying some still life, and going back and replacing it later, or

  (b) creating an unwanted still life as a byproduct of a useful reaction, and going back and removing it later.

Generally (b) is easier than (a), since most simple still lifes can be annihilated by a single glider on the correct lane -- maybe with the help of a catalyst, but with few or no timing constraints. If a period-2 byproduct (most commonly a blinker) has to be modified or removed, this usually cuts in half the allowable spacetime locations for cleanup gliders, but still leaves a very wide search space.

So this kind of repair just means routing a Herschel to any one of twenty-plus known Herschel-to-glider converters, anywhere along the target glider lane, with a wide range of timings (usually the quicker the better). With this many degrees of freedom, a Hersrch search can generally find a fairly compact solution.

-- Compact as these things go, that is! With a choice of 17 conduits in the basic set, a string of (say) three to five conduits will often be enough to put a glider on the correct lane, without having to wander off too far in the wrong direction -- unless the glider lane is too close to the input Herschel. A target area at least fifty cells away from the input Herschel should usually allow a clean connection to be made. I'll work on some rough coverage graphs for a separate posting.

The basic idea behind a staged-recovery construction is that it's often possible to quickly make a repair, even a difficult repair -- say, rebuilding a loaf used to reflect an incoming glider, as shown below -- at the cost of some minor damage to the repairing circuitry. If the damage itself can be repaired relatively quickly and easily, the result is a somewhat more complex circuit that can recover more quickly overall -- if the initial part of the circuit is triggered again, the damaged area can often be repaired before the next signal reaches it.

Highway robber without a staged-recovery mechanism -- recovery time is 2381 ticks.
As an example of a staged-recovery construction, here's a "highway robber" that absorbs gliders on a given lane and produces optional output gliders or Herschels, while letting gliders on all lanes beyond the key lane pass unharmed. This version takes the straightforward route of first producing Herschel signals from the initial glider, then using the Herschels to rebuild the original loaf. (The loaf is dangled in the key glider lane as "bait", and is destroyed while reflecting the input glider.)

Highway robber with staged-recovery mechanism --
recovery time is 1696 ticks, but the pattern does not become
stable again for 2234 ticks.
Here's the same basic reaction using two stages, where the stage 2 circuit removes two extra beehives from the stage 1 circuit, and as a result allows the highway robber to recover more quickly overall, and also to produce an output signal much more quickly:

stable pseudo-Heisenburp device -- recovery time is 1847 ticks.
And here's the same idea taken a little further -- attaching the highway robber to a revised 2c/3 transceiver produces a stable pseudo-Heisenburp device, which "borrows" a glider from the edge of a fleet of gliders, and later (thanks to the magic of stable 2c/3 signal wires) puts it back in exactly the right location relative to the other gliders in the fleet:

The primary use of the staged-recovery idea in the transmitter is in the northeast circuit, which asynchronously rebuilds a beehive and sends in a glider to reset the beginning of the 2c/3 wire after the signal is sent. The pattern could be rearranged to trigger this circuit considerably faster -- or even *before* the main trigger signal arrives (in which case the quiescent state of the transmitter would not include a beehive).

Here's a Python script that builds a complete P1 Heisenburp device from its component parts. The above screenshot shows what it looks like in Golly 1.1. It can also take advantage of the new multi-layer functionality in Golly 1.2. In multi-layer mode, the script produces a screen something like this:

tiled views of the Heisenburp device: screenshot from Golly 1.2 beta

Update: The latest version of this script is now included as Scripts/heisenburp.py in the Golly 1.2 release distribution.

No comments: