Rule 110: Conditional Dynamics

Building on the DPDE framework of yarchik and Nersissian (2026) [7, 8] and the symmetry classification of E. Chan-López [9].

ABSTRACT (original article): This paper establishes that Wolfram’s Rule 110 elementary cellular automaton possesses a fundamental conditional algebraic structure: its Algebraic Normal Form (ANF) decomposes as an OR–XOR switch controlled by the left cell. When the left neighbor is

, the update is

OR(b,c)

; when is

the update becomes

XOR(b,c)

. This decomposition is exact and verified computationally over all configurations. We analyze the symmetry and permutivity properties, derive a forward difference factorization, and take the continuous limit to obtain the quasilinear first-order PDE

∂u/∂m=

+u-

, with constant transport speed

v=1

, in stark contrast to Rule 30’s state-dependent wave speed

v=3(u+1)

. This constant velocity provides a structural explanation for the persistence of localized structures (gliders) in Rule 110 and its Class 4 behavior. We show that the one-sided light cone, sub-exponential block complexity, and regime-switching dynamics all follow from the conditional decomposition. The resulting classification places Class 2 (parabolic, full symmetry), Class 3 (hyperbolic, uniform breaking), and Class 4 (hyperbolic, conditional breaking) on a unified algebraic spectrum governed by the structure of symmetry breaking in the ANF.
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

1. Introduction and Motivation

Rule 110 occupies a singular position within elementary cellular automata (ECA): it is the simplest system proven to be Turing complete [3], yet its algebraic structure has received far less attention than that of Rule 30 or Rule 22. The recent work of Nersissian [6] established a powerful pipeline from Boolean logic to integer coefficients, Stirling transfer, and support-set algebra for Rule 30, culminating in a Discrete Partial Difference Equation (DPDE) formulation whose continuous limit reveals a quasilinear hyperbolic PDE. In Part II of that work, a symmetry classification was developed: fully symmetric rules (Rule 22) produce parabolic (reaction–diffusion) limits, while asymmetric rules (Rules 30 and 135) produce hyperbolic (transport) limits.

The present paper extends this framework to Rule 110 and discovers a qualitatively new symmetry-breaking mechanism: conditional symmetry breaking. Unlike Rule 30, where the asymmetry is uniform across all configurations, Rule 110’s ANF switches between two fundamentally different Boolean operations depending on the state of the left neighbor. This OR–XOR decomposition provides a precise algebraic explanation for the emergent Class 4 behavior — gliders, localized structures, and the coexistence of order and chaos — that has resisted analytic description since Wolfram’s original classification [1].

We compare three rules spanning the Wolfram complexity hierarchy:

Out[]=

Rule	ANF g(a,b,c)	Symmetry	Wolfram Class
22	a⊕b⊕c⊕abc	Full S 3	2
30	a⊕b⊕c⊕bc	None	3
110	b⊕c⊕bc⊕abc	None (conditional)	4

Table 1: ANF comparison across Wolfram classes.

2. The Algebraic Normal Form

Rule 110 has Wolfram code

110

(01101110)

. Its Algebraic Normal Form over

GF(2)

is:

110

(a,b,c)b⊕c⊕bc⊕abc.

Compare the ANFs of our three reference rules:

◼

Rule 30:

a⊕b⊕c⊕bc

— asymmetric:

and

are coupled but

is not.

◼

Rule 22:

a⊕b⊕c⊕abc

— fully symmetric under all permutations of

(a,b,c)

◼

Rule 110:

b⊕c⊕bc⊕abc

— no linear term in

;

appears only in the cubic term.

The critical structural feature is the absence of the linear term

. In Rule 30’s ANF, every variable appears linearly, ensuring left-permutivity. In Rule 110, the left neighbor

enters only through the triple product

abc

, acting as a gate rather than a direct contributor.

2.1 Derivation by Möbius Inversion

We derive the ANF systematically via Möbius inversion over

GF(2)

: the coefficient of the monomial

∏

i∈S



⊕

T⊆S

g(T)

The integer coefficients

m,r

from Part I satisfy a complex trinomial convolution recurrence. The key insight of yarchik is that these coefficients are more naturally accessed through generating polynomials that encode the full binomial expansion of each row.

Definition 2.1 (ANF coefficients via Möbius inversion). For a boolean function

{0,1}

{0,1}

,the ANF coefficient

for monomial index set

S⊆{a,b,c}



⊕

T⊆S

)

, where

is the indicator vector of

Constante term:

∅

g(0,0,0)0

Linear terms:

{a}

