(This is hopefully a clearer version of an earlier post of mine.)
I have been spending lots of time on the open challenge of proving the aperiodicity of the central column of a rule 30 cellular automaton. Instead of belaboring background information here, see Wolfram's recent great overview.
There is one avenue of attack I keep circling back to, but repeatedly I can't make up my mind whether there is anything to pursue there. I am hoping somebody can clarify the situation for me.
In brief, my idea is that:
- We know ECAs take their input from their left, current, and right cells in their most recent state.
- This establishes $c$, in CA parlance, as one cell per time step: cause and effect cannot propagate any faster than that.
- We assert a transient periodic central column given the standard seed row of a single $1$ cell against a tile of $0$s; that is, the column becomes periodic, but only after reaching some (large) row $N$. ("Row" is largely interchangeable with "step" or "time".)
Once this column becomes periodic, I would argue the column can no longer carry information. Assuming the cycle's sequence and parameters are known, and thus readily predictable in advance (e.g. via a simple arithmetic progression), then both sides of the CA have gathered all the useful information they ever can from that column. Since by definition, nothing can perturb its pattern anymore, a signal cannot pass through it; it should be information-opaque. See the earlier point about $c$ being a single horizontal cell per time unit.
One tricky issue is that you can't make points that rely on altering some bit or input somewhere, since with virtually no exception, that would compromise the environment and make any conclusion moot. The larger tricky issue seems to be the question of correlation vs. causation.
Rule 30 is riddled with circumstantial computation. It is straightforward to find nodes which together comprise legitimate logical circuits of (probably) arbitrary complexity. So for example, I can certainly find, say, a 2-bit-by-2-bit binary multiplier, and show that its output is propagated right up to the center column, and potentially through it.
What's really confusing is that half of the time, the two cells on either side of a periodic column will be correlated or anticorrelated---think entangled particles. A priori, we don't know the identity of either, but once we know one, we know the other. What's problematic here is that the information seems to be hopping over what should be an impermeable barrier, and what's more, it's doing it instantaneously over an impossible distance (again, entangled particles).
I can think of several resolutions:
- this is a product of the leftward alternative arrow of time, where information can be spent horizontally if you realign your conception of cause and effect, or
- this is an artifact of something akin to superdeterminism, where any such correlation follows implicitly in a vastly complicated way based on the initial conditions and intrinsic ruleset, or
- it's impossible because periodic columns like that are impossible.
What I'm asking for here is some guidance about whether this whole approach seems promising or like a waste of energy. My best idea along these lines currently is to identify a serial computation complex enough it cannot have been computed before that point, or in parallel on both sides, and then trace the output bit as it jumps the center and affects computations on the other side. Would that be a clear enough violation?
Anyway, in general, do you think there could be some way to contrive a scenario in which an information-bearing signal is proven to have crossed the wall, and that that is indeed impossible, thus yielding a proof by contradiction?