Here's an idea for a pattern search. I don't really have the time to do this search myself, but let me describe the general strategy, in case someone would like to take it up or comment on it.
3 steps:
1) Make a database of simple stable patterns (collections of still lifes, with less than N cells) which, when hit by a single glider, create another simple stable pattern (also of less than N cells) plus 1 or more escaping gliders. Let's call these "fluff", and imagine that we have built the database up to billions of rows.
2) Search the fluff catalog for cycles (for example, A --> B --> C --> A), ignoring glider inputs and outputs for now. Let's call these cycles "components". Imagine there are thousands of components.
3) Assemble components into glider relays. Some components will have a translation of (0, 0), making them good for constructing oscillators or guns; others will have other translations, for more interesting patterns. The nice thing about a glider relay is that you could control the period by spacing components farther apart.
Notes:
* In step 1, any fluff that translates to itself might be a small, stable reflector.
* It is possible this search will yield nothing, because although you can make the number of fluff entries explode exponentially by increasing the allowable complexity, the probability of being useful in a component plummets as that complexity increases, so you just don't get very many components, and those components are very hard to work with because they are picky in their glider paths. On the other hand, you don't know if you don't search.
* This search makes some simplifying assumptions. One is that useful fluff will take exactly 1 glider. There might be useful fluff that requires 2 or more gliders for input, but step 3 will be hard enough with single-glider transformations.
* The most interesting thing might be components that have translations other than (0, 0), especially the non-orthogonal or non-diagonal ones, since they could yield spaceships of unusual velocities.
* Anything built in this way would probably be easily glider-constructible.
Pattern search idea: Fluff Relays
Re: Pattern search idea: Fluff Relays
Two very preliminary thoughs.
1) The fluff database is probably going to be dominated by reactions that output a Herschel in some direction, with secondary contributions from block-and-gliders, octominoes, and possibly the tail-ends of Rs.
2) This kind of database sounds like it might be useful for glider construction purposes as well.
1) The fluff database is probably going to be dominated by reactions that output a Herschel in some direction, with secondary contributions from block-and-gliders, octominoes, and possibly the tail-ends of Rs.
2) This kind of database sounds like it might be useful for glider construction purposes as well.
Re: Pattern search idea: Fluff Relays
Interesting idea! It reminds me vaguely of factoring algorithms such as MPQS, particularly the "large prime" variant.
For cell counts that are large enough to be interesting there will be an infinite number of collections of still lives, separated by arbitrarily large distances. Constraining the pattern size will be necessary too, to keep the search space finite.
The output patterns could appear rotated or reflected as well as translated, so the cycles will have an overall rotation/reflection as well as a translation. This might allow for finding larger cycles - eg a cycle of N components which translates its still life and rotates it 90 degrees can be repeated 4 times to eventually return to its starting state.
A cycle which produces as many gliders as it consumes is a candidate for constructing an oscillator (possibly an infinite agar). A cycle which produces more gliders than it consumes could form the basis for a gun.
A cycle whose output appears translated could perhaps be used to construct a spaceship, a bit like the "Caterpillar".
I think most of the technology to perform this search exists already. I can easily modify one part of my searcher to enumerate all still lives in an NxN region. The output of this can be fed into gencols to generate the collisions; this step will take most of the time, but can easily be parallelised / distributed. The rest of the work is in filtering and classifying the output of gencols - I'm not sure if anything like this exists already.
If the intermediate patterns are still lives then there is a lot of flexibility in the timing. However this constrains the search space. It would be possible instead to search for fluffs based on any pattern that fits in say an NxN square. However combining these into cycles will place much tighter constraints on the timing of the input gliders.
For cell counts that are large enough to be interesting there will be an infinite number of collections of still lives, separated by arbitrarily large distances. Constraining the pattern size will be necessary too, to keep the search space finite.
The output patterns could appear rotated or reflected as well as translated, so the cycles will have an overall rotation/reflection as well as a translation. This might allow for finding larger cycles - eg a cycle of N components which translates its still life and rotates it 90 degrees can be repeated 4 times to eventually return to its starting state.
A cycle which produces as many gliders as it consumes is a candidate for constructing an oscillator (possibly an infinite agar). A cycle which produces more gliders than it consumes could form the basis for a gun.
A cycle whose output appears translated could perhaps be used to construct a spaceship, a bit like the "Caterpillar".
I think most of the technology to perform this search exists already. I can easily modify one part of my searcher to enumerate all still lives in an NxN region. The output of this can be fed into gencols to generate the collisions; this step will take most of the time, but can easily be parallelised / distributed. The rest of the work is in filtering and classifying the output of gencols - I'm not sure if anything like this exists already.
If the intermediate patterns are still lives then there is a lot of flexibility in the timing. However this constrains the search space. It would be possible instead to search for fluffs based on any pattern that fits in say an NxN square. However combining these into cycles will place much tighter constraints on the timing of the input gliders.
My gut feeling is that this is unlikely. Herschels, B-heptominoes etc have been remarkably rare in my searches. The loafer-to-herschel was a very lucky find.Tropylium wrote:1) The fluff database is probably going to be dominated by reactions that output a Herschel in some direction, with secondary contributions from block-and-gliders, octominoes, and possibly the tail-ends of Rs.
Re: Pattern search idea: Fluff Relays
Probably not clean Herschels, no. (And sometimes you get just the "stage 3" that only releases one glider.) But they're the most frequent glider-creating reaction from 1st-order collisions with simple still lifes at least…
OK, running 16 10×10 soups. 10 gliders observed from Herschels; 15 from all other sources.
Perhaps not necessarily "dominating", but it's clearly the major single source of gliders anyway (much in the same way a plurality of toads comes from failed centuries or octominoes).
What I'm getting at is that fluffs containing the full or partial three-blocks-and-ship end pattern would seem to have much better odds of being resynthesized than any random constellation of similar size.
OK, running 16 10×10 soups. 10 gliders observed from Herschels; 15 from all other sources.
Perhaps not necessarily "dominating", but it's clearly the major single source of gliders anyway (much in the same way a plurality of toads comes from failed centuries or octominoes).
What I'm getting at is that fluffs containing the full or partial three-blocks-and-ship end pattern would seem to have much better odds of being resynthesized than any random constellation of similar size.
Re: Pattern search idea: Fluff Relays
Resynthesized some distance away, anyway -- since the three-blocks-and-ship will generally happen only in pure vacuum (though there are a few exceptions of course) it seems fairly unlikely that that constellation would get cleanly destroyed and then move back in to the same spot.Tropylium wrote:What I'm getting at is that fluffs containing the full or partial three-blocks-and-ship end pattern would seem to have much better odds of being resynthesized than any random constellation of similar size.
I've been thinking about these "fluff relays" recently in the context of knightlife's recent postings about glider splitters and other Blockic single-use and multi-use devices. As I look at different suppression options for a blocks-only glider collision, I'm often pleasantly surprised by how often the final ash settles down to just a few scattered blocks.
I haven't seen any cases yet where the block pattern is a lucky accident -- a two- or three-block glider turner, let's say, or something else that might be re-used -- but I've seen so many block groupings go by in the Seeds-of-Destruction game now that a large-database approach seems likely to turn up some interesting overlaps.