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

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
19bo$17b3o$16bo5boo$16boo4boo3$25bobo$25boo$26bo$$15bobo$16boo$16bo$oo
$oo3$29bo5boo$28bo6boo$28b3o$5boo$5boo$$20boo21boo$19bobo20bobo$21bo
21bo4$15boo$15boo$51boo$50bobo$51bo3$22bo$21bobo$21boo$59boo$58bobo$
59bo3$30bo$29bobo$29boo$67boo$66bobo$67bo3$38bo$37bobo$37boo6$46bo$45b
obo$45boo$$67boo$67boo3$54bo$53bobo$53boo!

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
124bo3bo$123boo3boo6$104boo6boo25boo6boo$103bobbo4bobbo23bobbo4bobbo$
102b6obb6o21b6obb6o$103bobbo4bobbo23bobbo4bobbo$104boo6boo25boo6boo6$
107b4o$106b6o$105b8o$104boo6boo$105b8o$35bo17bo17bo17bo16b6o$34bobo15b
obo15bobo15bobo16b4o$135b3o$134bo3bo$34b3o15b3o15b3o15b3o43bo3bo$34b3o
15b3o15b3o15b3o44b3o$35bo17bo17bo17bo$95boo$95boo$35bo17bo17bo17bo$34b
3o15b3o15b3o15b3o44b3o$34b3o15b3o15b3o15b3o43bo3bo$134bo3bo$135b3o$34b
obo15bobo15bobo15bobo$11boo8boo12bo17bo17bo17bo$12bo8boo$12bobo$13boo
$$126boo$7boo117boo$8bo$8bobo$9boo$$116bobboboobobbo$116b4oboob4o$116b
obboboobobbo3$9bo$9bobo$9b3o$11bo$$21boo$21boobboo8bo17bo17bo17bo$25bo
bo6bobo15bobo15bobo15bobo17boo$bboo23bo80boo$3bo23boo$3o31b3o15b3o15b
3o15b3o$o33b3o15b3o15b3o15b3o$35bo17bo17bo17bo3$35bo17bo17bo17bo$34b3o
15b3o15b3o15b3o$34b3o15b3o15b3o15b3o3$34bobo15bobo15bobo15bobo$35bo17b
o17bo17bo!

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

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.

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.

Xlife #I format for Golly? Sort of...

I've added a couple of Python scripts, breeder.py and breeder-display.py, to a subsidiary folder in the Golly CVS system. These are by way of being translations of the original Xlife breeder.life -- one is short and fast, and the other is a slower on-screen walkthrough showing the breeder being incrementally constructed from smaller pieces.

I was hoping to be able to use breeder.life as a test case for code that would take *.life as input and produce one of these two types of .py script as output... but it's only _almost_ that simple.

The breeder.py script is a direct translation -- the numbers after each #I line show up pretty much unchanged in the Python script, and there's an easy glife conversion for the rotation and reflection specs:

0, 1 -> identity
1, 1 -> rcw
2, 1 -> flip
3, 1 -> rccw
0,-1 -> flip_y
1,-1 -> swap_xy
2,-1 -> flip_x
3,-1 -> swap_xy_flip

The only problem is that four subpatterns in breeder.life are defined with an 18-step time offset, like this:

#B ./breederrake.11
#I :breederpuffer 71 37 0 1 0
#I :ss.s 75 14 0 1 18
#I :ss.m 60 6 0 1 18
#I :ss.m 60 -8 0 -1 18
#E

Translated into English: "To make a breederrake11, put a breederpuffer at (71,37), run it for 18 generations, and then drop an LWSS at (75,14), an MWSS at (60,6), and a reflected MWSS at (60,-8)" [where breederpuffer, LWSS (ss.s), and MWSS (ss.m) are defined later in the file.]

This would all be very well and good, but here's the rub: the resulting breederrake11 subpattern is _not_ the 'flat' pattern resulting from running breederpuffer for 18 generations and adding the *WSSs. It's a true recursive definition -- which means that to get the right results in the final pattern, you have to rebuild each and every instance of breederrake11 by dropping a breederpuffer at the right relative location, waiting 18 ticks, and then adding the spaceships!

The glife system, on the other hand, generally deals with 'flat' subpatterns: if you give the above recipe for a breederrake11 and drop a copy of it into the Golly universe, what you'll see at t=0 in your final pattern is *generation 18* of breederpuffer!

The only safe way around this appears to be to "unpack" every definition that has a nonzero time value -- flatten out the nested definitions... and end up with a significantly longer recipe.

So in the end I cheated. In this specific case, it was easy enough to move the spaceships forward 9 cells to produce an equivalent breederrake11 that was all defined at t=0 -- no 18-tick time offset. The revised subpatterns were safe to use for the next level of definitions (this is not necessarily true, but it happened to be true in this case.)

