Hi everyone,
My name is Tigran. I am working with the Wolfram Language on cellular automata and would like to ask whether a particular larger-neighborhood extension of Rule 110, defined in algebraic normal form (ANF) over GF(2), is already known, and how best to validate it rigorously.
⸻
Rule family (ANF over GF(2))
For each neighborhood size m >= 3, I define a Boolean local rule
f_m(x1, …, xm) =
x_{m-1} + x_m + x_{m-1}x_m + (x1x2*…*xm) (mod 2)
where:
• addition is XOR (mod 2),
• multiplication is AND.
For m = 3, this becomes
f_3(x1, x2, x3) =
x2 + x3 + x2x3 + x1x2*x3 (mod 2)
which corresponds exactly to Wolfram Rule 110.
Converting the ANF to a lookup table and then to a Wolfram rule index gives, for example:
m = 3 → 110
m = 4 → 28398
m = 6 → 7993589098607472366
⸻
Evolution setting
I evolve a one-sided (causal) wedge with boundary zeros and a single-seed initial condition:
a(0,0) = 1
a(0,t > 0) = 0
Out-of-range indices are treated as zero.
The update rule is:
a(n+1, t) =
f_m( a(n, t-m+1), …, a(n, t) )
This is a triangular / wedge evolution rather than a standard bi-infinite CA.
⸻
Observation
Empirically, for certain neighborhood sizes — most notably
m = 2^j + 2
the resulting spacetime diagrams show persistent activity and localized structures strongly reminiscent of Rule 110, including glider-like behavior. This does not appear to be a trivial left-right symmetry or a simple shift.
⸻
Questions
1. Prior art
Is this specific ANF extension
x_{m-1} + x_m + x_{m-1}x_m + (x1x2*…*xm)
already known or studied (in Wolfram’s work, the CA literature, or related discussions of Rule-110 generalizations)?
2. Validation / factorization
What are the standard techniques to show that a larger-neighborhood Boolean CA factors onto Rule 110, for example via:
• a sliding block code,
• coarse-graining or renormalization,
• substitution or rescaling,
• or a proof of a semiconjugacy to Rule 110?
Does the use of a wedge evolution change what would count as a valid factor or simulation?
3. Practical workflow
If the right goal is to exhibit an explicit map pi such that
pi( evolution under f_m )
= evolution under Rule 110 applied to pi(state),
what would be a reasonable computational strategy (for example, searching small block maps) to test this in Wolfram Language?
If useful, I can share a minimal notebook or GitHub repository
Thank you very much for your time and for any pointers or references.
Tigran
ClearAll[NumberCellularAutomatonFastC];
NumberCellularAutomatonFastC[nMin_Integer, nMax_Integer, kMin_Integer,
kMax_Integer, ruleIndex_Integer, M_Integer /; M > 0] :=
Module[{bits, tMin = nMin, tMax = nMax, nMaxIter = kMax, outAll,
slice, cf},
bits = Reverse@IntegerDigits[ruleIndex, 2, 2^M];
cf = Compile[{{b, _Integer, 1}, {tmax, _Integer}, {nmax, _Integer}, {m, _Integer}},
Module[{prev, curr, out, n, t, j, idx, pattern, val},
prev = ConstantArray[0, tmax + 1];
prev[[1]] = 1;
out = ConstantArray[0, {nmax + 1, tmax + 1}];
out[[1]] = prev;
For[n = 1, n <= nmax, n++,
curr = ConstantArray[0, tmax + 1];
For[t = 0, t <= Min[tmax, (m - 1) n], t++,
pattern = 0;
(* pattern built from prev[t-(m-1)]..prev[t] *)
For[j = 1, j <= m, j++,
idx = t - m + j;
val = If[idx >= 0, prev[[idx + 1]], 0];
pattern = 2 pattern + val;
];
curr[[t + 1]] = b[[pattern + 1]];
];
prev = curr;
out[[n + 1]] = prev;
];
out
],
CompilationTarget -> "C", RuntimeOptions -> "Speed"
];
outAll = cf[bits, tMax, nMaxIter, M];
slice = outAll[[kMin + 1 ;; kMax + 1, tMin + 1 ;; tMax + 1]];
Transpose[slice]
]
XX[n_] :=
Symbol["x" <> ToString[n]] + Symbol["x" <> ToString[n - 1]] +
Symbol["x" <> ToString[n - 1]]*Symbol["x" <> ToString[n]] +
Product[Symbol["x" <> ToString[j]], {j, 1, n}];
Table[
{anfToRule[XX[(2^j + 2)], (2^j + 2)],
XX[(2^j + 2)],
ArrayPlot[
NumberCellularAutomatonFastC[
0, 10*(2^j + 2)^2 + 100,
0, 10*(2^j + 2)^2 + 100,
anfToRule[XX[(2^j + 2)], (2^j + 2)], (2^j + 2)],
ColorRules -> {0 -> Black, 1 -> LightBlue}]
},
{j, 0, 3}
]