g(0,0,0)⊕g(1,0,0)0⊕00,

{b}

g(0,0,0)⊕g(0,1,0)0⊕11,

{c}

g(0,0,0)⊕g(0,0,1)0⊕11.

Remark (The missing linear term). The coefficient

{a}

0

is crucial: the variable

(left cell) does not appear linearly in the ANF. In both Rule 30 and Rule 22,

{a}

1

. This absence is directly responsible for the one-sided light cone (§7) and the non-permutivity in

(§3).

Quadratic terms:

{a,b}

g(0,0,0)⊕g(1,0,0)⊕g(0,1,0)⊕g(1,1,0)0⊕0⊕1⊕10,

{a,c}

g(0,0,0)⊕g(1,0,0)⊕g(0,0,1)⊕g(1,0,1)0⊕0⊕1⊕10,

{b,c}

g(0,0,0)⊕g(0,1,0)⊕g(0,0,1)⊕g(0,1,1)0⊕1⊕1⊕11.

Cubic term:

{a,b,c}



⊕

T⊆{a,b,c}

)0⊕1⊕1⊕1⊕0⊕1⊕1⊕01.

Assembling:

110

(a,b,c)b⊕c⊕bc⊕abc

. 

(*Rule110truthtable*)rule110=IntegerDigits[110,2,8]//Reverse;(*ANFcoefficientbyexplicitMöbiusinversion*)anfCoeff[S_List]:=Module[{total=0},Do[Module[{vec={0,0,0}},Do[vec[[S[[j]]]]=T[[j]],{j,Length[S]}];total+=rule110[[4vec[[1]]+2vec[[2]]+vec[[3]]+1]]],{T,Tuples[{0,1},Length[S]]}];Mod[total,2]];(*Computeallcoefficients*)Print["

∅

= ",anfCoeff[{}]]Print["

= ",anfCoeff[{1}]]Print["

= ",anfCoeff[{2}]]Print["

= ",anfCoeff[{3}]]Print["

= ",anfCoeff[{1,2}]]Print["

= ",anfCoeff[{1,3}]]Print["

= ",anfCoeff[{2,3}]]Print["

abc

= ",anfCoeff[{1,2,3}]](*Cross-checkwithBooleanConvert*)BooleanConvert[BooleanFunction[110,{a,b,c}],]

∅

= 0

= 1

= 0

= 1

abc

= 1

Out[]=

b⊻c⊻(b&&c)⊻(a&&b&&c)

2.2 Computational Verification

The following Mathematica code verifies the ANF against the truth table:

(*Rule110truthtable*)rule110=IntegerDigits[110,2,8]//Reverse;(*ANF:g₁₁₀(a,b,c)=b⊕c⊕bc⊕abc*)g110[a_,b_,c_]:=BitXor[b,c,BitAnd[b,c],BitAnd[a,b,c]];(*Verificationoverall8inputs*)TableForm[Flatten[Table[{a,b,c,rule110[[4a+2b+c+1]],g110[a,b,c]},{a,0,1},{b,0,1},{c,0,1}],2],TableHeadings{None,{"a","b","c","Rule 110","b⊕c⊕bc⊕abc"}},TableAlignmentsCenter]

Out[]//TableForm=

a	b	c	Rule 110	b⊕c⊕bc⊕abc
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	1
1	1	1	0	0

3. Symmetry and Permutivity Analysis

Definition 3.1 (Permutivity). A Boolean function

g(a,b,c)

is left-permutive if for every fixed,

(b,c)

g(0,b,c)≠g(1,b,c)

. Analogously for right- and center-permutivity.

Proposition 3.1 (Rule 110 is non-permutive). Rule 110 is not permutive in any of its three variables.

Proof.
Left-permutivity requires

g(0,b,c)≠g(1,b,c)

for all

(b,c)

. Counterexample:

g(0,0,0)0g(1,0,0)

. Fails.
Right-permutivity requires

g(a,b,0)≠g(a,b,1)

for all

(a,b)

. Counterexample:

g(0,1,0)1g(0,1,1)

. Fails.
Center-permutivity requires

g(a,0,c)≠g(a,1,c)

for all

(a,c)

. Counterexample:

g(0,0,1)1g(0,1,1)

. Fails. 

