ABSTRACT (original article): In the companion paper, we showed that rule 110’s ANF decomposes as an OR–XOR switch controlled by the left cell, with the cubic monomial
abc
acting as a conditional eraser that cancels the quadratic term
bc
when
a=1
. Here we scan all 256 elementary cellular automata to determine which rules share this algebraic mechanism. The result are striking: exactly two rules possess the OR↔XOR switch — Rule 110 and its polarity-reversed dual Rule 230. The four known Class 4 rules (110, 124, 137, 193) form a single equivalence class under complement and mirror, and all four carry the cubic term
abc
and are self-referential in Nersissian’s framework. We identify the precise algebraic fingerprint that separates Class 4 from the remaining 252 rules and show that, when assembled as a six-step progressive filter, it has Rule 110 as its unique surviving fixed point. Extending the construction to neighborhood size
M=4
(
16
2
=65,536rules)
, the same filtration generalizes verbatim and selects a single survivor — Rule 38654, whose ANF carries the exact 4-variable analog of the OR–XOR switch and the same asymmetric quadratic sector that distinguishes Rule 110 from its symmetric cousin Rule 104. We conjecture that Rule 38654 is a Turing-complete 4-neighborhood automaton. All results are exact and derived in
O(1)
per rule from ANF coefficients — no simulation, no heuristic. CITATION (original article): E. Chan-López, A. Martín-Ruiz (2026), Symmetric Nonlinear Cellular Automata as Algebraic References for Rule~30, arXiv:2604.00165. https://doi.org/10.48550/arXiv.2604.00165
Sequel to: "Rule 110: conditional dynamics, the OR-XOR switch, and the structure of irreducibility" (Staff Pick, 2026). Building on the Universal Framework of Nersissian (Part III) [7]. By E. Chan-López, Tigran Nersissian and A. Martín-Ruiz.

1. Motivation: From One Rule to All Rules

In Part I, we established that Rule 110’s update function admits an exact conditional decomposition: OR when
a0
, XOR when
a1
. The cubic monomial
abc
in the ANF acts as a conditional eraser, it cancels the quadratic
bc
when the left cell is active, switching the dynamics from inclusive propagation (OR) to parity cancellation (XOR).​
​​
​The natural question is: is Rule 110 unique? Or do other elementary rules share this mechanism? Nersissian’s Universal Framework (Part III) [7] provides the algebraic infrastructure to answer this question systematically: the ANF, self-variable, source extraction, and self-referential classification are all computable for any rule. We apply this machinery to all 256 ECA rules and extract the algebraic signature of Turing completeness.

2. The Algebraic Scan Engine

