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

10 December 2005

Holiday Greyships -- Grey No Longer!

Over the last several months, Hartmut Holzwart (with some help and suggestions from Jason Summers and others) has been building a wide variety of "greyships": extensible orthogonal spaceships with a wide variety of sizes and shapes, where the expandable central area is made up of stripes -- half ON and half OFF cells, either parallel or perpendicular to the spaceship's direction of travel.

Running these ships in MCell with the Rainbow024 palette and 17 alive states (see the Colors menu for both settings) gave some nice Yuletide colors -- figured I'd post the results here:

trial pattern showing a slipping-stripe reaction sent in
by Gabriel Nivasch: Hartmut Holzwart, 21 November 2005

alternate mirror-symmetric pattern showing Gabriel Nivasch's
slipping-stripe reaction: Hartmut Holzwart, 28 November 2005
hybrid 2c/4 greyship: Hartmut Holzwart, 16 November 2005

alternate hybrid 2c/4 greyship
Hartmut Holzwart, 16 November 2005

sample asymmetric hybrid greyship
Hartmut Holzwart, 18 November 2005

hybrid greyship: Hartmut Holzwart, 18 November 2005

symmetric hybrid greyship: Hartmut Holzwart, 18 November 2005

triangular hybrid greyship:
Hartmut Holzwart, 23 Nov 2005

greyship showing new components: Hartmut Holzwart, 25 Nov 2005

hybrid greyship with a crooked internal boundary
Hartmut Holzwart, 8 December 2005

asymmetrical c/3 greyship
Hartmut Holzwart, 11 November 2005

long and short c/3 ships w/ central p14 wick,
based on a ship from Jason Summers' raw c/3 collection:
Hartmut Holzwart, 14 Nov 2005

c/3 ship with central p15/5 wick: Hartmut Holzwart, 7 Decenber 2005

perpendicular-to-the-grain greyship with new back slope
Hartmut Holzwart, 29 November 2005

new greyship component shown on right side
Hartmut Holzwart, 29 November 2005

mirror-symmetric against-the-grain greyship with new back slopes
Hartmut Holzwart, 2005-11-30

perpendicular greyship with -1/4 back slope
Hartmut Holzwart, 1 Dec 2005

pentagonal perpendicular greyship with -1/4 back slope
Hartmut Holzwart, 1 Dec 2005

sample greyship-based puffer:
Hartmut Holzwart, 2 Dec 2005

perpendicular greyship with even symmetry --
new back slope, front end from a spacefiller:
Hartmut Holzwart, 5 December 2005

two even-symmetry perpendicular
greyships chained together, with
small tagalongs at back end:
Hartmut Holzwart, 5 December 2005

new perpendicular greyship with central
wick from an old unfinished spacefiller:
Hartmut Holzwart, 6 December 2005

perpendicular greyship with -1/2 back slope
Hartmut Holzwart, 7 December 2005

greyships suggested by Gabriel Nivasch,
with stripes offset by one down the middle:
Hartmut Holzwart, 7 December 2005

20 September 2005

Some ideas for a p8 or pure-stable Unit Life Cell

I've been looking a little bit at rebuilding David Bell's Unit Life Cell using p4/p8 glider and Herschel technology. The point would be to produce a unitcell with a period that's a power of two, to work more efficiently with hashlife/qlife algorithms. The p30 mechanisms in the current unitcell mean that hashlife has to add 15 different phases to its hash table before it has them all (I think). Also, I was wondering if it might not be possible to squash the necessary p8 circuitry into a 256x256 area -- or [much more likely!] into a 256x512 area, which hashlife could handle just about as well. The idea is to optimize the design for simulation by the new hashlife-based player/editor, Golly:


