(Never mind, I found a problem.)
First off, we assume that if the center column is periodic, it has a transient delay before showing it; that is, the very first cell cannot be the start of some cycle. I believe this follows readily from several things, perhaps most importantly that there is an implicit infinite structure which precludes this exact configuration from being allowed to repeat. This also completes limited self-similarity in an intriguing way, but that can wait for another day.
So if it is periodic, there is some row \(n\) at which the actual cycle begins. We're able to use this constraint to remove all but a handful of possible cases, which can be discounted through inspection.
Consider the first \(k\) periodic column cells (whether it's a partial or complete period is irrelevant for our purposes). There must be a corresponding horizontal row intersecting that topmost periodic column cell, where the portion of the row we care about extends from \(-k\) to \(+k\). This forms the spacetime light-cone, if you will, which is able to affect any one of our \(k\) column cells. Nothing outside of this region has a direct bearing on our column, in the sense that the horizontal row completely defines what values our column cells must take.
We can consider what happens as we look further down the column\(-\)that is, as \(k\) increases. For each row we descend, we must also widen to include an additional column on either side of the relevant section of our horizontal generator row.
These diagrams show all \(3 \times 2\) legal configurations that can arise which feature \(1,0\) in the center. This then expands to \(5 \times 3\) to give us a center of \(1,0,1\), and so on, for several steps.
Several important things to notice:
- We are restricting ourselves to only considering spacetime patches with \(0,1,0,0,1,0,\ldots\) in the center column.
- Even despite this, the number of legal arrangements exactly doubles with each expansion. This seems to be a general rule.
- Most of the diagrams are grayed out. This is to show that these diagrams could not possibly have followed one of the smaller prior diagrams, and must therefore be located somewhere else in spacetime. For instance, in the second row, only one diagram is allowed. You can see that if you remove the sides and bottom, it is the same as the first diagram on the right, meaning that the larger diagram is possibly the same structure, but with a wider view, which cannot be true for the other three in that row.
- The numbers were originally used for determining which diagrams can follow which, but really, it's easier just to see whether you can add an outer edge to the smaller one that results in a bigger one.
Naturally, all that grayed out stuff isn't really necessary. From here out we omit all non-relevant diagrams, giving us a more streamlined look, like so:
In this case, not only do the later diagrams not match up with the earlier ones, but there at \(n=4\), there is no matching diagram at all, which means we can immediately discount the entire branch.
Now let's take a look at what we get when we step through all legal progressions given some sequence, where the sequence is a \(2\)-to-\(12\)-bit binary word, all of which are tried here.
(The sequences being used for each column are shown as the leftmost list of \(0\)s and \(1\)s.)
There isn't too much we can tell yet. Let's go a couple of steps further:
Now what looks like some regularity is beginning to emerge. For the moment, we seem to have stopped at \(12\) valid configurations, and indeed, I expect there are \(12\) indefinitely.
They are all of a few certain special types, but we'll skip ahead one last time for clarity, to column lengths \(11\) and \(12\):
These are all essentially trivial or degenerative forms. The top two take advantage of the fact that
000 leads to
0, and they will never change, and could not occur in our context.
The second type are the ones that are essentially just the top of the standard one-cell initial configuration, which is interesting. They also include an extra line or two up there, which is complete allowed; the left line is actually implied if we don't decree time starts at the first cell, while everything to the right is indeterminate and could be anything.
The more important point is that obviously these are not able to yield periodic output, as by our earlier assertion, our periodicity doesn't start until later; all of these forms can be safely ignored.
This leaves only the striped ones. Similar to the last case, they're all reminiscent of a starting configuration using a 01 background, which is the only case that really impacts Rule 30:
No other background is able to cross the center line and/or remove the periodic cruft that accumulates on the left. This is because this background cripples the primary mechanism of operation behind Rule 30, a dependence on a conditional-NOR when
00 is encountered.
The bottom line is that this disqualifies these configurations as well. To continue indefinitely would require an infinite background tiling of
01, obviously a dealbreaker. More to the point, all of them are stuck in loops at this point after a little inspection. They will trivially spam the periodic
0 respectively, but these situations could not arise in our one-cell-origin scenario (remember, we haven't explicitly incorporated that constraint anywhere). Furthermore, all but one of them has a few mixed cells at the beginning, disqualifying them from being immediately periodic, assuming they only emit
1s from now on.
As a total digression, there are many, many equivalent formulations of Rule 30; saying it's
a XOR (b OR c) is fine if you like that sort of thing. What I find the simplest is shifting everything to the right, so that it's the left cell below a given three inputs which is affected instead of the center cell (see diagram below). Then, the only rule you need is to go down a column and NOT everything, unless there's a
00 to the right, in which case it carries down unchanged. The shift changes the appearance, but not any of the logic or content of the field:
With this layout, you can also discern some triangle-tiling techniques similar to other well-known rules like 54 and 110, and I can see to some extent how parity is being leveraged to generate complexity. (Even vs. odd length triangles are treated ever so slightly differently.)
But yeah, I digress. Back to the proof: the point is, we've shown that no valid period can ever be started, provided my code and logic are sound.
Note the crucial point that presumably, every possible bitstring can be constructed on any row or column, so there is almost certainly some (arbitrarily long) generative row which can maintain a periodic column which is also arbitrarily long. However, it turns out that many configurations for \(k\) cells typically require something more like \(2.25k\) width of horizontal cells to work with, not the bare minimum \(2k+1\) cells we allow.
And yet, we don't need to allow that, and it seems like we can force the issue by taking advantage of that. There must be a row where the period starts, and it must only be affected by the cells within that radius of \(\pm k\), and it must obviously be consistent from one moment to the next, and that's what lets us rule almost everything out.
In essence, the argument boils down to:
- Starting at some row, the center must be periodic, and that must correspond to some explicit generative row.
- Assuming that constraint, we can pare down the state space to all but a few legal situations by early winnowing of any configuration that doesn't immediately follow from its predecessor.
- The few configurations that survive fall into three categories, all of which are inadmissible as possible solutions.
- No other solution can arise at a later time; the handful of survivors are stagnant, and nothing new can show up since we require a complete record for each timestep since the period started, and we've eliminated all those possible stepping stones. The moment we identify a single slice of time where no potentially periodic configuration is presently admissible, the proof is complete (which I think happens back at \(t=4\) or \(5\), once I clean things up.)