Conjecture on collisions with small stable constellations

[pcallahan]

[Note: going with "Patterns" not "General Discussion" since I am considering a family of patterns.]

I don't have the tools available to confirm a negative result, but it would be good to see this settled one way or the other (if it hasn't already; has it?).

Suppose a single glider hits a constellation of non-moving objects, (call it A) that lies in a kXk bounding box, for some small k<=20 for instance. The collision emits at least one additional glider and settles into a new constellation B. A single collision with B also produces another glider and settles into constellation C. Eventually, such a series of collisions restores constellation A (at the same place or maybe not; if rotated or flipped, it could be brought there by more collisions; or it might be shifted). Note that it is possible that A=B. There is no upper or lower bound on cycle length; there just has to be a cycle. B, C, etc. do not have to fit in the box. Just one step in the cycle does.

The reason for restricting k is that eventually a reflector meets the definition (snark is 23x17 and even p30 buckaroo does not violate the above definition, which does not mention period at all). Extending the bounding box much farther, you get into universal constructor territory. For this question, k is small, maybe k=15.

Another point to emphasize is that each collision must emit at least one glider. Otherwise, there are many glider-consuming solutions to restoring objects and constellations.

After revisiting some old search ideas and colliding gliders with natural junk, I'm convinced that there are only two constellations or objects that satisfy the above (up to equivalents like adding inert parts to the constellation).

One is the remarkable biloaf collision. The other is this glider shifter I found using primitive and forgotten methods in 1994.

Code: Select all

x = 81, y = 80
2bo$obo$b2o67$72b2o5b2o$72b2o5b2o5$79b2o$79b2o$67b2o$66bobo$68bo!

The glider shifter can be reset back into place with a second glider, while the biloaf is always shifted.

I thought maybe there was something else out there consisting of a natural constellation in a 15x15 box that could be reset through several steps like the above. I don't think so anymore based on this search (quoting myself from another thread).

(1) I began with millions of random starting seeds, generated them to find a stable ash with 20x20 bounding box constraints, normalized their orientation and phase (with blinkers), removed duplicates and obtained a list of 49905 "natural" stable and period-2 targets.
(2) Set up all glider collisions giving the glider 30 steps before hitting, which is usually enough to make it work coming from infinity.
(3) Tested these collisions for output gliders and non-zero stable ash fitting in a 20x20 bounding box.
(4) Collected the ash and dedupped again to use as another round of targets.

Repeat above until the set of targets is stable. There are some other things you can do to remove junk, such as taking the intersection of the target list from current and some past round.

The point is that ultimately a target is only reusable if it consists of collision ash. However, even these may be uninteresting as so many collisions produce ash that does not ultimately lead to a cycle.

So my conjecture is that the 3-block glider shifter and the biloaf are the only objects or constellations that can fit in a 15x15 box and be reset to the original shape without glider loss (or you can add the empty pattern to this list if you like). (EDIT but this is probably incorrect, if you let the intermediate constellations get large, assuming you can engineer a cleanup using only glider-producing collisions)

Is there a simple way to test this with modern tools? The basic idea is that there is a finite set S of stable constellations that fit in a 15x15 box. Non-lossy glider collisions transform this into another finite set of ash constellations (which need not fit in the box). Does this transformation graph contain any cycles other than noted above? My belief is no, but it would be great to see it verified and of course even better to see it refuted.

If it makes the problem more tractable, we could have some restriction on the constellation to rule out exotic, dense still lifes that are almost certain not to be part of a cycle. Anything that would work should come up in soup results. It is just possible that some Bellman-derived still life could fit in the box, and work as a catalyst. Rather than try to make the negative result apply, I suggest placing reasonable restrictions on the allowable constellation.

[dvgrn]

I don't have the tools available to confirm a negative result, but it would be good to see this settled one way or the other (if it hasn't already; has it?).