I think the Life-logic circuitry can be simplified considerably if the neighbor-count chute is modified a bit; in particular, if the stream of gliders that reads the contents of the chute is slowed down to (let's say) p64, then it's possible to check that either the #2 or the #3 neighbor-count glider is the first one out of the chute -- and then suppress the #2 neighbor-count glider with a negated cell-is-ON signal.

With a long-enough gap between gliders, Herschel-based switches can allow just the first glider of a stream to get through, then automatically reset itself afterwards. Here's one such circuit that works at p64:

Okay, now imagine a Unit Life Cell with no moving parts. An infinite grid of OFF unitcells will just sit there; it takes three appropriately-timed gliders from neighboring unitcells to activate a given cell, and then it stays activated only as long as two or three gliders keep coming in to sustain it.

A glider at some critical spot still means the unitcell is ON, and the lack of that glider means that it's OFF.

As in the p8 case, the fanout device is simple to construct with Herschel circuitry -- it could be a standard G->H converter (fairly compact at p8, but not too bad even at p1) followed by a string of glider-producing conduits:

Then the trouble starts. If the unitcell can't have any moving parts, there can't be a "timing gun" in it saying when to look for gliders from neighboring cells. So we have to always produce a "timing" signal at exactly the same time no matter which gliders come in from neighboring cells -- one glider, two gliders, eight gliders.

I have the feeling that I'm not being clever enough, but the best design I can think of at the moment is a string of eight circuits like the following sample pattern, each hooked up to an input glider from a neighboring cell:

Then you also have to actually count the number of signals from neighboring cells. Luckily the above pattern has a spare output glider for each input signal, and these could be collected into a single lane with standard stable reflectors and sent through a counting mechanism. Here's one possibility:

#C ladder from programmable constructor --
#C could be used as a configurable neighbor-counting mechanism
x = 424, y = 465, rule = B3/S23

Because there's a separate output for each possible neighbor count (if the ladder were extended to eight "rungs") it's possible to add eaters to block off outputs corresponding to any standard Bnnn.../Snnn... rule. The remaining outputs would be collected into a single lane with standard stable reflectors, as before -- the ladder would be set up so that there's at most one output glider for any neighbor-count (and either an ON or OFF cell-state signal, which suppresses either the S or B part of the ladder's output signal.)

The size of the ladder means that 512^2 is probably too small to hold the entire stable pattern -- but the next larger power of two, 1024^2, should be plenty big enough. And it should be relatively easy to adjust the period of the cell to a power of two, as well: probably p8192.

19 September 2005

David Bell's Unit Life Cell adjusted to 512^2

There's a new cross-platform open-source Life editor in the works -- and an insurmountable opportunity came up recently in the "golly-test" discussion list. Brice Due had constructed several patterns made up of "unit Life cells", which are large Life logic circuit configurations that mimic the behavior of single Life cells. Thus a single infinite Life universe can support an infinite regress of unitcells simulating unitcells simulating unitcells, at exponentially slower speeds. (See also Jared Prince's "Deep Cell".)

As it turns out, the timing guns in David Bell's original 500x500 Unit Life Cell are a good bit slower than they need to be, so there's still plenty of time for signals to arrive from neighboring 512-size cells, even though they have a little farther to travel. So the biggest headache was resynchronizing a lot of p30 circuitry; stretching each unitcell by 12 cells added multiples of 48 ticks to the glider paths. [If only the magic number had been 515 instead of 512, I would hardly have had to resynchronize anything at all...]

Unit Life Cell diagramThe "circuit diagram" for the original Unit Life Cell is shown at right: the area is 499^2 cells (and you need a one-cell-wide space between adjacent cells).

I didn't include a trail for the reaction for an OFF cell with two neighbors, which makes use of the isolated pentadecathlon at the left -- the #2 neighbor-count glider bounces back and annihilates what would otherwise be the ON output glider generated by the #3 neighbor-count glider. (I think.)

I had to make surprisingly few changes to expand the above to a 511^2 cell -- basically, just a gun and a few reflectors in the lower left corner had to be moved southwest, and then the gun, the counting chute, and all the reflectors leading to it needed to be rephased to match the new timing of the gliders from neighboring cells.

