I got together with Ville Salo this week to think about this self-forcing agar. We ended up solving the generalized version of the grandfather problem (
https://www.conwaylife.com/wiki/Grandfather_problem): for all n there exists a pattern that has an nth predecessor but not an (n+1)st predecessor.
I'll sketch the proof below.
So, it turns out that up to shifts and reflections, there are exactly eleven 6x3-periodic still life agars with unique predecessors.
For each of them, if you repeat the pattern a certain (finite) number of rows/columns in each direction, the central 6x3 patch of each preimage is forced to be the original pattern, just like with the first one I found.
Code: Select all
000101
011010
101001
000101
010010
111010
001001
010110
110010
001001
001011
110100
000001
001011
111100
000101
011001
101010
000001
011100
101011
000001
011110
110010
000101
011010
110010
000001
010110
111010
000000
010111
111010
Let's focus on number 7 from the top, shifted to make the structure clearer:
Code:
Select all
#C [[ THUMBNAIL ]]
x = 6, y = 3, rule = B3/S23:T6,3
ooobbb$
bobooo$
bbbbob!
It happens to have the following additional property: all finite perturbations spread to the left and right at lightspeed. More explicitly, let X be the infinite agar, and let Y be any other universe that differs from X in some finite set of cells. If the leftmost difference between X and Y is in column i, then the leftmost difference between X and the successor of Y is in column i-1. Symmetrically for the rightmost difference. The proof is a simple case analysis: depending on which column of the agar pattern i is, let (i,j) be either the highest or lowest cell on that column that differs between X and Y, and check that in each case one of the cells (i-1,j-1), (i-1,j) or (i-1,j+1) of Y will be flipped on the next step.
Using the above property we construct, for any given n, a pattern with an nth predecessor but not an (n+1)st one. Start with a large patch of the agar and flip one cell in the center. Let this pattern P evolve for n steps and call the result Q. If the initial patch was large enough, Q still has a large patch of the agar that now contains a perturbation of width 2n+1.
This Q has at least one nth predecessor, namely P. Suppose for a contradiction that it has a chain of n+1 predecessors R(0), R(1), R(2), ... R(n+1) = Q. If the initial patch was large enough, the self-forcing property of the agar pattern guarantees that each R(i) contains a "ring" of the agar pattern around the central cell. They are positioned so that the ring of R(i) is contained in the ring or R(i+1). The thickness of the rings decreases at a constant rate as we decrease i, so we can guarantee that R(0) has a ring of thickness at least 2. Since Q contains a finite perturbation of the agar, it has to come from somewhere, so R(0) also contains a finite perturbation inside the ring. If the width of that perturbation is w, then it will spread into a perturbation of width w+2(n+1) in R(n+1) = Q. But the perturbation in Q has width 2n+1 < w+2(n+1), a contradiction. End of proof sketch.
Now, the neat thing about this proof technique is that it can be automated, in the sense that I can write a script (and hopefully will find the time to do so) that takes in a CA rule and searches for a self-forcing agar pattern with the property that all finite perturbations spread in opposite directions at constant speed. In fact I first verified the property with a program, followed by Ville doing the case analysis on paper. If the script finds such an agar, the above argument shows that the input CA also has patterns with nth-but-not-(n+1)st predecessors for all n.
Our proof works as such for 15 other totalistic rules, since we don't actually care what happens to live cells with 0, 7 or 8 live neighbors, or dead cells with 8 live neighbors; these patterns just don't occur in the agar nor come up in the case analysis.
