Spider synthesis

[18booster]

Is it known how to synthesize a c/5 spider from gliders (and possibly other tools such as bocks and blinkers)?

[Paul Tooke]

18booster wrote:

Is it known how to synthesize a c/5 spider from gliders (and possibly other tools such as b[l]ocks and blinkers)?

No.

The only spaceships in Life which have constructions are the standard spaceships (i.e the glider, LWSS, MWSS & HWSS, but then you knew that), some Corderships and a 2c/5 spaceship discovered by Tim Coe which proved tractable because its central components could be produced by perturbing constructible still lifes. (EDIT: and of course Gemini, but that really is a special case).

David Buckingham, an incomparable glider synthesis expert, has described spaceships which, like the Spider, can be found by search programs but don't occur naturally, as "spacedust". By this he meant: inconstructible. The task of constructing such a spaceship has been likened to building a Formula-1 race car whilst it's on the track and travelling at 200mph. I'm paraphrasing, because I can't remember the exact quote or who wrote this but I'm sure that you get my drift.

That said, all(!) that it takes to turn my "no"into a "yes" is for some enterprising individual who either won't take no for an answer or who appreciates the difference between "it hasn't happened" and "it can't happen" to take a strong interest in making it happen.

[Karatorian]

Just figured I'd point out that it's thought that the caterpillar is also synthesize-able. Not that anybody has, but the basic components (blinkers, gliders, spaceships, and pi heptominos) all have synthesis recipes.

I've messed around with trying to synthesis some of the smaller c/3 ships, but I haven't had any luck so far.

[dvgrn]

The only spaceships in Life which have constructions are the standard spaceships (i.e the glider, LWSS, MWSS & HWSS, but then you knew that), some Corderships and a 2c/5 spaceship discovered by Tim Coe which proved tractable because its central components could be produced by perturbing constructible still lifes. (EDIT: and of course Gemini, but that really is a special case).

And a lot of combined-*WSS-with-tagalongs, like the Big A spaceship -- more special cases...

David Buckingham, an incomparable glider synthesis expert, has described spaceships which, like the Spider, can be found by search programs but don't occur naturally, as "spacedust". By this he meant: inconstructible. The task of constructing such a spaceship has been likened to building a Formula-1 race car whilst it's on the track and travelling at 200mph. I'm paraphrasing, because I can't remember the exact quote or who wrote this but I'm sure that you get my drift.

That said, all(!) that it takes to turn my "no"into a "yes" is for some enterprising individual who either won't take no for an answer or who appreciates the difference between "it hasn't happened" and "it can't happen" to take a strong interest in making it happen.

Here are a few wild speculations on how the "no" might turn into a "yes":

I think it's quite likely that there are syntheses "out there" for many or most medium-sized spaceships -- darts, weekenders, spiders, and so on. The problem is not that it's hard to find possible ancestor patterns that might be useful in a synthesis -- it's easy to generate a wide variety with tools like lifesrc / WinLifeSearch / JLS -- but rather that there are too many of them to sort through. Brute force searches tend to very quickly wander off into areas of search space that would require billions of years on planet-sized computers.

It's easy enough, but not useful, to find a 10-generation predecessor of a spider that's just a patch of "space dust" much bigger than 30x7 -- that just gives you a more difficult synthesis problem than you had before. Conversely, if you find a 10-tick ancestor that _does_ fit in 30x7, it's pretty much bound to be another spider... ancestors are basically guaranteed to get bigger, on average, as you go back in time.

So you're bound to exceed your CPU capabilities before too long, even if you set up a distributed search. The trick will be to somehow bias a backtracking search so that with every step backwards, it finds ancestor patterns that are reliably more constructible than the original -- whatever "more constructible" means.

The easiest line of attack might be to sort out ancestors that are closer to stable toward the center, with as thin as possible a ring of active cells around the outside edge. The search area might expand at the speed of light as you go back in time -- or even faster -- but as long as the active area stays the same size or shrinks, you might still have a manageable search problem.

Bonus points if the stable area looks like small constructible still lifes (or small constructible oscillators would be fine, too)... and more bonus points if the active area looks like gliders or *WSSes, or their collision byproducts. But that's starting to sound like a tall order, requiring some very clever programming. I've started trying to write a "biased backtracker" utility several times in the last decade, but so far haven't been able to cut the search space down enough (without cutting it down so far that I don't get any results at all).

[Paul Tooke]

dvgrn wrote:

And a lot of combined-*WSS-with-tagalongs, like the Big A spaceship -- more special cases...

Hmm, yes, that's me shooting from the hip. The basic point I was trying to make though is that 'unnatural' spaceships like the Spider, those that came out of computer searches, are difficult to construct and may be inconstructible.

Your thoughts on the possible search program are similar to thoughts I've had in the past, but never taken very far. I'd add bonus points based on wider separation of components, particularly at the edges (I'm thinking divide & conquer). I'd also have an auxiliary search that investigated glider collisions and glider + still life collisions looking for isolated active fragments on the edge of the reaction envelope. Ancestors having such active patterns at their edges would likewise be awarded bonuses.

The search space is indeed huge, but is this such a bad thing? It pretty much rules out exhaustive searches (until our grandchildren run them on their 64 kqubit cellphones) but it does mean that, working backwards, at each generation we can cull a large number of unsuitable possibilities whilst still having a reasonable expectation of finding a solution based on one of those that remain. A backtracking search with a really good search order heuristic could work. It's perfecting that heuristic that's going to take the work.

[Macbi]

How does one even find the 1-generation ancestors of a pattern quickly?

[Paul Tooke]

Macbi wrote:

How does one even find the 1-generation ancestors of a pattern quickly?

Lookup the -p (parent option) for lifesrc. Maybe it also works for the derived program, WLS. I haven't checked.

[calcyman]

until our grandchildren run them on their 64 kqubit cellphones

A quantum Commodore 64! It can show every possible 'syntax error' at the same time!