Constructing All Still Lifes

[mscibing]

calcyman quoted a discussion of constructing all still lifes in the reverse caber-tosser thread:

Mainly to Harold:

Thanks for the papers on de Bruijn diagrams. Now, a lot of stuff
(at least the basic ideas) are starting to make a little bit of sense.

I am currently working on a related task, attempting to prove that
every still-life (finite or infinite) may be cut along an arbitary
horizontal boundary and everything below the line replaced by a small
finite stabilizer. If this can be proven rigorously (and I believe that it
can), we can prove that all infinite still-lifes can be made finite.

This is done by dividing up the universe into regions
...
aaaaa
aaaaa
aaaaa
bbbbb
ccccc
ddddd
eeeee
eeeee
eeeee
...
where 'a' is the interior of the still-life, is already stable, and has no
effect on the exterior.
'b' is just below the surface, is already stable, and influences row 'c',
'c' is at the surface, and may require stabilization from external row 'd',
'd' consists of cells 'outside' the still-life which we need to add to
stabilize row 'c',
and 'e' consists of anything else we need to stabilize 'd'.

By definition, for every still-life which is cut in this way, for every
sequence
'b' and 'c' in that still-life, there must exist at least one sequence 'd'
(i.e.
the row which occurs just below 'c' if the still-life is not cut).

The idea is to prove that for every possible sequence of 'b' and 'c', some
arbitrary 'd' can be chosen which stabilizes 'c', and is also itself
stabilizable by some arbitary 'e'.

The proof is somewhat similar to examining every edge in a de Bruijn
diagram of a (4,2) automata (the states 0,1,2,3 correspond to no cells,
'b' cell, 'c' cell, and 'b+c' cells being on in any specific column.) to
ensure that such edges preserve the 'c' cell. Wherever this is not
possible, any path leading through that edge must be re-routed through
a parallel edge connecting altered versions of the initial states.
We may replace states 0-3 by new states 4-7 as required (like 0-3
but with an additional 'd' cell.). Since 'd' cells may not always be
placed with impunity, finding optimal alternate paths requires some
trial and error.

So far, I have expanded a fair bit of the tree, and it seems like a
quite possible (although fairly tedious task.) I'lll mail the results
when (if?) I get finished.


A slightly more ambitius task which requires the above as a pre-requisite is
to define all such states at the exterior of a partially-constructed
still-life,
and find all mappings between such states and the corresponding states
in which one more cell is added to the interior:
... ...
aaaaa aaaaa
aaaaa aaaaa
abbbb aabbb
bbccc -> bbbcc
cccdd ccccd
ddddE ddddD
eeeee eeeee
eeeee eeeee
... ...
If cell E is the same as cell D, no translation is needed;
if they differ, a glider construction is required which flips
the state of the single bit (and possibly alters other bits
in 'e'); this will, of course, have no effect on the already-
constructed parts of the still-life 'a', 'b', and 'c'; only
'd' needs to be taken care of by taking care how 'e' is altered.

In the majority of cases in which 'e' is empty, this is not
likely to be a problem. However, if the local area of 'e'
contains a convoluted stabilizer, mucking with an inner cell
could be quite a problem. (On the other hand, such convoluted
stabilizers are usually forced by one obnoxious cell; if
that cell is the one which needs to be flipped, most of
the stabilizer could be removed as well.)

If every such state-transition can be provided with a glider
synthesis, we will have a proof that every still-life can be
constructed from gliders, one bit at a time.

(But don't hold your breath; this could involve thousands of
cases, and even though Dave Buckingham is the best person to
generate the syntheses, I am sure he is not enough of a
masochist to try to find them all!) Perhaps some kind of
automated search will be required here.


Has anyone else researched this area? (or determined that it is
either too trivial or intractible to bother?)


-- MDN

I did some investigation into just the first part of this project: finite stabilization. I tried to come up with a way to stabilize the c row iteratively with only limited look-ahead and was getting nowhere. So to get a sense of the problem I made a program to explore patterns that require a large number of d+e rows to stabilize.

So far I haven't found any still lives that require 6 d+e rows to stabilize. But I have found a largish number of example patterns that require 5 d+e rows to stabilize:

Code: Select all