Here's the RLE for a single 511^2 Unit Life Cell.

-- And here's the RLE for a 3x3 test grid representing a blinker, with the Xlife version here.

Coincidentally, I had to switch to RLE in the unitcell #B definition -- it looks like the current version of Xlife can't quite handle picture-format subpatterns at width 512, so my 3x3 grid was getting corrupted. I included the #M prefix in the RLE header, so Achim's Xlife 3.6 should be able to handle the above pattern. I have a private build (3.5.2. going on 3.5.3) that can handle RLE subpatterns with or without the non-standard Xlife-style #M tags, but that change hasn't spread very far yet...


It wouldn't be an impossibly difficult task to adjust the unitcell period to be a power of 2 as well: after David Bell designed and built the original Unit Life Cell, a p8N glider reflector was discovered, comparable in size to the p30N reflector used in the current unitcell. (Unlike p30, p8 would be compatible with power-of-two step sizes between generations, which would match the way Golly's underlying 'hlife' algorithm works with Life patterns.]

However, so far I am successfully resisting that project: since the fanout device and the glider-to-block converters (and the rest of the neighbor-counting logic) are irrecoverably p30, they'd all have to be replaced with p8 equivalents -- and offhand I don't know of a p8 glider-to-block converter or a small alternate glider reflector equivalent to the two-p30-gun reflector used to get gliders onto the other square color. Easy enough to arrange a new Herschel-based fanout device so no alternate reflectors are needed, though --

Rather than work on a p8-reflector-based version, I'd be tempted to find a pure-stable solution: the advantage would be that any cells that are not ON have no moving parts whatsoever! Which would probably increase the simulation speed, and might also make it easier to see the active cells in a large pattern of unitcells. I think I have all the pieces for a pure-stable Unit Life Cell worked out in my head now (see the next posting)... and they are even easy to reconfigure for any standard rule. Well, any non-B0 rule at least -- otherwise I need a clock gun in each cell.

16 August 2005

Sawtooth pattern needs tuneup

[thumbnail at .5 sub-pixel zoom -- click on image to expand]

attempted sawtooth pattern with incorrect timing
attempted sawtooth pattern with incorrect timing --
runs for three cycles and then blows up.
The generations where the line burns out to
create a block are 3648, 9952, 20896, and 39800.
Their remainders modulo 192 are 0, 160, 160, and 56.
The growth in the generation numbers is
approximately a factor of 1.72.

David Bell, 18 July 2005

Adapted from notes by David Bell:

For the sawtooth to be made functional, the remainders of the generation numbers where the line burns out (modulo 192) must either be constant or else oscillate only over a few "safe" values.

The sawtooth can be easily modified by shifting the glider reflectors forwards or backwards along the path and by adjusting when the beehive is turned into the backward glider. But simply bouncing the gliders back using the glider reflectors might not be good enough; it might be necessary to hold onto them until the right generation numbers before releasing them.

attempted sawtooth pattern with incorrect timing
Alternative sawtooth mechanism

David Bell, 18 July 2005

Another sawtooth mechanism: a pair of gliders can arrive from the end of the line to cleanly ignite it while sending a glider back to the source direction. Perhaps the timings involved in this alternative mechanism would be easier:

Update: 16 August 2005

attempted sawtooth pattern with incorrect timing

another attempted sawtooth with incorrect timing --
runs for about 342,000 ticks and then blows up.
A p1056 gun is attached to a p8 regulator
in place of the original simple reflectors.
Dave Greene, 16 August 2005

Notes by Dave Greene:
I tried replacing the reflectors at the stationary end of the pattern with a p8 universal regulator, and ended up with an almost-sawtooth that works nicely for 342,000 generations -- and then blows up. Apparently my math is still wrong somewhere...