Nope, definitely not settled. Paul Chapman was running searches off and on for a few years along these general lines, hunting for Spartan stable reflectors that just looked like random junk, along the lines of Gabriel Nivasch's "stableshift" search program. More recently Alan Hensel had a more general idea about bombarding random ash ("fluff") with gliders and somehow getting the same sequence of gliders out again, and returning the ash to its original configuration.

Here's a thread with a slightly more recent variation on the idea, limiting the target ash to just blocks. No particularly interesting results, though: everyone involved failed to compile the required billion-record Blockic Fluff database...

The reason for restricting k is that eventually a reflector meets the definition (snark is 23x17 and even p30 buckaroo does not violate the above definition, which does not mention period at all). Extending the bounding box much farther, you get into universal constructor territory. For this question, k is small, maybe k=15.

...
So my conjecture is that the 3-block glider shifter and the biloaf are the only objects or constellations that can fit in a 15x15 box and be reset to the original shape without glider loss (or you can add the empty pattern to this list if you like).

Is there a simple way to test this with modern tools?

I don't think so -- not exhaustively enough to confirm or refute the conjecture, anyway. I'm guessing that with a limit of 10x10, we might possibly collectively have enough computing power available to check everything, but 15x15 is over twice that area and the number of nodes in the search tree gets to be somewhere between unmanageable and ludicrous.

Now, I definitely don't know that for sure -- maybe shortcuts can cut down the search space more than I think they can. But I do have some plausible data points based on having written this Cheesy Constellation Enumerator and tried it out on different sizes of bounding box and different numbers of allowable still lifes to be packed into the box. If you allow as much ash as will fit in the box, it starts getting fairly crazy by around 10x10 -- you can fit a lot of blocks into that space, let alone anything else.

The Cheesy Constellation Enumerator deliberately doesn't create any pseudo-objects -- I wanted only easy glider-constructible stuff for this enumeration. If tighter packing is allowed there are even more options to check.

But I agree that if you're looking for ash that has any realistic chance at all of reappearing spontaneously after several glider strikes, you might as well limit the search to the really common stuff from Catagolue. If an object hasn't been used as a transparent catalyst in a Herschel conduit, it might be too rare to bother with... so that's block, beehive, blinker, boat, loaf, ship, pond, and I think that's about all.

I guess my main response is that if you started your experiment with just some number of millions of ash patterns, it seems like you must still be a very long way from having tried everything that fits inside 15x15.

[pcallahan]

I guess my main response is that if you started your experiment with just some number of millions of ash patterns, it seems like you must still be a very long way from having tried everything that fits inside 15x15.

True, and I'm not claiming a negative result. But this starting set was enough to find the only two constellations I know of that work, which makes me think there are really very few useful starting collisions if we just had a better idea of where to begin.

Almost none of the constellations that fit in a 15x15 box will ever come up "naturally" from a glider collision. They could come from an engineered collision with a huge field of still lifes that produce gliders and do cleanup, but it is extremely unlikely that such a field will ever come from repeated collisions from a small starting point. Unfortunately, there is no way to prove it without intermediate bounds on the constellations in a collision sequence. But I suspect that the natural collision products that exceed a smallish bounding box will not really be useful (that's my heuristic and it would have been useful if I could get a positive result, but doesn't help with a negative one). It would certainly be miraculous (even more than the biloaf collision) if a glider hitting some big junky debris field just happened to create a rare <=15x15 constellation that also just happened to be useful and eventually got back to the collision that produced the debris field.

Another thing about big debris fields is that they are so sparse that a single glider will almost never consume them completely (only if they're engineered for that or if you're luckier than anyone has yet been).

What I think we have in our favor is that the step of colliding a target with a glider, keeping only results that emit a glider, extracting and dedupping the ash, seems to reduce the number of targets. (EDIT No: only with some additional filtering) The branching factor from generating collisions is pretty big, but the probability that any one of them even produces a glider is low enough that there is a net reduction (that was what I noticed yesterday, assuming I did not make a mistake; need to check that). (EDIT Oops, maybe that is just because I am restricting bounding box size to 20x20 in between collisions) BTW, in a CA without that empirical property, I can imagine my question being undecidable, since the intermediates could become arbitrarily complex (fixable with a bound on box size or cycle length, but not needed for Life I think).

