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} + xm + x{m-1}xm + (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} + xm + x{m-1}xm + (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}
]