My one useful result was that a line-igniting glider can be delayed by any multiple of 176 generations, and the burning fuse will still arrive at the active site at the same phase of the p192 lineship. [After 192 generations the fuse is longer by 16 cells, so it takes 16 ticks longer to burn. So to keep the burning fuse from arriving late at the active site, you have to subtract 16 ticks from 192].

-- So I attached a p1056 gun (6 x 176) to the universal regulator, and found a configuration that survives for quite a few cycles... apparently by sheer luck, since there's something wrong with the underlying theory. The problem seems to be that the ever-increasing return time of the glider also extends the length of the fuse by a variable amount -- and the fuse burns four times as fast as a glider travels, so it's easy for the feedback effect to result in several possible arrival times. The burning-out reaction is versatile enough to handle any amount of lateness up to 80 ticks or so after the phase used for the first couple of cycles -- but eventually a phase always seems to come along that is off by more than that.

I also tried p880 and p2112 drive guns [I thought I had accounted for the variable fuse lengths with p2112, which is LCM(176,192) -- but no such luck.] It seems possible that delaying one of these drive guns by some number of generations would get the pattern into a stable cycle -- I just haven't figured out how to predict this in advance yet, and brute-force searching is fairly tedious in this case. Anyway, it wouldn't be quite as interesting to get the right answer by accident!

I tried writing equations to predict the length of later cycles, given the glider travel time and fuse burning time and the phase of the burning fuse's arrival at the active site... but so far I've always ended up with wrong answers after a cycle or two. Haven't given up yet, but would be happy if someone else wanted to figure it out!

12 August 2005

Perpendicular greyship update

Update: 22 July 2005 07:22

Hartmut Holzwart has produced some new partial results related to perpendicular greyships -- i.e., spaceships whose central section is made up of alternating lines of ON and OFF cells, and whose direction of travel is perpendicular to these lines. Several completed spaceships of this type are shown in an upcoming weblog posting.

Connection of 1/10 slope to 1/2 slope
Hartmut Holzwart, 14 July 2005

A 1/10-slope edge can be connected to a 1/2-slope edge:

Connection from side of perpendicular 
greyship to 1/4-slope back edge

Hartmut Holzwart, 22 July 2005

Jason Summers' side component can be connected to the 1/4 back edge component; however, Holzwart reports that his attempts to connect the side component to a known front component have not been successful.

09 July 2005

Greyship details

Jul 1:

#C diamond-shaped greyship Hartmut Holzwart 1 Jul 2005
x = 88, y = 83, rule = B3/S23

July 2:

#C front and sides for square greyship Jason Summers 2 Jul 2005
x = 46, y = 63, rule = B3/S23

July 4:

#C 2c/4 45-90-45 triangle greyship Hartmut Holzwart 4 Jul 2005
x = 100, y = 59, rule = S23/B3

#C 45-90-45-triangle greyship with p2 technology except on backslope
#C Hartmut Holzwart 4 Jul 2005
x = 85, y = 74, rule = B3/S23

#C greyship w/ back at limit slope ~1/4 Hartmut Holzwart 4 Jul 2005
x = 95, y = 120, rule = B3/S23

Jul 5:

#C junctions to construct arbitrary greyship front-edge slopes, 0-90
#C Jason Summers 5 Jul 2005
x = 95, y = 66, rule = B3/S23

#C shift a greyship left or right edge in by one stripe
#C Jason Summers 5 Jul 2005
x = 77, y = 55, rule = B3/S23

#C Greyship with slope of 5/9 Hartmut Holzwart 5 Jul 2005
x = 140, y = 115, rule = B3/S23

#C some components for a possible p4 greyship traveling perpendicular
#C to its stripes, instead of parallel Jason Summers 5 July 2005
x = 209, y = 93, rule = B3/S23

09 June 2005

A structured pattern for a Caterpillar

Structured patterns

Something I've been wanting to do for a while now is to produce a structured description of Gabriel Nivasch's Caterpillar.