x = 240, y = 220, rule = LifeHistory
3$72.A$3.A9.2A18.A6.2A.2A.A24.A.A19.A29.A5.2A2.2A4.2A42.A.A9.2A.2A5.
2A19.2A$.3A2.A4.A2.A16.3A2.A.A2.A.A.2A2.A.A19.A.3A14.A2.3A24.A2.3A2.A
2.A2.A3.A2.A2.A4.A11.A18.A2.2A.A9.A.A2.A.A2.A9.A8.A2.A$A3.3A4.2A17.A
3.3A.2A3.A3.3A.3A16.2A4.A13.3A3.A23.3A3.A2.A.2A5.A2.4A3.A.A10.3A16.3A
3.A8.A2.A.2A.3A8.3A9.3A$A.2A5.2A2.4A13.A.2A5.A.A2.2A8.A18.2A.A16.2A.A
26.2A.A.2A.A4.A.3A7.A.A2.2A4.2A3.A18.2A.2A7.A.2A.A8.A3.A5.A.A.3A$BABA
B2A3BABA3BA13.BABAB2ABA2B2ABAB7ABAB14.2ABABAB13.2ABABA3B2A19.2ABABA2B
A4BABABA4BAB3ABAB2A2BA3BA2B4A2BA12.2ABABA2BA3B2ABABA4B2A4BABABA2B5AB
2ABA2B4A2B2AB$5B2A2BA2B2A3B13.5B2AB3A2BA4BA2BA2B2A14.2A5B13.2A7B2A19.
2A6BA3B3A2BABAB3ABABA3BABA5BABA3B3A12.2A5BA3BAB2A3BABAB2A5B2ABAB2A10B
2A2B4A2B$.A.A6.2A2.A16.A.A8.A10.A19.A.A17.A.A27.A.A3.2A6.A.2A10.A.2A
5.A3.A18.A.A.2A2.A7.2A10.A.A4.2A.5A9.A$.2A.3A6.2A16.2A.4A.3A12.2A14.
2A.2A.A13.2A.2A.A23.2A.2A.A3.A.3A3.A3.3A7.A2.A9.3A12.2A.2A.A3.2A10.2A
3.4A2.A5.A.A2.A2.4A.4A$4.A2.A26.A2.A.A15.A15.A4.A14.A4.A2.2A20.A4.A2.
A2.A2.A3.3A2.A9.2A11.A13.A4.A.2A13.A2.A.A4.2A4.A.A4.2A2.A.A$4.A.A27.A
.A17.A16.A.3A15.A.2A.A.A.A20.A.2A.A.A3.A.A6.A39.A.2A.A2.A13.A.A14.A
12.3A$5.A29.A18.2A16.2A18.A.A.2A24.A.A.2A5.A48.A.A.2A16.A30.A9$11.A
10.2A$10.A.A4.2A3.A29.A19.A16.2A.A$10.A.A4.A2.A.A28.A.A16.3A11.2A.A2.
A.3A$3.2A4.2A.A.2A.A.2A.2A19.2A6.A.A2.A.2A9.A3.2A7.A2.A.2A6.A5.2A$4.A
7.A.A2.A5.A20.A5.2A2.3A.A.A.2A4.A.2A3.A5.A.2A4.5A2.A5.A$B3A3B3AB2A3BA
2B2ABAB16.B3A3B2A3B2A6BABA5BA2B4A2BAB3A2BAB2ABA3B3ABA3BAB$2BA5BA5BAB
2AB2AB2A16.2BA3BABAB2A3B3A2BA3BABAB2A5B4A3BA3B2A2BA5B2A3B2A$A3.A.A3.
5A2.A22.A3.A2.A2.A2.2A3.A.A.A.2A.A5.2A5.3A.A4.2A2.2A$4A.5A5.A3.2A.2A
16.4A.2A3.A3.A.2A.A.A.A3.A6.A2.3A4.4A.A4.A.4A$3.A5.A2.3A5.A.A20.A7.3A
2.A2.A3.A3.2A5.A.A.A2.A.A3.A.A.A2.A.A2.A$2.A2.2A5.A7.A.A19.A2.2A6.A.A
2.2A3.2A10.A4.2A.2A5.2A3.A$3.2A.A14.A21.2A.A7.A9$79.A$15.2A.2A2.2A54.
A.A$13.A2.A.A2.A.A19.A29.A4.A2.A.2A$2A.2A4.2A2.2A.A.A.2A.A.2A14.3A2.
2A.2A20.3A3.2A.2A.A$A3.A3.A2.A.A2.A2.A3.A2.A13.A5.A3.A19.A9.A2.A3.A$
2B2A5B2A2BAB2A3B2A2BA2B13.AB2A3B2A2B19.AB2A3B2A3BA3BABA$B2A3B3A4BA2BA
BABAB3ABA13.B2A5B2AB19.B2A4B2ABABABA2BAB$4.A2.A2.3A.A2.A.A5.2A17.A.A
3.A23.A5.2A.A.2A$.2A.2A3.2A3.2A.A.A.3A17.2A.2A.3A21.2A.5A4.A$2.A11.A
2.A2.A.A.3A15.A4.A24.A5.A.2A.A$2.A.2A10.2A8.A15.A.2A.A24.A.2A3.A.A.2A
$3.A.A37.A.A.2A24.A.A10$4.A6.A$4.3A.A.A.A$7.2A.A2.A$4.2A4.3A.A$B2A2B
2AB2A3BAB$2B2A3B2A2B2A2B$A3.2A4.2A$2A.A2.4A3.A$4.2A4.3A.A$6.4A2.A.A$
6.A2.A3.A10$13.2A$13.A$.2A11.A$A2.A9.2A$ABA2B2A3B2A3B$B2AB2A3BABAB2A$
3.A3.A2.A2.A$3.A.2A.2A3.A$4.A.A3.3A$7.3A2.A.A$9.A3.2A10$9.A11.2A5.2A
6.2A$7.3A9.A2.A4.A2.A.2A.A2.A5.A$A2.2A.A12.2A.A.A2.A2.A.A3.2A4.3A$4A
3.A13.A.A.A.A.2A3.2A5.A$5B2A2B2A6B3ABA3BABA2BA2B2A2B3A2BA3B2A$2BAB2A
4BA3BABABABAB4AB2ABABA3B2A2B3A3B2A$2.2A3.A2.A.3A.A5.A7.A.4A3.A$5.2A.A
.2A4.A5.A.2A.3A5.A.2A.A.3A$6.A.A4.2A.2A5.A.A.A6.A2.A2.A.A2.A$6.A.A.3A
.A.A2.A15.2A2.2A.A.A$7.2A.A7.2A23.A10$15.A$11.A.3A$11.2A$9.2A3.4A$2A
6BA3B2ABA2BAB2A$2A2BA3B2AB2A4B2ABAB$4.3A.A5.3A4.A$7.A2.4A.A2.3A$6.A4.
A5.2A$5.A3.A$5.2A2.2A10$12.2A$8.A4.A3.A$6.3A2.A5.3A8.A$5.A3.4A7.A6.A.
A$4BA2BA5BAB3AB2A5BA2BAB$AB3AB3ABA2B2ABA6BABA3B2A$2A3.A3.2A7.6A.2A$3.
2A2.A9.2A5.A2.A$4.A.2A.4A8.3A2.2A$4.A2.A.A2.A8.A$5.2A10$12.A4.2A4.A$
3.A2.A2.A2.3A.A.A3.A.A.A7.A5.2A$3.4A2.3A3.2A5.A.A.3A3.3A4.A.A5.2A$12.
2A3.A2.2A2.A4.A.A7.A.A.2A3.A$B10ABAB3A2BABABA2B2ABABA2B3AB2A2B2A2BA2B
$2BA3BA3B2A4BAB2A3B2AB2ABABABABA3BA5B3AB$A3.A3.A9.A2.A2.A5.A2.A3.2A9.
A$4A.4A.4A4.A.2A.A2.4A3.2A3.A.A.2A3.2A$3.A6.A2.A5.A2.A.2A11.A2.2A.A$
2.A2.2A3.A.A8.A2.A2.A9.2A$3.2A.A4.A10.2A2.2A10$6.A19.A$5.A.A.A6.A9.3A
16.A.A$5.A2.2A5.A.A11.A4.2A.2A5.A.2A$4.2A9.A2.A5.5A6.A.A6.A$6B4A3B2AB
2A6BA3BABA2BA3BA5B2AB2A$AB3A3BA3BABA3B3A5BA3B5A2B3A3BA2B2A$2A.A.2A3.A
2.A2.2A3.A3.2A.A11.A3.A$7.3A.2A4.A2.A7.2A.2A6.2A4.3A$7.A3.A5.A.A8.A3.
A14.A$11.A.A4.A10.A.A$12.2A14.2A.2A10$4.A$3.A.A.A$3.A.A.3A8.2A.A2.A$
2.2A.A4.A2.A3.A.A.4A$A5B3AB4A3BA7B$3AB2A2BA7B2ABAB4A$3.2A2.A2.2A6.A.
2A2.A$2A4.2A.2A.A5.A$.A.3A2.A4.A5.3A$.A.A3.A2.2A.A7.A$2.A5.2A.A.2A!