The only remaining ugliness was the way that Xlife drops subpatterns into the universe, then runs the universe until it's time to drop in the next pattern -- instead of running each subpattern in isolation, then dropping it in when it has reached the right phase. Doing this in Python and storing the subpatterns in variables can require a lot of nested parentheses [or a long series of assignments to intermediate variables]:

flotilla = (((((((breederrake11(314,242)[4]
                  + breederrake11(312,201,flip_y))[101]
                 + breederrake00(368,286))[33]
                + breederrake10(359,158,flip_y))[306]
               + breederrake10(406,137,flip_y))[129]
              + breederrake01(349,273))[141]
             + breederrake10(428,336) + breederrake10(426,107,flip_y))[223]
            + breederrake00(473,371))[1]
           + breederrake00(472,71,flip_y)

The final result is a Python variable containing a complete breeder pattern.

--------------------------------------

The other way to build a breeder using the Xlife recipe is to use Golly's visible universe -- actually drop subpatterns in and run them. The second Python script, breeder-display.py, does this, in a way that lets you see the breeder pattern coming together:

breederrake11.put(314,242)
run(4)
breederrake11.put(312,201,flip_y)
run(101)
breederrake00.put(368,286)
run(33)
breederrake10.put(359,158,flip_y)
run(306)
breederrake10.put(406,137,flip_y)
run(129)
breederrake01.put(349,273)
run(141)
breederrake10.put(428,336)
breederrake10.put(426,107,flip_y)
run(223)
breederrake00.put(473,371)
run(1)
breederrake00.put(472,71,flip_y)