In the context of the Game of Life, a "structured pattern" would be a description in terms of the smaller subpatterns that are repeated many times in the full pattern, such as the "shish-ke-babs" or the various rakes that make up the Caterpillar. The subpatterns in turn may be composed of smaller sub-subpatterns like pi climbers, blinkers, gliders, etc. A structured format makes a much better "blueprint" of a large pattern than a standard RLE encoding or picture-format file, and it's also very compact -- probably better compression than any standard binary-archive tool could manage.

Xlife 3.5/3.6 provides a good pattern format for describing this kind of structured pattern. Unfortunately it isn't quite versatile enough for this purpose. The big problem is that when you're dealing with periodic subpatterns, you often want to be able to include copies of them at several different phases. Xlife's approach is to define one phase of each periodic pattern as its "base" pattern; to paste multiple copies in, you paste the first base pattern, run the entire universe some number of generations to get the first pattern to the right phase relative to the second; then paste the second base pattern -- and if necessary run N more generations and paste a third base pattern, and so forth.

For stable patterns, or patterns that don't interact too closely, that's fine. But unfortunately this approach doesn't work very well for large numbers of subpatterns or higher periods -- sometimes Xlife's format doesn't support a "natural" compact definition based on subpatterns, because (for example) two of the subpatterns interfere with each other before the correct phase of the third subpattern can be placed to stabilize the whole conglomeration.

Ideas for an extension of Xlife #I format:

First, for reference, here is a summary of current Xlife syntax.

An extension of the format would fix the problem described above -- you'd have to be able to say, "run just this pattern in isolation for N generations, then paste it at (x,y)." This seems like a more natural way to compose patterns from subpatterns.

-- In fact, that's how Xlife's GUI does it! To register subpatterns in a "load script", you specify subpatterns' locations, transformations, and number of ticks forward in time from the base pattern. It's actually quite a surprise to look in an #I-format file for the first time and find out that Xlife has translated your registered subpatterns into this alternate format that is only sometimes equivalent.

I think Eugene Langvagen's PLife project has the necessary versatility to describe this kind of run-N-ticks-then-paste operation, but I haven't done enough benchmarking yet to know whether PLife can handle Caterpillar-sized structured patterns.

The main problem that I see is that a PLife script can easily become much too syntactically complex to be read directly by other Life software. You could create a structured pattern using a PLife script, but you'd have to convert it back to RLE to communicate it to anyone who doesn't have Python and PLife available. Xlife format is much more straightforward to write a parser for.

02 June 2005

2c/3 transceiver, large size

The new 2c/3 receiver accepts diagonal signals from the track and uses a repeatable reaction to convert these signals into output gliders. (In the pattern as shown below, all the output gliders are blocked, but one or more of them could easily be allowed to escape by removing the appropriate eaters.)

This version of the receiver can process signals separated by 2175 or more generations. The incoming signal interacts with a small constellation of still lifes at the receiver end of the 2c/3 track (two blocks and an eater, shown in light green in the picture). With the assistance of a few catalysts, the constellation collapses cleanly into an R-pentomino, which is then guided onto a Herschel track.