(*Left-rightsymmetrytest*)lrSym=And@@Flatten[Table[g110[a,b,c]==g110[c,b,a],{a,0,1},{b,0,1},{c,0,1}]];Print["Left-right symmetric: ",lrSym](*FullS₃symmetrytest*)s3Sym=And@@Flatten[Table[Length[DeleteDuplicates[g110@@@Permutations[{a,b,c}]]]==1,{a,0,1},{b,0,1},{c,0,1}]];Print["Full S₃ symmetric: ",s3Sym](*Permutivitytests*)leftPerm=And@@Flatten[Table[g110[0,b,c]!=g110[1,b,c],{b,0,1},{c,0,1}]];rightPerm=And@@Flatten[Table[g110[a,b,0]!=g110[a,b,1],{a,0,1},{b,0,1}]];centerPerm=And@@Flatten[Table[g110[a,0,c]!=g110[a,1,c],{a,0,1},{c,0,1}]];Print["Left-permutive: ",leftPerm]Print["Right-permutive: ",rightPerm]Print["Center-permutive: ",centerPerm]

Left-right symmetric: False

Full S₃ symmetric: False

Left-permutive: False

Remark (Permutivity Comparison). Rule 30 is left-permutive (which guarantees the XOR Lemma and entropy injection into the center column). Rule 22 is permutive in all three variables. Rule 110 is permutive in none. Information is never injected unconditionally. This non-permutivity is the algebraic root of Rule 110’s ability to sustain localized structures: perturbations do not propagate universally but only when gated by the state.

4. The Conditional OR–XOR Decomposition

This section contains the central result. We show that the ANF of Rule 110 admits a clean decomposition into two familiar Boolean operations, selected by a single bit.

4.1 The decomposition

4.2 Dynamic Interpretation

The two regimes have fundamentally different dynamical characters:

Remark (Gliders as OR-XOR interfaces). A glider is a persistent interface between an OR-dominated region and an XOR-dominated region. The OR regime attempts to expand; the XOR regime attempts to cancel. The dynamic equilibrium between these two opposing tendencies produces a localized structure that propagates at fixed velocity. The computation of Turing (proven by Cook [11]) occurs precisely at these boundaries — it is the conflict between OR and XOR that carries information.

4.3 Computational Verification

4. 4 Large-Scale Verification

5. The OR/XOR Regime Map and Glider Anatomy

5.1 Panel I: Side-by-Side Evolution and Regime Map

5.3 Panel III: Interface Extraction — Gliders as OR–XOR Boundaries

The most striking visualization isolates only the cells where OR and XOR regimes are spatially adjacent. An interface cell is an active cell whose immediate spatial neighbor belongs to the opposite regime:

Remark (The glider skeleton). The interface extraction is the visual proof of our thesis: when we strip away all cells that are purely OR or purely XOR and retain only the boundaries between regimes, the glider trajectories survive. The diagonal lines in the right panel are the gliders — they exist precisely where OR meets XOR. This is not a post-hoc correlation; it is a structural identity: a glider is an OR–XOR interface.

5.4 Panel IV: Quantitative Regime Analysis

Proof. Verified over 200 generations from single-cell initial condition. Of 1197 XOR-produced cells, 1197 (100%) are adjacent to at least one OR-produced cell. The OR regime, by contrast, can form bulk regions: only 91.7% of OR cells are at interfaces. 

6. Forward Difference Factorization

7. One-Sided Light Cone

8. Column Analysis and Block Complexity

9. The Continuous PDE Limit for Rule 110

9.1 Derivation via Taylor Expansion

9.2 Comparative Table of PDE Limits

10. Support Cardinality and Growth

11. The Algebraic Classification of Wolfram’s Classes

The conditional decomposition of Rule 110, combined with the framework of [6], suggests a unified algebraic classification of Wolfram’s complexity classes based on the structure of symmetry breaking in the ANF.

Conjecture 11.1 (Algebraic classification of Wolfram classes). For elementary cellular automata whose nonlinearity derives from a k-ary product term in the ANF:

(i) Class 2 (periodic/nested): The ANF is fully symmetric under permutations. The continuous limit is parabolic (reaction–diffusion). The symmetric vacuum. Example: Rule 22.

(ii) Class 3 (chaotic): The ANF breaks permutation symmetry uniformly. The continuous limit is hyperbolic with state-dependent wave speed. Global symmetry breaking drives chaotic mixing. Example: Rule 30.

(iii) Class 4 (complex/Turing-complete): The ANF breaks permutation symmetry conditionally, a state variable switches between distinct Boolean operations. The continuous limit is hyperbolic with constant wave speed. Selective breaking enables regime coexistence. Example: Rule 110.

11.1 Summary Classification Table

11.2 Connection with Theoretical Physics

The algebraic classification admits a striking parallel with the structure of symmetry breaking in quantum field theory and statistical mechanics:

12. Discussion and Open Problems

This paper has established three principal results:

3. The algebraic classification. By combining Rules 22, 30, and 110, we identify a spectrum: full symmetry → parabolic (Class 2), uniform breaking → hyperbolic with variable speed (Class 3), conditional breaking → hyperbolic with constant speed (Class 4).

Several problems remain open:

Open problem 1 (Glider characterization). Can the OR–XOR regime boundary be used to derive the complete catalogue of Rule 110 gliders? The regime map suggests that gliders correspond to stable OR/XOR interfaces, but a formal classification from the decomposition is missing.

Open problem 2 (Turing completeness from the PDE). Does the constant transport speed v=1 play a necessary role in enabling Turing completeness? Is there a threshold on the variability of v(u) below which computation is possible?

Open problem 3 (Extension to all 256 ECA). Extend the conditional decomposition analysis to all 256 elementary rules. Which rules admit OR–XOR (or AND–NAND, etc.) \
switches? Is conditional decomposition a reliable marker for Class 4 behavior?

Open problem 3 (Formal symmetry classification). Extend the parabolic/hyperbolic classification of [6] to all 256 ECA. Is the classification stable under rule equivalence classes (complement, mirror, complement-mirror)?

13. The Topology of Universality: Causal Anatomy and the Structural Skeleton of Rule 110

The following multi-panel structure stands as the ultimate synthesis of our computational dissection. It illustrates the complete logical chain from macroscopic phenomenon to fundamental architecture: strict spatial evolution → regime mapping → discrete switch dynamics → persistent topological skeleton:

To understand the emergence of complexity in Rule 110, it is useful to move beyond its macroscopic appearance and examine the underlying causal structure. The following visual decomposition provides a layered view of the dynamics across four complementary representations. Panel A shows the evolution of the light cone from a single seed. Panel B separates the dynamics into two local regimes, corresponding to OR-type propagation and XOR-type interaction. Panel C recasts this distinction as a binary switching structure, making explicit the local algebraic mechanism. Panel D isolates the interfaces between these regimes, highlighting the boundaries associated with persistent structures such as gliders.

Taken together, these views show how complex behavior arises from simple local rules through the interaction of propagation, interference, and boundary formation.

References

[1] Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601–644.

[2] Wolfram, S. (1986). Random sequence generation by cellular automata. Advances in Applied Mathematics, 7(2), 123–169.

[3] Wolfram, S. (2002). A New Kind of Science. Wolfram Media.

[4] Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley.

[5] Lucas, É. (1878). Théorie des Fonctions Numériques Simplement Périodiques. American Journal of Mathematics, 1(2), 184–196.

[6] Nersissian, T. (2026). Rule 30 Exact Binomial–Lucas Lifting: From Boolean Logic to Integer Coefficients, Stirling Transfer, and Support-Set Algebra. Wolfram Community Staff Picks.

[7] Nersissian, T. (2026) Rule 30 exact binomial–Lucas lifting (part II): generating polynomials, continuous PDE limits, and symmetry classification of elementary cellular automata. Wolfram Community Staff Picks.

[10] Martin, O., Odlyzko, A. M., & Wolfram, S. (1984). Algebraic properties of cellular automata. Communications in Mathematical Physics, 93(2), 219–258.

[11] Rowland, E. S. (2006). Local nested structure in rule 30. Complex Systems, 16(3), 239–258.

[12] Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology — EUROCRYPT '93, Lecture Notes in Computer Science, vol. 765, pp. 386–397.

[13] Cook, M. (2004). Universality in Elementary Cellular Automata. Complex Systems, 15(1), 1–40.

[14] Chan-López, E. & Martín-Ruiz, A. (2026). Symmetric Nonlinear Cellular Automata as Algebraic References for Rule 30. Complex Systems, submitted.

[15] Lind, D. & Marcus, B. (2021). An Introduction to Symbolic Dynamics and Coding (2nd ed.). Cambridge University Press.

[16] Smoller, J. (1994). Shock Waves and Reaction–Diffusion Equations (2nd ed.). Springer.

[17] Murray, J. D. (2002). Mathematical Biology I (3rd ed.). Springer.

[18] Crama, Y. & Hammer, P. L. (2011). Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press.

CITE THIS NOTEBOOK

Rule 110: conditional dynamics, the OR–XOR switch, and the structure of irreducibility
by Ramón Eduardo Chan López
Wolfram Community, STAFF PICKS, April 3, 2026
https://community.wolfram.com/groups/-/m/t/3673620