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

[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!