The path of the active signal is shown in gray the image below; the direction of travel is indicated by the red arrows. Gliders from the output Herschel (short blue arrows) are used to create two more Herschels; the Herschels are then routed to various Herschel-to-glider converters, which produce five gliders in two salvos (long blue arrows). Four of these gliders collide to rebuild the original constellation. (The first glider just removes an extra block left by the conversion of the receiver's initial output R-pentomino to a Herschel.)

2c/3 signal receiver: Dave Greene, 6 February 2005
Stable 2c/3 signal receiver; recovery time = 2175 ticks

2c/3 details

2c/3 is a respectable speed in the Life universe; by comparison, a glider travels at only one-fourth of the speed of light, and it was proven many years ago that this is the fastest that any finite diagonal spaceship can travel through empty space. There is a similar limit of half of the speed of light for orthogonal spaceships.

However, disturbances in pre-existing structures can travel much faster than these limits -- there is no theoretical limit lower than lightspeed, either diagonally or orthogonally. See Gabriel Nivasch's lightspeed article for details and examples.

A signal in a 2c/3 track will quickly overtake a glider travelling in the same direction. If a sufficiently long track can be made to turn a corner, a 2c/3 signal in it will even overtake an orthogonal c/2 spaceship.

29 May 2005

2c/3 transceiver, Mark Minus One

What follows is the first draft of a Game-of-Life circuit with a new, faster type of signal -- two-thirds of the speed of light diagonally! This is a big improvement in signal speed. Even Jason Summers' light-speed 'telegraph' can theoretically approach only half the speed of light diagonally, and it is considerably more unwieldy even than this pattern, and harder to re-use. Besides the telegraph, the fastest repeatable diagonal signal was a simple glider, at c/4.

Input is a Herschel, output is a glider. For comparison purposes, an extra reference glider has been added near the input Herschel. Despite the horrific and unnecessary inefficiency of the Herchel-to-2c/3 converter, and the fact that the output glider is produced from a 'backward' part of the 2c/3-to-glider converter, the output signal still manages to catch up to the reference glider!

Nothing about this pattern is properly optimized. For example, there's no good reason for the input Herschel ever to travel north; the conduit delivering the sacrificial beehive to the key point of the 2c/3 transmitter is ridiculously long; and the four boojum reflectors had to be moved embarrassingly far to the northwest to get the timings to work out.

The stair-step diagonal Herschel conduit at the left edge of the pattern is an artifact of an old toolkit I put together a year or two ago, which allows a shotgun for a synchronized glider salvo (like the three closely-spaced gliders traveling northeast from this area) to be constructed relatively quickly, though at considerable cost in efficiency. This part of the pattern took me less than an hour to put together, but it should be possible to fit a shotgun that fires twice as quickly into less than half the space.

Mark Minus One 2c/3 transceiver  Dave Greene  29 May 2005

After some optimization on the transmitter, it will be possible to use this technology to build the world's first period-independent pseudo-Heisenburp device, which can absorb a glider and produce as many output signals as needed -- including a new glider with exactly the same path and timing as the original!

[Previous Heisenburp devices all require the input glider to be aligned to some particular period, or they fail catastrophically. On the other hand, these periodic patterns can be "true" rather than "pseudo" Heisenburp devices: they produce output signals without destroying, or even temporarily affecting, the input glider.]

The 2c/3 signal track was discovered by Dean Hickerson in March 1997; Noam Elkies came up with several ingenious recipes for getting a repeatable signal started in a 2c/3 track, early this year, after I came up with a convoluted way of getting a signal out of a 2c/3 track. Further optimization is no doubt possible at both ends...

Update: May 1, 2007 -- Finally got around to doing the optimization work; the results can be seen in the latest version of the Golly project, Golly 1.2. Run heisenburp.py in the Scripts folder (you need to have Python installed, but it will take you all of maybe five minutes, and it's worth it.)

14 February 2005

Glider-proof patterns

Copied from my postings to newsgroup: comp.theory.cell-automata
Date: 13 Feb 2005
Subject: Re: exist glider gun able of reconstruction in Life?

Ilmari Karonen wrote:
> This line of thought suggests another possibly interesting
> question: are there any known patterns that are fully
> "glider-proof", in the sense that they can withstand a
> collision with a single glider from any direction and in
> any phase?
Among existing eater patterns in B3/S23 Life, I think the successful-defense record is still held by the eater2, which can absorb any number of gliders on any of four adjacent paths and emerge undamaged:

#Life 1.05

-- For many stable patterns, by the way, there are other input glider lanes where the gliders are caught and turned into boats, which are then cleanly deleted by another glider coming in on the same lane. I'm not sure how to count those, though; if another glider then comes in on a different "glider-proof" lane, a boat would sometimes get in the way and cause an explosion.

So I suppose that's a different metric: any object will have a glider-pair-invulnerability percentage (!) higher or equal to the single-glider-invulnerability percentage. (Percentages could be calculated from the number of input glider lanes that allow a complete recovery, divided by the total number of input lanes that affect the object in any way.)

There's a double-sided version of the eater2 which I thought at first would have the highest known glider-invulnerability. By the above metric, if my quick counts are right, the double-sided eater2 is exactly 10% single-glider-proof, and 12.5% glider-pair-proof -- whereas the single-sided eater2 above is only 6% glider-proof -- 1/17 of the lanes are safe.

By comparison, a double-ended fishhook eater has a rating of 1/28 (3.6%) and a standard eater is down around 1/52 -- though the slow-glider-pair-proof ratings go up to 1/14 and 3/52, respectively...

However, it appears that one can string together double-sided eater2 patterns and increase the percentage rating indefinitely: each new eater2 added to the chain means that 18 more glider lanes will affect the object, of which 8 lanes are safe. So the glider-proof rating of these eater2 chains asymptotically approaches 4/9. Here's a 22% glider-proof eater2 chain, for example:

#Life 1.05

It takes one or two more eater2s to reach 25% (depending on whether glider-pair invulnerability is good enough) and further improvement gets slower and slower.

So it looks like maybe the first challenge would be to find something that breaks the 50% barrier. There might possibly be some clever way of getting those absorbing blocks one step closer together, but it doesn't look too likely to me...


One more related topic:

Ilmari Karonen wrote:
>...  There are known CA's with indestructible patterns, but I'd be
> surprised if Life had any. However, the weaker condition of
> "glider-proofness" doesn't intuitively seem quite as impossible
> to me.
There's an even weaker form of the question which has the virtue of having a positive answer: it is technically possible to build an eater (of sorts) that can safely handle a wider "glider highway" than the eater2's four adjacent lanes. In fact, it can be shown that any given width of highway can be made single-glider-proof with a stable pattern -- or even multiple-glider-proof, as long as there's enough space between the gliders.

Last March I cobbled together a miscellaneous collection of stable Herschel conduits into a pattern that I called a "highway robber": it can absorb a glider coming in on one particular path -- let's call it "lane 0" -- and recover its initial configuration (very slowly!). It can also send out one or more output gliders to signal a capture from the highway. But in this case the important thing is that it allows gliders on adjacent lanes 1, 2, 3, ... of the highway to pass by

[Conventional small eaters based on boats or tub-with-tails (tubs-with-tail?) can almost manage this last trick --

#C 7x9 boat-based eater

-- they can absorb a glider on lane 0 and leave lanes 2, 3, 4 ... unaffected. As it happens, they also usually work on gliders coming in at 90 degrees from lane 0, that strike the eater at the same point. But they reliably blow up if a glider comes in on lane 1.]

A row of highway robbers watching adjacent lanes of a glider highway can absorb any slow glider salvo traveling along that highway. And setting several highway robbers to watch the same lane could reduce the minimum time between gliders by quite a bit.

But guarding a wide highway this way is hideously expensive -- the current highway-robber pattern is close to 400x400, though it could be made a good bit smaller. And it can only watch for gliders coming from one direction, of course -- if gliders can travel in both directions on the highway, you have to double the number of robbers so they can watch each others' backs.

Basically, every glider lane that you have to guard with this method just makes a pattern that much bigger and adds more unguarded lanes somewhere else. Figuring out how to build a complete glider-proof perimeter is very much an unsolved problem.


So to return briefly to the original question: my instinct is that a stable pattern will never be 100% glider-proof -- there are too many possible lanes of attack -- and that even with an active pattern, it's going to be very hard to avoid having an Achilles' heel somewhere, at least during the detect-and-repair process. But it might at least be possible to design an active defense system with a reasonably high probability (above 99.99%, let's say) of recovering from a single random glider impact.

-- Just don't throw any orthogonal spaceships at it, or all bets are off!