ConwayLife.com

On 10th August 1994, Mark Niemiec wrote: 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

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!

Kazyan wrote: ↑

October 4th, 2020, 6:38 pm

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.

• 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.