[if you look at what the script is actually doing, it's actually a bit more complicated than that, because it highlights the location of the next paste operation ahead of time -- but the above is the basic idea.]

--------------------------------------

In either case, the Xlife model doesn't seem to be the most efficient way of describing patterns compactly _or_ building them quickly -- my final target here is still a structured-format Caterpillar. The Xlife system essentially requires rebuilding every single copy of every single component pattern! It's possible to take shortcuts some of the time, but they're dangerous -- a pattern that Xlife can successfully load may blow up catastrophically if shortcuts are used.

Golly's normal method of defining new patterns in terms of transformed and rephased subpatterns, and then re-using the 'flat' results, seems to be more generally useful for recursive pattern definitions.

Brice Due's Game-of-Life Metapixel -- Sample Patterns

Here are a few sample screenshots showing "metapatterns" created using Brice Due's new Conway's Life metacell and displayed with Golly 1.0. Click on the images to see them at full size:
Download this file


Download this file

A metacell is a large pattern that "simulates" a single cell in Conway's Game of Life or another similar CA rule; that is, when a grid of metacells is run for the right number of ticks -- one "metatick", so to speak -- a metacell will turn ON or OFF according to the rules it's programmed to follow, just as a single cell does.

David Bell's original unitcell was the first example of a metacell, followed by Jared Prince's modification which allowed multiple independent cell states in a single "Deep Cell". Both of these unitcells were hard-coded to simulate only the Conway's Life rule (which is also the only rule that allows the patterns to function.)

One of these days, Brice Due will probably get around to finishing the work of documenting his recent OTCAMP [Outer Totalistic Cellular Automaton Meta-Pixel] construction, which showed up as a star feature of the Golly 1.0 pattern collection. This new 2048-cell-square pattern is capable of acting like a single CA cell following any "outer totalistic" rule -- i.e., birth and survival can be programmed to depend on any combination of number of ON neighbors, from zero to eight, in the metacell's immediate neighborhood. The official OTCAMP weblog describes the new signal-processing technology (mostly period 46) included in the construction.

But the most impressive feature is the "metapixel" behavior: where Bell's and Prince's designs relied on a single glider in a particular spacetime location to signal an ON or OFF state for the metacell, Brice's metapixel quickly switches rows and columns of LWSSs on and off across a large area -- so the state of a metacell can be seen even when a viewer is zoomed out so far that it's impossible to distinguish individual circuit elements, let alone single cells.

The effect is that Golly can run a large metapixel pattern at surprisingly high speeds (after some initial warmup time to build up the hash table) -- and if the zoom level is high enough to show the whole metapattern, the effect is fairly similar to watching a regular pattern in a conventional Life player. When I started zooming in for the first time, the effect was thoroughly jaw-dropping -- it takes several successive magnifications before the individual components become visible.

The OTCAMP weblog is currently [as of 2/5/2007] a work in progress, and since Brice is also working on another very interesting Game-of-Life project (reworking Paul Callahan's 'ptbsearch' signal-conduit search program) I don't want to distract him... so I figured I'd make the ON and OFF metapixel patterns available here, along with a few pictures and sample metapatterns -- just in case anyone wanted to look at some of the metapatterns that didn't make it into the Golly "top-100" collection.

A full archive of the metapatterns Brice sent me, plus one or two that I generated myself with a Golly Python script (metafier.py, now included in the Golly 1.1 Scripts folder), can be downloaded from http://cranemtn.com/life/weblog/metablog.tar.gz. And here are the base patterns from which any metapattern in any outer totalistic rule can be composed -- a single OFF cell and a single ON cell. Notes on programming these metacells to simulate any rule of the form B??/S?? [each cell's birth and survival depending on the number of ON cells in its eight-cell neighborhood] can be found in the comments of the OFF and ON cells; I've also reproduced the header at the bottom of this posting.

Here's a detail from a metapattern made out of copies of Jason Summers' p156 gun:

Download this file or click on it to see a full-sized image.

Here's a detail of one particularly interesting phase of the p156 tiling:

Here's a sample metapattern showing what happens when the tiles are programmed to run the B1/S1234568 rule instead of B3/S23:
Download this file to open it in Golly, or click on the image to see a full-sized screenshot. Detail after the pattern runs several metacycles:

Here are a couple of simple B3/S23 patterns, generated with the Golly 'metafier' script (left) and Brice's original Perl script (right), showing what metapixels look like at various scales. The Perl script works on HistoricalLife three-state rule patterns from MCell 4.20, so the presence or absence of a metapixel cell can be used to denote the third state -- a "history" state that is used for cells that are currently OFF but have been ON in the past:

Download this file

Download this file

Here's an MWSS -- a middle-weight spaceship from Conway's Life, B3/S23 -- made out of metapixel tiles. However, the tiles are programmed to simulate a completely different rule, B3-S12345, which uses the MWSS as a seed for an expanding maze pattern:
Download this file

Here's the same pattern after it has run for a few hundred meta-generations:

Header (slightly modified) for metapixel ON and OFF base tiles:

------------------------------------------------------------------
OTCAmetapixel unit cell by Brice Due (fall 2005 - spring 2006). For info, base patterns, and a perl script to automate tilings, see b3s23life.blogspot.com/2006/09/brice-dues-game-of-life-metapixel.html

Both ON and OFF tiles must be programmed identically before tiling a model pattern. See below for programming instructions.
------------------------------------------------------------------
OTCAmetapixel tilings require Golly hashlife to run. Get Golly at http://golly.sourceforge.net

USAGE: Speed steps 8^3 - 8^6 are good. Be patient after changing the speed step; the hashlife cache needs time to warm up. Try increasing the maximum hash memory setting if the meta-pattern continues to run haltingly.
------------------------------------------------------------------
OTCAmetapixel = Outer Totalistic Cellular Automata Meta Pixel = OTCAMP

Period: p35328 = 2^9 * 3 * 23
Dimensions: 2048x2048 but physically 2058x2058 (see TILING below)
Pixel Area: 1720x1720 = 70% of the tile area
Duty Cycle: 90% (1720 / lwss c/2 = 3440 gens to transition pixel display)

TILING: To tile by hand, place tiles so that the cornermost blocks overlap. The tiles will physically overlap by 5 cells in every direction. The overlap will place tubs inside cross-corner neighbors. When tiling by script the tiles can be trimmed to 2048x2048 and the corner blocks and tubs removed. But the script MUST place the tubs inside cross-corner neighbor tiles.

PROGRAMMING: There are three different programmings. Two must be done explicitly by the user while the third is done implicitly during tiling.

B/S RULE: Any outer totalistic rule can be programmed. The lookup tables in the SW corner of the tile are in the familiar B/S format. The presence of an eater denotes membership of {B,S}n within the active rule set. To aid programming by hand, defective eaters have been placed at all 18 positions. These defective eaters burn cleanly. Thus, programming a rule is as simple as completing the eaters at the desired positions within the lookup tables. The lookup tables have been graphically annotated to make things clear. (Note: to study a single tile, program the rule B0/S = B0/Snone.)

CONNECTIVITY: There are eight glider output channels {NW, N, NE, E, SE, S, SW, W}. These channels are initially closed by eaters. The physical presence of a neighbor tile will trigger the appropriate proximity fuses and open the necessary glider channels. This programming is done automatically when tiles are placed.

NEIGHBORHOOD: Any subset of a Moore neighbrhood can be programmed. Initially there are 8 active proximity fuses {NW, N, NE, E, SE, S, SW, W}. Disabling a fuse results in that glider *output* channel remaining permanently closed. To disable the corner fuses, remove the lwss for that corner. To disable edge fuses, remove the block in the middle of that edge. Do not remove the eater near the block. For example, a von Neumann neighborhood is programmed by disabling the four corner fuses, leaving the four edge fuses active.