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
Let's focus on number 7 from the top, shifted to make the structure clearer:
#C [[ THUMBNAIL ]]
x = 6, y = 3, rule = B3/S23:T6,3
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.