For each of the 256 rules, we compute exactly (from the truth table, with no approximations):
◼
  • ANF via Möbius inversion over
    GF(2)
    .
    • ◼
  • Conditional decomposition: which of the 16 Boolean functions of
    (b,c)
    does
    g
    reduce to when
    a0
    vs
    a1
    ?
    • ◼
  • Self-variable: the minimum-index variable present in the ANF (Nersissian’s definition [7]).
    • ◼
  • Self-referential status: does the source
    hg⊕
    x
    self
    still contain
    x
    self
    ?
    • ◼
  • Permutivity: left, right, center, or none.
    • ◼
  • Symmetry degree: how many of the 6 permutations of
    (a,b,c)
    leave the ANF invariant.
    • ◼
  • Equivalence class: complement, mirror, complement-mirror.
    • M=3 engine loaded. All functions ready.

    3. Result 1: Exactly Two Rules Have the OR↔XOR Switch

    Scanning all 256 rules for the specific OR↔XOR conditional decomposition (in either direction):
    Theorem 3.1 (Uniqueness of the OX-XOR switch). Among all 256 elementary cellular automata, exactly two \​
    ​rules admit the OR↔XOR conditional decomposition:​
    ​​
    ​
    Rule 110:gb⊕c⊕bc⊕abc(a0OR, a1XOR)
    ​
    ​ ​
    ​
    Rule 230:gb⊕c⊕abc(a0XOR, a1OR)
    ​
    ​ ​
    ​Rule 230 is the exact algebraic dual of Rule 110: same switch, reversed polarity. Its ANF is Rule 110’s ANF without the quadratic term
    bc
    .
    Remark (The
    bc
    term as the differentiator). Rules 110 and 230 differ by exactly one monomial:
    bc
    . In Rule 110, the
    bc
    term creates the OR operation when
    a0
    (since
    b⊕c⊕bcb⋁c
    ); when
    a1
    , te
    abc
    term cancels, leaving XOR. In Rule 230, there is no
    bc
    to cancel. The XOR persists when
    a0
    , and the
    abc
    term adds the quadratic correction to produce OR when
    a1
    . The eraser operates in reverse.
    (*Scanall256rulesforOR↔XOR*)​​orXorRules=SelectRange[0,255],​​ Function​​ Module{d=conditionalDecomp@#},​​ OrAnd[Equal[d@"a=0","OR"],Equal[d@"a=1","XOR"]],​​ And[Equal[d@"a=0","XOR"],Equal[d@"a=1","OR"]]​​ ​​ ​​ ​​;​​​​Print["Rules with OR↔XOR: ",orXorRules]​​Print["Rule 110 ANF: ",anfString[110]]​​Print["Rule 230 ANF: ",anfString[230]]
    Rules with OR↔XOR: {110,230}
    Rule 110 ANF: b ⊕ c ⊕ bc ⊕ abc
    Rule 230 ANF: b ⊕ c ⊕ abc

    4. Result 2: The Four Class 4 Rules Form One Equivalence Class

    Under the standard equivalence relations (complement, left-right mirror, and their composition), Rule 110 generates a class of exactly four rules:
    Out[]=
    Rule
    Switch a=0 → a=1
    ANF
    Lin. a
    Perm.
    Sym.
    110
    OR → XOR
    b⊕c⊕bc⊕abc
    No
    None
    2
    124
    b → NAND
    a⊕b⊕ab⊕abc
    Yes
    None
    2
    137
    XNOR → AND
    1⊕a⊕b⊕c⊕ab⊕ac⊕abc
    Yes
    None
    2
    193
    NOR → b
    1⊕a⊕b⊕c⊕ac⊕bc⊕abc
    Yes
    None
    2
    Table 1: The Rule 110 equivalence class . All known Class 4 ECA.
    Proposition 4.1 (Shared algebraic properties). All four rules in the equivalence class share: (i) the cubic monomial
    abc
    is present; (ii) they are self-referential in Nersissian’s sense; (iii) they are completely non-permutive; (iv) symmetry degree exactly 2 (out of 6).
    Remark (Only Rule 110 lacks linear
    a
    ). Among the four equivalent rules, Rule 110 is the only one where the variable
    a
    does not appear linearly in the ANF. This is the property \​
    ​responsible for the one-sided light cone (provided by induction y Part I). The other three rules have bilateral light cones. The absence of linear
    a
    is not preserved under complement or mirror, it is a property specific to Rule 110 within its equivalence class.
    (*Computeequivalenceclass*)​​equivalenceClass[110]​​(*VerifyallfourareClass4andcarryabc*)​​Table[{r,anfCoeff[r,{1,2,3}],isSelfReferential[r],Row[List@#,","]&@Values[conditionalDecomp[r]]},{r,equivalenceClass[110]}]//TableForm
    Out[]=
    {110,124,137,193}
    Out[]//TableForm=
    110
    1
    True
    {OR,XOR}
    124
    1
    True
    {b,NAND}
    137
    1
    True
    {XNOR,AND}
    193
    1
    True
    {NOR,b}

    5. Result 3: The abc Eraser Mechanism

    The cubic monomial
    abc
    appears in the ANF of 128 rules (exactly half). Among those, 64 rules also contain the quadratic term
    bc
    , meaning
    abc
    can potentially act as a conditional eraser of
    bc
    (as it does in Rule 110). These 64 rules for exactly one quarter of the entire ECA rule space.
    Definition 5.1 (The abc eraser). A rule has the
    abc
    eraser if both
    α
    bc
    1
    and
    α
    abc
    1
    in its ANF. When
    a1
    , the term
    abcbc
    exactly cancels
    bc
    over
    GF(2)
    , removing the quadratic coupling between the center and right cells.
    Proposition 5.1 (abc eraser statistics). Among all 256 ECA rules:​
    ​​
    ​— 128 rules (50%) contain the
    abc
    monomial.​
    ​— Exactly 64 rules (25%, one quarter of rule space) have the abc eraser (
    abc
    and
    bc
    both present).​
    ​— Of these 64, exactly one produces the OR→XOR switch: Rule 110.​
    ​— The remaining 63 produce other conditional switches (AND↔XOR, OR↔AND, etc.).​
    ​— Rule 230, the polarity-reversed dual of Rule 110, also produces an OR↔XOR switch (in the reversed direction XOR→OR), but it does so without the abc eraser: its ANF is
    b⊕c⊕abc
    , with no
    bc
    term. Rule 230 thus belongs to a structurally distinct branch of the analysis (Section 6).
    Definition 5.2 (The abc eraser). A Boolean operation
    f(b,c)
    on two variables is:​
    ​​
    ​Filling (monotone increasing) if
    f(b,c)≥f(
    ′
    b
    ,
    ′
    c
    )
    whenever
    b≥
    ′
    b
    and
    c≥
    ′
    c
    . Equivalently, setting any input from
    0
    to
    1
    can never decrease the output. The maximal filling operation is OR:
    f1
    unless both inputs are
    0
    .​
    ​​
    ​Cancelling (linear over
    GF(2)
    ) if
    f(b,c)αb⊕βc⊕γ
    for constants
    α,β,γ∈{0,1}
    . The output depends on parity, not magnitude. The canonical cancelling operation is XOR:
    f(b,c)b⊕c
    .​
    ​​
    ​A filling/cancelling switch is a conditional decomposition where the
    a0
    regime is filling and the
    a1
    regime is cancelling (or vice versa).
    Remark (What makes OR↔XOR special). The OR→XOR switch is unique because it juxtaposes the two algebraically simplest operations with complementary dynamical characters: OR is the maximally filling operation (
    b⋁c1
    unless both inputs are
    0
    ), while XOR is the maximally cancelling operation (parity, Sierpiński dynamics). Other switches — AND→NAND, XNOR→OR, etc. — do not produce this clean filling/cancellation dichotomy. This is why Rule 110 generates Class 4 behavior while the other 63 abc-eraser rules do not.

    6. Result 4: The Dual — Rule 230

    Rule 230 is the only other rule with the OR↔XOR switch, but with reversed polarity: XOR when
    a0
    , OR when
    a1
    .
    Out[]=
    Rule 110
    Rule 230
    ANF
    b⊕c⊕bc⊕abc
    b⊕c⊕abc
    When a = 0
    OR (filling)
    XOR (cancelling)
    When a = 1
    XOR (cancelling)
    OR (filling)
    Difference
    The bc monomial: present in 110, absent in 230
    ​
    Self-ref.
    Yes
    Yes
    Non-permutive
    Yes
    Yes
    Wolfram Class
    4
    2 (periodic)
    Table 2: Rule 110 vs its dual Rule 230.
    Remark (Why Rule 230 is not Class 4). Despite having the same OR↔XOR switch, Rule 230 produces only Class 2 (periodic) behavior. The difference is the default regime: in Rule 110, the quiescent background has
    a0
    (all cells dead), which triggers OR, the filling operation that expands activity. In Rule 230, the quiescent background triggers XOR, the cancelling operation that suppresses activity. The OR-first dynamics of Rule 110 generates enough structure for XOR to act upon; the XOR-first dynamics of Rule 230 cancels structure before it can form. The order of the switch matters.

    7. The Algebraic Fingerprint of Class 4

    We apply a progressive algebraic filter to all 256 rules. Each condition is exact and computable from the ANF alone:
    Out[]=
    Filter
    Condition
    Surviving
    (0)
    Nontrivial rule
    254
    (i)
    +
    α
    abc
    = 1 (cubic coupling present)
    128
    (ii)
    + self-referential
    128
    (iii)
    + completely non-permutive
    128
    (iv)
    + monotone → parity switch (filling → cancelling)
    16
    (v)
    + cancelling regime uses both variables (XOR, not b or ZERO)
    2
    (vi)
    + asymmetric quadratic sector (bc but not ab or ac)
    1
    Table 3: Progressive filtering — from 256 rules to 1.
    Remark (The final discriminator). At step (v), two rules survive: Rule 110 (OR→XOR) and Rule 104 (AND→XOR). Both switch between a monotone filling operation and pure parity cancellation. But Rule 104 has ANF
    ab⊕ac⊕bc⊕abc
    . All three quadratic terms are present, giving it full
    S
    3
    symmetry (degree 6). It is Class 2. Rule 110 has only
    bc
    (not
    ab
    or
    ac
    ) breaking the symmetry and producing the asymmetric conditional dynamics that generates Class 4. The
    bc
    monomial without
    ab
    or
    ac
    is the final algebraic sieve.
    Conjecture 7.1 (Algebraic fingerprint of Turing completeness). Among the 256 elementary cellular automata, a rule belongs to Class 4 (up to equivalence) if and only if its ANF satisfies all of the following:​
    ​​
    ​(i) The cubic monomial
    abc
    is present.​
    ​​
    ​(ii) The rule is self-referential (the source feeds back into the current layer).​
    ​​
    ​(iii) The rule is completely non-permutive.​
    ​​
    ​(iv) The conditional decomposition juxtaposes a monotone operation (
    a0
    ) with a parity operation (
    a1
    ) that depends on both variables.​
    ​​
    ​(v) The quadratic sector is asymmetric:
    α
    bc
    1
    but
    α
    ab
    
    α
    ac
    0
    .​
    ​​
    ​This filter selects exactly one rule: Rule 110. Its equivalence class
    {110,124,137,193}
    constitutes the complete set of Class 4 ECA.​
    ​​
    ​All filters are computable in
    O(1)
    per rule from the eight ANF coefficients
    α
    S
    . No simulation, no heuristic, no numerical approximation. Rule 110 is not just universal — it is the unique fixed point of an algebraic filtration on the space of elementary cellular automata.
    Remark (Filter collapse: filters (i), (ii), (iii) are not independent). Inspecting Table 3 reveals that filters (i), (ii) and (iii) all leave exactly 128 surviving rules. This is not a numerical coincidence, it is a structural fact that we have verified by direct enumeration: every nontrivial ECA rule whose ANF contains the cubic monomial
    abc
    is automatically self-referential and completely non-permutive. The same pattern persists at
    M4
    , where filters (i), (ii) and (iii) all leave exactly
    32,768
    15
    2
    surviving rules (see Table 4). The presence of the highest-order monomial implicitly forces the other two algebraic conditions, so the genuinely discriminating filters are (i), (iv), (v) and (vi). Conditions (ii) and (iii) are retained in the table for interpretive clarity, since each names an independently meaningful structural property even though they happen to be implied by (i). We conjecture that this implication
    α
    x
    1
    ⋯
    x
    M
    1⇒self-ref⋀non-perm
    holds for all
    M
    , and that it is the algebraic reason the filtration scales uniformly with neighborhood size.
    Remark (Self-referentiality and computational irreducibility). Condition (ii) has a direct connection to Wolfram’s principle of computational irreducibility [3]. In Nersissian’s framework [7], non-self-referential rules admit closed-form symbolic polynomial generation. Their generating polynomials can be computed without simulating the automaton step by step. Self-referential rules, by contrast, require iterative point-by-point evaluation: the output of each step feeds back as input to the next, and no algebraic shortcut exists. This is precisely the computational structure that Wolfram identifies as irreducibility: the only way to determine the outcome is to run the computation. The self-referential property of Rule 110 is not an incidental feature, it is the algebraic manifestation of the irreducibility that makes Turing completeness possible. A rule that admits closed-form polynomial generation can be “shortcut”; a Turing-complete rule cannot.

    8. Connection with Nersissian's Universal Framework

    Nersissian’s Part III [7] introduces two concepts that illuminate the results above:
    The self-referential dichotomy. Rules where the source depends on the self-variable (like Rule 110) require iterative point-by-point computation — they cannot be solved in closed form as symbolic polynomials. This computational obstruction is, we conjecture, the algebraic correlate of computational irreducibility: the rule cannot be “shortcut” because its own output feeds back into its input at each step.

    9. Beyond M=3: The Algebraic Filtration at M=4

    10. Visual Confirmation: Dynamics of Rule 38654

    Experiment 1: Single seed on zero background

    Experiment 2: Random initial condition

    A 400-cell row of random 0s and 1s, evolved for 300 steps. Within roughly the first 50 steps a periodic background — an “ether” — emerges and stabilizes, visible as the regular vertical striped pattern in the left portion of the figure. Crossing this ether are propagating localized structures with several distinct slopes; these are the candidate gliders. Several apparent collisions between gliders are visible in the central region, where two diagonal tracks meet and either annihilate, fuse, or scatter into new structures. This is exactly the qualitative phenomenology that distinguishes Class 4 cellular automata from Class 2 and Class 3.

    Experiment 3: Comparison with Rule 110

    The most direct test of the algebraic homology between Rule 110 and Rule 38654 is to run both rules from random initial conditions of comparable size and compare the resulting space–time diagrams side by side.

    Quantitative signature: density evolution

    The density stabilizes within 50 steps and remains in a narrow band thereafter. This is the canonical density signature of a Class 4 automaton: stable but intermediate, neither full nor sparse, neither monotone nor chaotic.
    Remark (What this confirms and what remains open). These experiments confirm three things about Rule 38654, beyond what the algebraic filtration alone could establish: (i) the dynamics is non-trivial and does not collapse to Class 1, 2, or 3; (ii) a periodic background emerges spontaneously and supports propagating localized structures with multiple velocities; (iii) the qualitative phenomenology is structurally isomorphic to Rule 110. They do not establish Turing universality — that would require a catalog of glider species, a table of collision rules, and an explicit construction of logical gates and signal routing, in the spirit of Cook’s proof for Rule 110. We treat universality as an open problem (Conjecture 10.1 below) and present these experiments as the preliminary visual evidence the conjecture requires to be considered seriously.

    11. Conclusions and Open Problems

    This paper establishes six results — five exact and algebraic, one preliminary and dynamical — about the rule space of elementary cellular automata and its 4-neighborhood extension:
    5
    .
    Filters (i), (ii) and (iii) collapse to the same surviving count at monomial implicitly forces self-referentiality and complete non-permutivity. We conjecture this implication holds for all M and is the algebraic reason the filtration scales uniformly with neighborhood size.
    Open problem 1 (Cook-style construction for Rule 38654). Section 10 shows that Rule 38654 exhibits the qualitative ingredients of universality: periodic ether, propagating localized structures with multiple velocities, and non-trivial collisions. The natural next step is to catalog these structures in the manner of Cook (2004): identify the elementary glider species and their fundamental periods, build the full collision table between every pair of glider types, and determine whether the resulting collision algebra contains a logically complete subset (NAND or equivalent) together with signal routing primitives. If yes, an analog of Cook’s universality proof goes through and Rule 38654 is provably Turing-complete. The dynamical evidence in Section 9.5 makes this program concrete and falsifiable rather than purely speculative.
    In the exploration of dynamical systems, truth is not imposed but filtered.​
    ​As constraints accumulate, the space of possibilities collapses—until only those rules remain whose behavior cannot be simplified, bypassed, or erased.​
    ​What remains is not chosen. It is what could not disappear.

    References

    [1] ] Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601–644.
    [2] Cook, M. (2004). Universality in Elementary Cellular Automata. Complex Systems, 15(1), 1–40.
    [3] Wolfram, S. (2002). A New Kind of Science. Wolfram Media.
    [4] Nersissian, T. (2026). Rule 30 Exact Binomial–Lucas Lifting (Part I). Wolfram Community Staff Picks.
    [5] Nersissian, T. (2026). Rule 30 Algebraic Pipeline II: Generating Polynomials, PDE Limits, and Symmetry Classification. Wolfram Community Staff Picks.
    [6] Chan-López, E. (2026). Rule 110: Conditional Dynamics, the OR–XOR Switch, and the structure of irreducibility. Wolfram Community Staff Picks.
    [7]Nersissian, T. (2026). Rule 30 Algebraic Pipeline III: The Universal Framework — From Elementary to General Cellular Automata via ANF Source Extraction. Wolfram Community Staff Picks.
    [8] Chan-López, E. & Martín-Ruiz, A. (2026). Symmetric Nonlinear Cellular Automata as Algebraic References for Rule 30. Complex Systems, submitted: https://arxiv.org/abs/2604.00165
    [9] Lind, D. & Marcus, B. (2021). An Introduction to Symbolic Dynamics and Coding (2nd ed.). Cambridge University Press.
    [10] Crama, Y. & Hammer, P. L. (2011). Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press.

    CITE THIS NOTEBOOK

    The abc eraser: algebraic filtration and the emergence of universality​
    by Ramón Eduardo Chan López​
    Wolfram Community, STAFF PICKS, April 19, 2026
    https://community.wolfram.com/groups/-/m/t/3695987