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

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

27 April 2007

Hex Counter and Cells Within Cells

Some incredible patterns have been included with the latest version of Golly, a cross-platform editor and player that can display huge CA patterns, and often run them at unheard-of speeds. Golly 1.2 came out in mid-April on SourceForge; one of the new patterns is a two-digit hexadecimal counter implemented as a Conway's Life pattern. It's a modernization of sorts of Alan Hensel's 1994 "Decimal Counter" pattern -- an animated Java version of which is now available on the Web [collidoscope.com].

Another set of patterns by the same author, using some of the same components, are composed of huge grids of metapixels -- regions thousands of cells square that are designed to mimic the behavior of the underlying cellular automaton, or that can be "reprogrammed" to simulate other rules.

The Golly engine is based on hashlife (see the Dr. Dobb's Journal link for details on how the algorithm works).

The hex counter can be found in the Hashing-Examples folder in Golly's pattern collection, along with three metapixel samples. This series of screenshots shows the counter in action at various scales.

The first screenshot shows individual cells in the underlying grid, making up two still lifes (a block and a fishhook eater) and two spaceships (lightweight and middleweight).

The two spaceships are part of a high-period salvo that either creates a block or 'pulls' it along a row of memory bits that encode each pixel of the 'hex counter' movie.

The two blockers in the lower left corner both suppress the creation of blocks. The one on the left ends the block-pull cycle and allows the movie to cycle back to the beginning. The one on the right cleans up the extra block in an identical reaction triggered by the salvo-suppression glider coming in from the upper left, instead of by a block.

The suppressing glider is itself suppressed by a glider from a high-period Herschel-based gun that ends just to the right of this image. It is made from a long series of Herschel period-doublers plus a Herschel-to-glider converter.

This is the first subpixel zoom in the series, so individual cells can no longer be seen and shapes may become somewhat distorted. For example, the two seven-bit eaters at center left, which are part of the row of 'memory bits' that tell the movie pixel when to toggle ON and OFF, are reduced to four-bit polyominoes in this view.

The rows of lightweight spaceships (LWSSs) that form the ON state of each movie pixel can now be seen clearly at the top. No LWSSs can be seen at the bottom edge because that pixel is currently turned OFF.

Here an entire edge of a single movie metapixel can be seen; in the center can be seen the row of memory bits that encode half of the metapixel's contribution to the movie. For compactness, the even and odd bits of the movie are stored along separate edges of the metapixels.

The other half of the movie's frames are encoded in a column along the left edge of the movie metapixel, on a diagonal mirror-image from the row along the bottom. At this zoom, two entire metapixels are visible, and the memory-bit columns are visible only as thin vertical lines at the far left. It can be seen that different metapixels contain different coded sequences.

Here several metapixels can be seen at once. The differential shading between the two halves of the pixels at this scale is an artifact of the LWSSs' rectangular shape, and the fact that they are not spaced a power-of-two distance from each other.

At this scale the pixels appear solid and almost all of the details of the control mechanisms are too small to be seen.

At this scale the entire 'movie screen' can be seen. The movie's frame rate will vary widely depending on the memory and CPU speed, but with a step size of 8^4 or 8^5 it may reach several frames per second once Golly's hash tables have been populated.

A final view of the movie screen with all the construction details lost in the distance.

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.