Assuming the above, there is at least a (usually) effective procedure for resolving: given set S of constellations, is there a series of glider-emitting collisions that is cyclic and includes some A in S. You just create S, S_1, S_2, etc. until the set stabilizes. Then look for cycles in the union of results. Of course, you're not guaranteed the set will really stabilize like that, but if it does (as it seems to), you can answer the question one way or the other.

Could we do this with 10x10 starters or a reasonable subset? (EDIT I need to recheck my assumption about the target set not expanding)

Another thing I am excluding explicitly is a cycle of collisions that consumes a glider in one step but outputs an extra glider in another step. This is certainly possible, and might result in a useful pattern, but the negative result is hard enough in the restricted form.

EDIT: I think a series of collisions starting with a block that consumed gliders over some collisions but made up for it with a later excess and restored the block could be engineered using current techniques (right?). So that is excluded from the conjecture. In practice, all the intermediate states should be pretty small and the cycle should be short.

Though I think the conjecture is more elegant when the bounding box restriction is only on one step of the cycle, in practice, we could require that the target stays within a larger box for other steps. In that case, we can get the number of targets to go down with each iteration and we can resolve the question as above. I think it is nearly impossible that some giant debris field will be useful, though that is not mathematically sound reasoning.

[simsim314]

Is there a simple way to test this with modern tools?

I've recently written SLSparker which iterates and collide glider into set of 3SL in predefined by input file rectangular area. The search is using 53 common ash objects.

The only thing is left to add for your request is to modify the condition here - you're searching for 3SL leftover insead of generic list of sparks defined by the user. Current LifeAPI is also removing gliders. Yet LifeAPI is working on 64x64 grid. I hope to fix it soon - at least to work with 256 AVX. Hopefully will work with 16x16 tiles and predefined hash table for any common 16x16 constellations eventually.

Preparing the list of connectivity and searching for cycles inside this graph of connectivity is something entirely different.

[dvgrn]

Almost none of the constellations that fit in a 15x15 box will ever come up "naturally" from a glider collision.

That's certainly true in one sense: a lot of the constellations inside 15x15 are tightly packed square-looking stacks of a dozen or so objects --

Code: Select all

x = 15, y = 15, rule = B3/S23
2o2b2o3b2o2b2o$2o2b2o4bo2b2o$8bo$8b2o$4b2o6b2o$2o2b2o6b2o$2o$7b2o$3b2o
2b2o3b2o$3b2o7b2o2$2o7b2o$2o2b2o3b2o$4bobo6b2o$5b2o6b2o!
#C [[ THUMBNAIL THUMBSIZE 3 VIEWONLY NOSOURCE ]]

-- and statistically speaking these are very unusual. Maybe we don't even need to bother to look at constellations with uniform high density like this... but then again, we do occasionally run into small random-looking tight constellations like Guam's semi-Snark and the sidesnagger, where most of the objects are actually catalysts:

Code: Select all

x = 32, y = 33, rule = B3/S23
5bo$3bobo$4b2o2$9bo8b2o$7bobo8b2o$8b2o2$27b2o$26bobo$27bo4$23b2o$23b2o
$28b2o$28bobo$30bo$15b2o13b2o$16bo$13b3o6b2o$13bo8b2o2$6bo$5bobo$4bo2b
o3b2o$5b2o4b2o$bo$obo$2o$6b2o$6b2o!
#C [[ THUMBNAIL THUMBSIZE 3 NOSOURCE AUTOSTART PAUSE 2 LOOP 200 ]]

The semi-Snark is 19x19, not far from your 15x15 limit and kind of almost what you're looking for.

Another tangential thing I wanted to mention, just because it could maybe help develop intuition about what comes up naturally, is calcyman's SS (slow salvo) search tabulated on Catagolue. Just a dozen or so gliders can occasionally get you to some surprising places, like a block on griddle:

