ConwayLife.com

Definition: Non trivial predecessor of a SL is a predecessor that doesn't contain the SL as a subset.

Question: can we prove or show otherwise that every SL has a non trivial predecessor? In other words can we prove that every SL has the potential to be synthesized?

Maybe we can call this property "weak synthesizability" (it's necessary but not sufficient).

simsim314 wrote:Definition: Non trivial predecessor of a SL is a predecessor that doesn't contain the SL as a subset.

Question: can we prove or show otherwise that every SL has a non trivial predecessor? In other words can we prove that every SL has the potential to be synthesized?

I certainly don't know the answer, but that seems like a good way to ask the question. If we can come up with a counterexample for this "Weak Synthesizability Conjecture", that will save a lot of trouble for anyone who might otherwise want to try to build a universal still-life synthesis toolkit.

(There's been a lot of success recently at adding cells around the edges of small still lifes to get slightly larger still lifes. But experience with <=16-bit still lifes may or may not not translate well to very delicately balanced 160-bit still lifes, which have a lot less accessible edge and a lot more inaccessible middle...!)

I think I see one possible issue with the definition, though:

Do internal OFF cells count as part of a still life? For example, does the following predecessor contain the pond as a subset? I.e., is this an example of a "trivial predecessor"?
Or should the pond be defined to include four central OFF cells, one of which is not present in this predecessor?

It seems to me that the above predecessor might be a perfectly good step toward a proof-by-example that the pond is constructible (if one were needed). So if we're effectively throwing away cases like this, might we be losing a useful tool?

-- On the other hand, I don't see how to patch the definition easily. Adding "internal" OFF cells brings up new questions, such as whether the central-spine OFF cells in a hat count as internal or not.

If the definition only applies to ON cells, then we'll have to look for any predecessor of a still life -- not necessarily a T-1 predecessor -- in which at least one of the ON cells is OFF. Right?

We could certainly hack together a WLS/JLS variant that could test any candidate still life, as long as we could look only for immediate predecessors: run a series of searches, each with one ON cell forced to be OFF at T=-1, and stop each search when the first predecessor is found.

If WLS/JLS can't find anything, we have a valid counterexample at least for the Immediate-Predecessor Weak Synthesizability Conjecture. Building likely candidates for this test will be the tricky part... but then it doesn't seem as if such a limited-cases counterexample would be very useful, anyway.

dvgrn wrote:If the definition only applies to ON cells, then we'll have to look for any predecessor of a still life -- not necessarily a T-1 predecessor -- in which at least one of the ON cells is OFF. Right?

Technically you're right - but this brings another question: is there a SL whose only predecessors contain it (by ON cells) in T-1 but has non trivial T-2 predecessor? I think this case is even less common than just non trivial predecessors, using the ON cell definition. Anyway technically we should look for any T-k predecessor and compare by ON cells alone.

dvgrn wrote:We could certainly hack together a WLS/JLS variant that could test any candidate still life, as long as we could look only for immediate predecessors: run a series of searches, each with one ON cell forced to be OFF at T=-1, and stop each search when the first predecessor is found.

I would say this could bring a useful information - how many non trivial predecessors there are for random large SL? Find the minimal number of predecessors for a large SL, and finally we could classify the edges of a SL and maybe find a universal way to find weak predecessor using some brute force proof.

The proof can go as follows: take an edge of a SL, take some surrounding of it say 5x5, find all possible options of a SL in this bounding box, and prove everyone of them has a non trivial predecessor, which keeps all the rest of the SL intact. If this will work, this could be the path to synthesis proof as well.

simsim314 wrote:The proof can go as follows: take an edge of a SL, take some surrounding of it say 5x5, find all possible options of a SL in this bounding box, and prove everyone of them has a non trivial predecessor, which keeps all the rest of the SL intact. If this will work, this could be the path to synthesis proof as well.

Seems like this will be a long and slow path to a synthesis proof. Or rather, this would be just a very small step towards a proof -- at least until someone comes up with a version of WLS/JLS that can reliably track these kinds of minimal-disturbance predecessors backwards until the disturbance is made out of nothing but gliders.

I think I might be slightly more hopeful about the other side of the bet -- that there might possibly be a medium-sized delicately balanced still life where the center section provably has no valid predecessors other than itself.

A counterexample to the Weak Synthesizability Conjecture would be really nice to have. It's another of the very old open problems, similar to the Grandfather problem and the Coolout Conjecture except those have been solved. The Coolout Conjecture has some interesting similarities to this current problem.

It occurs to me that there's another potential wrinkle here:

what if every still life provably has a non-trivial predecessor,
but there exist still lifes whose only non-trivial prececessors are Gardens of Eden?

That seems like it might be a good new version of the grandfather problem. It's different from the old unique-father problem [from Lifeline 6:1, "Is there a stable configuration whose only father is itself (with some fading junk some distance away not being counted)?"] There might be lots of parents, but if the parents are all harder to construct than the original pattern, then eventually you might hit a dead end no matter where you look.

It may be wishful thinking that any such thing exists. If it did exist, obviously it would prove that the Weak Synthesizability Conjecture is too weak, and universal SL synthesizability is an impossible goal even if the conjecture can be proved.

I hope there is a surprising result within reach along these lines, in one direction or the other.