(The b and c rows are highlighted.)

To prove that all still lives can be stabilized I'm planning to construct a decision tree for picking d and e cells based on the d and e cells picked so far and some bounded lookahead of b and c cells. I think where I was going wrong was in looking ahead the same amount in all parts of the decision tree, which meant I couldn't look ahead very far without blowing out my memory. I don't see any indication in the examples so far that the needed lookahead wouldn't be bounded so I'm hopeful that the number of cases to consider will be finite, and that by varying the lookahead in different parts of the tree I can keep the number of cases reasonable.

The other complication to building such a decision tree is that some combinations of b and c can't be stabilized at all and it's important to recognize and avoid all these cases to avoid the build failing.

[Kazyan]

There exists a family of still lifes that require more than 6 rows, as first discovered by Martin Grant here. This method will not be able to construct this family.

[mscibing]

There exists a family of still lifes that require more than 6 rows, as first discovered by Martin Grant here. This method will not be able to construct this family.

Ah, thank you. I won't attempt to prove the impossible then. And because the d row is forced in that example going to p2 for the stabilization won't help.

[calcyman]

Since there's now a thread about constructing all still-lifes, it's a convenient location to reiterate a few ideas.

To prove that every stable pattern is constructible, it suffices to show that for every non-empty stable pattern X there exists a simpler stable pattern X' such that there is a glider synthesis which converts X' into X. 'Simpler' can be any well-founded relation on the set of all stable patterns: Mark Niemiec uses a partial order where cell count is the main metric, with various tie-breakers dependent on what motifs are present. Well-foundedness basically means that the sequence:

X <-- X' <-- X'' <-- X''' <-- X'''' <--- ...

eventually terminates (in finitely many steps) with the empty pattern, so you can run the synthesis in the direction of the arrows above to obtain X.

When we stratify by cell-count (and quotient out by translations), something remarkable happens: even though there are infinitely many stable patterns with n >= 8 cells (take the disjoint union of two blocks separated by a huge distance), all but finitely many are extremely sparse and can be removed from consideration. The argument goes like this:

Code: Select all

x = 44, y = 22, rule = LifeHistory
B10.B6.B6.B6.B10.B2$2.B8.B6.B6.B6.B8.B2$4.B6.B6.B6.B6.B6.B2$6.32B$7.
30B$8.28B$9.26B$10.6B4D2A3D2AD6B$11.6B2DA2DA2D2A6B$12.6B2DADA3D6B$13.
6B2DA3D6B$14.6B4D6B$15.6B2D6B$16.12B$17.10B$18.8B$19.6B$20.4B$21.2B!

• Assume, by the inductive hypothesis, that every stable pattern of <= n-1 cells can be constructed by gliders.
• Then every stable pattern of <= n-1 cells within a size-R red triangle (see above) can be constructed by a synthesis of gliders from the northwest and northeast such that the synthesis reaction envelope doesn't extend more than f(n-1, R) half-diagonals to the south-west or to the south-east of that original R-by-R bounding box (i.e. stays within the blue triangle or above it), where f is some function. This is true because there are only finitely many such patterns, so we can take f(n-1, R) to be the maximum of the reaction envelope overshoot across those patterns.
• Let Y initially be an arbitrary cell in the uppermost row of the pattern X. Then expand Y by iteratively including any cells within its radius-2 Moore neighbourhood. Then let R be the size of the smallest red triangle containing Y, and expand Y by including any cells within the blue triangle of radius f(n-1, R). Keep repeating this iteration until we reach a fixed point. The resulting Y definitely can't be larger than g^n(1), where g(R) := f(n-1, R + 2n). So if Y is the whole of X, then X must be smaller than g^n(1) -- and there are finitely many such configurations -- or Y must be a proper subset of X which can be synthesised independently from the rest of X, and we also win.

This argument may seem very ineffective (it provides awful bounds), but it does allow an easier inductive proof: it means that instead of needing a well-founded relation 'simpler', it suffices to use an acyclic relation 'simpler' (on the set of stable patterns up to translation) with the property that a lower-cell-count pattern is always considered simpler than a higher-cell-count pattern.

To clarify, read the https://en.wikipedia.org/wiki/M%C3%BCnchhausen_trilemma -- the above argument handles the problem of infinite regress, which means that we only need to avoid circular reasoning (by stipulating that the relation 'simpler' is acyclic) and non-empty irreducible configurations (by showing that they're all reducible to something simpler).

I have some ideas about what relation to use, such that it satisfies acyclicity whilst also being amenable to showing (with a finite amount of work) that all configurations are reducible.