Code: Select all

x = 435, y = 372, rule = B3/S23
12b2o68b2o$11bo2bo66bo2bo$12b2o68b2o6$7b3o2$5bo6b2o$5bo5bobo73b3o$5bo
5b2o74bo$bo86bo$obo4b3o$obo$bo13$16b2o$15b2o$17bo8$122b3o$122bo$123bo
51$151b2o$150b2o$152bo26$189b3o$189bo$190bo26$211b3o$211bo$212bo26$
239b3o$239bo$240bo26$270b2o$269b2o$271bo51$344b2o$343b2o$345bo26$362b
2o$361b2o$363bo26$404b2o$403b2o$405bo26$433b2o$432b2o$434bo26$428b2o$
427b2o$429bo!

These searches throw away branches with glider outputs, of course -- if they didn't the search space would be quite impressively huge.

EDIT: I think a series of collisions starting with a block that consumed gliders over some collisions but made up for it with a later excess and restored the block could be engineered using current techniques (right?).

Right. It wouldn't be easy, but at least we don't have to appeal to the horrible "we can do everything because universal constructors". We could do it with just a large sparse constellation of reburnable blocks and a quick call to slsparse. You won't get a useful burst of gliders, but technically you can definitely break even! Here's the first pattern from the "reburnable blocks" link -- just imagine lengthening the block chains and starting with some one-time splitters to make several gliders from an initial trigger, and then a bunch more splitters to handle cleanup:

Code: Select all

x = 596, y = 422, rule = B3/S23
394b2o$394b2o3$389b2o$389b2o9$551b2o$551b2o10b2o$563b2o$298bo$296bobo$
297b2o252b2o$551b2o$517b2o$517b2o10b2o$529b2o3$517b2o75b2o$517b2o75b2o
$483b2o$483b2o10b2o$495b2o2$426b2o$426b2o55b2o$483b2o$449b2o$449b2o10b
2o$430b2o29b2o$430b2o2$449b2o120b2o$449b2o120b2o$415b2o$415b2o10b2o$
427b2o3$415b2o120b2o$415b2o120b2o6$503b2o$503b2o6$469b2o$469b2o6$435b
2o$435b2o5$319b2o$319b2o80b2o$346b2o53b2o$314b2o30b2o$314b2o45b2o$323b
2o4b2o30b2o$323b2o4b2o12$362b2o$362b2o33$313b2o$313b2o4$317b2o$317b2o
4$331b2o$331b2o3$326b2o$326b2o35$229b2o$229b2o3$224b2o$224b2o5$234b2o$
234b2o3$239b2o$239b2o13$180bo$178bobo$179b2o8$399b2o$399b2o16b2o$417b
2o5$365b2o$365b2o6$331b2o$331b2o3$172b2o$172b2o2$297b2o$297b2o$176b2o$
176b2o4$263b2o$208b2o53b2o$176b2o30b2o$176b2o45b2o$191b2o30b2o$191b2o
12$196b2o$196b2o90$57b2o$57b2o3$52b2o$52b2o26$83b2o176b2o$83b2o176b2o
16b2o$279b2o2$88b2o$88b2o2$227b2o$227b2o6$193b2o$193b2o2$28bo$26bobo$
27b2o2$159b2o$159b2o3$2o$2o2$125b2o$125b2o$4b2o$4b2o4$91b2o$36b2o53b2o
$4b2o30b2o$4b2o45b2o$19b2o30b2o$19b2o!

I think it is nearly impossible that some giant debris field will be useful, though that is not mathematically sound reasoning.

The problem is that nobody has ever systematically investigated dirty turners. Maybe a good thing to try looking into is 4-still-life-or-less constellations, that make a glider and make another 4sL constellation. Seems like a negative result might eventually be within reach there, but also something surprising might be found. Here's an example of a dirty turner, which would fit your criterion if it happened to make a medium-sized debris field as well as the boat... provided the debris field happened to be made up of other dirty turners whose leftovers just happened to be the initial three blocks.

-- "Nearly impossible" is probably a good estimate, but when we have this big a search space to work with, some values of "nearly impossible" multiply out to fairly decent odds of something being out there somewhere. There are a lot of dirty turners.

Large sparse debris fields might actually be particularly hopeful cases, since there will turn out be a toolkit of standard ways to burn some sufficiently well-separated debris. "Aha, there's a Herschel signature sticking out -- we can clean that up with X, Y, Z gliders and get three gliders out." (Not sure that actually exists, unfortunately -- Seeds of Destruction suggests a few options, but they're kind of explodey early on.)

For outliers where there's no convenient cleanup targeting them directly, it will often be possible to modify them with a one-glider-in, two-gliders-out reaction where one glider hits the outlier. Random not-very-good examples from Seeds of Destruction:

Code: Select all

x = 497, y = 326, rule = B3/S23
301bo$300bobo$132b2o166bobo$132b2o167bo2$296b2o7b2o$295bo2bo5bo2bo$
133b2o161b2o7b2o$132b2o$134bo167b2o$302b2o5$312b2o$311b2o$313bo5$141b
2o$140b2o$142bo4$325b2o$324b2o$326bo189$495b2o$494b2o$496bo102$3o$2bo$
bo!

[dvgrn]

Another thought that came up was your old century catalyst in the bistable switch, where a honeyfarm got regenerated in just the right place. Honeyfarms are common enough that their size is a little misleading when it comes to estimating the probability that they might reappear. Probably there are lots of other constellations like that, where something looks like a large and wildly probable debris field but the odds are actually relatively good of an exact reappearance.

Unfortunately you can't start with a honeyfarm and return to a honeyfarm, because there aren't any single glider collisions with a HF that release a single glider.

But what about traffic lights? The search tree certainly doesn't die out right away. Like the tree for isolated Herschel debris it's kind of explodey at least early on, but the size doesn't necessarily go totally out of control.

Here's a branch that contains a couple of possible replacement traffic lights. Seems like it might happen to be possible to clean up the remaining junk at one output glider per shot:

Code: Select all

x = 175, y = 160, rule = B3/S23
170bo$170bo$170bo2$160b3o3b3o3b3o$162bo$161bo8bo$170bo$170bo74$101bo$
101b2o$100bobo73$bo$b2o$obo!

There's a boat and a toad among the debris. Any time those (or long boats, long ships, eater1s, etc.) show up in the debris and can be isolated, there will be nice search-tree-expanding binary choices: we can search the pattern with those clean turners left in place, or with one or more of them taken out.

As the search gets longer, I suppose it will start to matter that input lanes will start to be forbidden by the lanes used up by the output gliders (?). Except for that limiting detail, it kind of looks to me like search targets might reach an equilibrium size: once the ash perimeter is long enough, the odds are pretty good that somewhere there are clean(ish) turners that can be removed.

You might be able to maintain a population of say ten thousand branches of the search tree, choosing new branches that reduce the cell count whenever possible. Some nodes will have multiple ways to reduce the population, and some will be dead ends. Maybe at some size that will average out, and after that equilibrium point you could keep searching pretty near forever (without running out of new branches, or increasing the average cell count or bounding box of the active branches). So it could be useful to keep track of input lanes that are forbidden due to previous output gliders, to keep the search tree down to a more workable size.

[pcallahan]

I think I missed seeing sidesnagger when it came out (semisnark looks familiar). A reasonable-sounding definition of initial constellations that happened to include sidesnagger might make a good starting set. Of course, it will be taken out fast since it does not produce gliders. A starting set like that might also turn up some new eaters if they're not filtered out.

Preparing the list of connectivity and searching for cycles inside this graph of connectivity is something entirely different.

I have never written reliable code for this, but it's not hard. The cycles should be pretty short anyway, and we will get deadends in a few links I think.

ADDED: I've convinced myself that the question is hopeless unless we put some restrictions on which collision products to continue trying. Based on a few tests, it seems if I start with a set of constellations and keep only the collision products that produce at least one glider and ash that fits in a 25x25 bounding box, then the set size decreases. For 30x30, it still increases.

Bounding box is kind of a blunt instrument. What I'm really after is ruling out collision products that are "obviously useless" (barring miracles, which unfortunately happen; see e.g. biloaf). But a collision that is probably not worth exploring would hit a large debris field, emit a glider, and then stabilize before consuming most of the field. It is really unlikely that these will be consumed over one or more glider-emitting collisions in the future, because these collisions are not all that common and most will just add to the debris (include non-glider-emitting collisions and all sorts of slow syntheses are imaginable from any debris).

So an open question is what is a good heuristic (besides size restrictions) for whether collision ash is worth exploring further.

[dvgrn]

But a collision that is probably not worth exploring would hit a large debris field, emit a glider, and then stabilize before consuming most of the field. It is really unlikely that these will be consumed over one or more glider-emitting collisions in the future, because these collisions are not all that common and most will just add to the debris (include non-glider-emitting collisions and all sorts of slow syntheses are imaginable from any debris).

So an open question is what is a good heuristic (besides size restrictions) for whether collision ash is worth exploring further.

Funny, after the sample traffic-light collision from my last post I've been thinking that a solution might well be findable that looks just like a series of those. I can't find one manually, but I wouldn't be at all surprised if a long enough search would turn one up.

The idea is to start with something ubiquitous like a traffic light and make a medium-sized mess, sparse enough that most of the ash can be hit by gliders from outside somehow. Then look for glider-emitting collisions that change as many ash objects as possible to into accessible clean turners. Each one of these collisions might affect only 10% of the ash, so there are a lot of different orderings to try.

When everything besides one traffic light is a clean one-time turner, the search has been successful! But you're not necessarily out of luck if you've only gotten _almost_ to that point. You can always sacrifice one or more of the one-time turners in an emergency, if you can hit them in some other way that also produces a glider (plus other ash to continue to try turning into one-time turners).

Sure, it will turn out that 99.9999% of random blobs of ash can't be converted into turners-plus-a-TL -- but one in a million odds don't actually seem all that bad in a search like this. It's not that computationally expensive to find all the accessible clean turners in a given ash field, given that we have to generate all possible glider collisions with the field anyway. So maybe a good metric would be the percentage of ash that's cleanable in this way -- with a big bonus if the original initial target is present in the ash.

[pcallahan]

When everything besides one traffic light is a clean one-time turner, the search has been successful!

That's a good point. I did not make any attempt to find collisions with ash that were actually just turners. It might be worth taking a second look. In fact, a boat might very well end up far from a more compact ash, and it would be a mistake to filter it out.

[dvgrn]

In fact, a boat might very well end up far from a more compact ash, and it would be a mistake to filter it out.

There are a lot of two-still-life clean turners also -- two blocks in a couple different ways, or a block plus some other still life. Nothing as common as a boat, of course, and most of them not even as common as a long boat or toad, which are next in order of likelihood on the clean-turners list followed by eater, aircraft carrier, and longship. But I bet a few fairly common larger constellations will turn out to be clean turners as well.

Even the block-plus-loaf and block-plus-boat splitters currently shown in the turner stamp collection would count as clean turners if one of the gliders happens to clean up some other piece of junk.

[pcallahan]

But I bet a few fairly common larger constellations will turn out to be clean turners as well.

Even the block-plus-loaf and block-plus-boat splitters currently shown in the turner stamp collection would count as clean turners if one of the gliders happens to clean up some other piece of junk.

You've convinced me to withdraw any conjecture, though I still think the question is interesting. The results would look more engineered than I was thinking. Your idea, I think, is to let the ash grow bigger, provided there is a way to clean it only with glider-producing collisions. This provides the branching factor needed to engineer the outcome.

Filtering over my old results, I can find, for instance, these reactions that delete a block in the presence of a blinker and emit a glider and produce another blinker in a new location. This is not exhaustive and it's only one type of reaction. So the search might just be how to clean a large field of ash using only turner reactions, extending the definition of turner to messy reactions that increase the size of the field. The starting point might be very simple, and you could get it back after cleaning. I am not sure how practical these would be as stable components.

Code: Select all

x = 14, y = 7, rule = B3/S23
o$o11b2o$o11b2o6$b2o$obo$2bo$!

Code: Select all

x = 14, y = 7, rule = B3/S23
2bo$obo$b2o10$11b3o7$8b2o$8b2o$!

Code: Select all

x = 18, y = 9, rule = B3/S23
2bo$obo$b2o7$17bo$17bo$17bo$9b2o$9b2o$!

Code: Select all

x = 14, y = 7, rule = B3/S23
2b3o7$2o$2o6$11b2o$11bobo$11bo$!

Code: Select all

x = 12, y = 6, rule = B3/S23
2bo6b3o$obo$b2o10$9b2o$9b2o$!

Code: Select all

x = 21, y = 9, rule = B3/S23
8bo$8bo$8bo2$2o$2o5$18b2o$18bobo$18bo$!

Code: Select all

x = 14, y = 6, rule = B3/S23
11bo$11bobo$2b3o6b2o6$2o$2o$!

[pcallahan]

Here is a proof of concept for dvgrn's suggestions (specifically his point that a large field of ash can be consumed over multiple glider collisions). Unfortunately, there is at least one step at which an escaping glider collides with an incoming glider. At that point, I lost interest in trying to make one big collision, but I want to report the results. Each step modifies the object it hits and also emits a glider. I start with a loaf and get a loaf in a new place after hitting it with 8 gliders (not synchronized, but they do have to match period-2 phase for blinkers), getting a new glider out each time.

I got this doing essentially the same search as before, but starting with just a loaf as the initial pattern, and not filtering by bounding box of the result. I did filter the population of the ash to 30 cells or fewer.

Once I had a target set that included a loaf, I backtracked over the old results using ad hoc techniques, filtering+visual to piece them together. Clearly, this could be automated and would have saved me hours.

Step 1

Code: Select all

x = 13, y = 16, rule = B3/S23
b2o$o2bo$obo$bo10$10b2o$10bobo$10bo!

Step 2

Code: Select all

x = 29, y = 18, rule = B3/S23
6b2o$6bobo$7b2o3$14b2o$14bobo$15bo$3o7$26b3o$26bo$27bo!

Step 3

Code: Select all

x = 27, y = 35, rule = B3/S23
13bo$14bo$12b3o8$24b2o$24b2o3$23bo$22bobo$22bobo$18b2o3bo$18b2o2$16bo$
16bo$16bo3$26bo$6bo19bo$6bo19bo$6bo6$3o!

Step 4 (which outputs a glider that collides with the next input)

Code: Select all

x = 27, y = 28, rule = B3/S23
3bo$bobo$2b2o6$14b2o$13bo2bo$14b2o3$14b2o$14b2o4$24b3o$4b3o6$o$o$o!

Steps 5-8

Code: Select all

x = 303, y = 195, rule = B3/S23
188bo$188bobo$188b2o10$179b2o11b3o$178bobo$179bo5$168bo$168bo$168bo50$
218b2o$218bobo$218bo63$300b2o$300bobo$300bo54$b2o$obo$2bo!

This convinces me that there is almost certainly a way to get from a small constellation back to itself with a series of glider-emitting collisions, and if there are enough of them, we can find one without diagonal conflicts. It isn't really what I want, which is a small stable component, but the engineered solution is a first step.

I was able to get from beehive back to beehive, but that took one more step, so I didn't backtrack through the solution, which is very time consuming. The more steps, the more likely there will be a diagonal conflict. If I consider more starting points, I might be able to find a shorter sequence and also avoid diagonal conflicts.

EDIT Here are the parts fitted together into a single pattern. I haven't optimized it in any way. I was putting it together by hand in Golly. Two output gliders collide with input gliders, so I patched these with gliders slightly ahead to delete the output. The rest is 10 gliders-in/7 gliders out (one hit produces an extra glider). This could be improved to 10-in/9-out I think, but it is not worth the effort.

Code: Select all

586bo$586bobo$586b2o2$581bo$581bobo$581b2o8$191bo$189bobo$190b2o70$
278bobo$279b2o$279bo124$377b2o$376bo2bo$376bobo$377bo10$386b2o$386bobo
$386bo38$432b2o$431b2o$433bo202$616b2o$616bobo$616bo57$689b2o$688b2o$
690bo4$698b2o$698bobo$698bo54$b2o$obo$2bo!

Here is the loaf displacement. Input is on the right, output on the left.

Code: Select all

2$27b2o$26bo2bo$26bobo$27bo$bo$obo$o2bo$b2o!

ADDED: As for a negative result, I still think there may not be any unknown objects like this if we restrict the size of the bounding box for the entire cycle to something like 15x15, which is really what I would like--a small pattern that can redirect gliders without consuming them and does not always block the same diagonals. This could be resolved by a search because if the box is small enough, the branching factor is <1 on average.

For larger patterns, the question is different. Basically, can you clear debris without wasting gliders, and use this process to restore the starting point. The answer to this seems to be yes, though I don't have an example with gliders on usable diagonals.

[pcallahan]

I just ran some scripts a little more carefully than before, starting with still life output from lifesrc, and I believe I can claim the following limited negative result:

For still life constellations 14 cells or less that fit in an 8x9 bounding box, there are only two distinct patterns that a can bit hit by a glider, emit at least one glider or spaceship, and reappear (possibly at a different position and orientation) after the collision without any additional non-moving objects.

One is the biloaf (14 cells in a 7x7 box) and the other is the 3-block glider shifter (12 cells in an 8x9 box). Each emits a single glider.

This does not surprise me, but it is intentionally limited to the search space where we've already found the results. It also does not address the question of whether longer cycles are possible. I thought there might be something out there that I had missed in the 90s and could find with faster searches, so my initial results were disappointing, but maybe there is something a little further out with relaxed criteria.

I'm revamping some of my old tools and trying to implement the less CPU-intensive parts in simpler python programs. Some important parts include removing gliders when necessary and putting patterns in a canonical form. I believe this part works, and I was able to find the two collisions above just by filtering the output without having to look over results in Golly.

ADDED: While I'm not as confident of my analysis on the following, when I updated the script to look for longer cycles (A -> B -> A, etc.) I still only found the two above. So I think any other results will require a larger bounding box and or more cells.

ADDED: I can find collisions that chain along from one to the next, but do not make a cycle. Here is one that ends up with the 3-block shifter (but sends an output glider along its input path).

Code: Select all

x = 143, y = 84, rule = B3/S23
5$72bo$73bo$71b3o5$76bo$75bobo$76bo3$79bo$78bobo$79bo37$123b2o$123bobo
$123bo6$16b3o$18bo$17bo!

[AforAmpere]

Would it be possible to use the script you used to collide gliders with small constellations, but replacing gliders with common patterns like b-heptominos, herschels, and other things? Has that already been done?

[pcallahan]

Would it be possible to use the script you used to collide gliders with small constellations, but replacing gliders with common patterns like b-heptominos, herschels, and other things? Has that already been done?

Setting up the collisions is not hard. But detecting whether the result produced a new herschel isn't as trivial as finding and removing a glider. I think I understand what you're getting at. Are there any natural herschel conduits out there that we could find in a search. Maybe. I don't have the spare cycles (CPU or personal) to work on that but it might be worth it if it as not been done yet.

ADDED: if we just wanted to know what collisions with b-heptominos produce gliders, that would be easier, but unless the constellation comes back at the same orientation, it doesn't get you much.