Fact-checked by Grok 2 weeks ago

Rule 90

Rule 90 is an elementary cellular automaton consisting of a one-dimensional array of cells, each in one of two states (typically 0 or 1), where the state of each cell in the next generation is determined by the exclusive OR (XOR) operation applied to the states of its two immediate neighbors in the current generation, ignoring its own state. This rule, numbered 90 in binary (01011010₂) following Stephen Wolfram's encoding scheme for the 256 possible elementary rules, was first systematically studied as part of the classification of such automata. Introduced by in his 1983 analysis of cellular automata as models for complex systems in , Rule 90 exemplifies how simple local rules can generate intricate global patterns. The rule is linear and additive over the finite field , meaning the evolution of multiple initial cells is the superposition (modulo 2 sum) of the evolutions from individual cells, which aligns it with algebraic structures like linear algebra modulo 2. One of only eight additive elementary cellular automata, Rule 90 is amphichiral (symmetric under and complementation) and has Rule 165 as its complement. A hallmark of Rule 90 is its production of the Sierpinski triangle (or sieve) when evolved from a single live (1) cell in an otherwise empty row; this fractal pattern, first mathematically described by in 1915, emerges due to the rule's XOR mechanism mirroring binomial coefficients modulo 2 from . Such patterns have historical precedents, appearing in 13th-century Italian mosaics and underscoring the rule's connection to self-similar structures in mathematics and art. The rule's behavior from arbitrary initial conditions can be decomposed into these single-cell evolutions, making it a valuable case study in and emergent phenomena.

Introduction

Definition and rule

Rule 90 is an , a type of consisting of an infinite (or periodic) array of cells, each holding a state of 0 or 1, that evolves synchronously in discrete time steps according to a fixed rule based on the states of three neighboring cells: the left neighbor, the cell itself, and the right neighbor. In this setup, the next state of each cell is determined solely by these three cells from the previous time step, with the rule encoded as a string of length 8 corresponding to all possible neighborhood configurations. The specific update rule for Rule 90, introduced by in 1983, states that the next state of a is the (XOR) of its two immediate neighbors from the previous generation, disregarding the cell's own state. Formally, if the previous row is denoted as \dots a, b, c, \dots, where b is the in question, then the next state under b is a \oplus c, the XOR operation. This rule is numbered 90 in Wolfram's decimal convention, derived from its binary representation 01011010₂, which specifies the output for each of the 8 possible input neighborhoods ordered from 111 (leftmost bit) to 000 (rightmost bit). The complete truth table for Rule 90 is as follows:
Neighborhood (left, center, right)Output
1110
1101
1010
1001
0111
0100
0011
0000
This table confirms the XOR behavior, as the output matches the parity of the left and right bits regardless of the center. Standard initial conditions for studying Rule 90 typically involve an infinite line with all cells set to 0 except a single live cell (state 1) at the center position (e.g., position 0). Under infinite boundary conditions, this setup generates successive rows that branch outward symmetrically. A visual representation of the first few generations from this (with 1s shown as filled cells and 0s as empty, centered for clarity) illustrates the basic mechanics: 
Generation 0:  ... 0 0 0 1 0 0 0 ...
Generation 1:  ... 0 0 1 0 1 0 0 ...
Generation 2:  ... 0 1 0 0 0 1 0 ...
Generation 3:  ... 1 0 1 0 1 0 1 ...
Generation 4:  ... 1 0 0 0 0 0 1 ...
This evolution shows the initial cell deactivating while activating its neighbors, leading to a spreading pattern. Overall, such configurations under Rule 90 produce nested patterns resembling the .

Historical development

Patterns resembling the evolution of Rule 90 predate the formal study of cellular automata, appearing in the binary structure of modulo 2, a construction rooted in 17th-century . formalized the triangle in his 1654 Traité du triangle arithmétique, while explored its properties, including harmonic variants that highlight binomial patterns; the modulo 2 reduction reveals self-similar structures akin to modern fractals. These patterns gained renewed attention in fractal studies, notably through the , mathematically described by in 1915 as an example of a nowhere-differentiable continuous . Although the appeared as a decorative in 13th-century Italian mosaics, its formal recognition preceded cellular automata by decades. Rule 90 was introduced as an by in 1983, within his systematic classification of the 256 possible one-dimensional rules based on nearest-neighbor interactions. The rule's designation arises from the encoding of its output pattern—01011010 in , equivalent to decimal 90—for the eight input triples ranging from 000 to 111. In his paper "Statistical Mechanics of Cellular Automata," Wolfram analyzed Rule 90's behavior, noting its additive (linear over GF(2)) structure that enables superposition of configurations, facilitating analytical tractability amid emergent complexity. This work established Rule 90 as a paradigmatic example of how minimal rules can produce intricate dynamics, influencing subsequent research in computational theory. Wolfram expanded on Rule 90 in (2002), underscoring its generation of patterns from simple initial conditions and its relevance to understanding natural complexity. The explicit link between Rule 90's evolutions and the was drawn in the 1980s through 's simulations, revealing the automaton as a discrete dynamical realization of the . In the , Rule 90 featured in computational experiments probing phase transitions and aperiodic behaviors in rule spaces, such as studies of fuzzy variants and global dynamics. In 2023, Henryk Fukś advanced the analytical treatment of Rule 90 in his book Solvable Cellular Automata: Methods and Applications, deriving explicit deterministic solutions for its via matrix methods and algebraic decompositions, confirming its status among solvable elementary rules. As of November 2025, this remains the most recent high-impact contribution, with ongoing interest in its linear properties but no major theoretical breakthroughs reported.

Mathematical properties

Additive structure and superposition

Rule 90 operates as a linear transformation within the of binary configurations over the , where each 's state is an element of {0,1} and operations are performed modulo 2. The update rule for a at position i at time t+1 is given by the (XOR) of its left and right neighbors at time t, formally s_i(t+1) = s_{i-1}(t) \oplus s_{i+1}(t), which corresponds to addition in . This linearity implies that the global evolution map F satisfies F(\mathbf{v}) = A \mathbf{v}, where A is the and \mathbf{v} is the configuration vector; for finite configurations, A is the with entries given by binomial coefficients modulo 2. A key consequence of this linearity is the additivity of the rule: the evolution of the XOR of two configurations equals the XOR of their individual evolutions. Formally, if A and B are initial configurations, then F^n(A \oplus B) = F^n(A) \oplus F^n(B) for any time step n \geq 0, where \oplus denotes componentwise XOR and F^n is the n-th iterate of the update function. This property holds because the update is a homogeneous linear function over GF(2), preserving the field structure under addition. The superposition principle follows directly from additivity, allowing any initial configuration to be decomposed into a (via XOR) of basis configurations, typically single live s at various positions. The evolution of the full configuration is then the XOR of the evolutions of these basis elements, facilitating analytical computation without simulating each step. For instance, the pattern from a single live spreads according to the rows of the Pascal triangle modulo 2, and superposing multiple such patterns yields the overall behavior. Rule 90 can be decomposed into two independent instances of running on interleaved sublattices: one on even positions (shifted appropriately) and one on odd positions, which explains the rule's disregard for the center cell in its neighborhood. itself is additive and linear over GF(2), with update s_i(t+1) = s_{i-1}(t) \oplus s_i(t) \oplus s_{i+1}(t), but the decomposition isolates the contributions without the self-term. This linear structure enables exact prediction of future states for any by matrix exponentiation or binomial coefficient evaluation modulo 2, in contrast to nonlinear rules where such closed-form solutions are generally unavailable. The predictability stems from the diagonalizability of the over GF(2) and the finite nature of configurations in periodic settings.

Evolution formula

The evolution of Rule 90 can be expressed in closed form due to its linearity over the field GF(2). For an initial configuration x, where x_k \in \{0,1\} represents the state at position k, the state at time step n and position j, denoted [F^n(x)]_j, is given by [F^n(x)]_j = \sum_{i=0}^n \binom{n}{i} x_{2i - n + j} \pmod{2}, with the understanding that x_k = 0 for positions outside the defined range. This formula arises from the additive structure of the rule, which allows the overall pattern to be a superposition of contributions from each initial live . Each such contribution corresponds to the nth row of modulo 2, shifted to align with the initial position; the generating function for a single cell at the origin is (x^{-1} + x)^n \pmod{2}, whose coefficients are the binomial terms \binom{n}{i} \pmod{2}. In the special case of a single live cell at position 0, the state at time n and position j is \binom{n}{\frac{n + j}{2}} \pmod{2} if n + j is even and \frac{n + j}{2} \in \{0, 1, \dots, n\}, and 0 otherwise. By Lucas' theorem, \binom{n}{k} \pmod{2} = 1 if and only if every binary digit of k is less than or equal to the corresponding digit of n (i.e., the binary representation of k is a of that of n). Computing the state via this formula requires O(n) operations per cell, compared to O(n^2) for direct over n steps, making it efficient for analyzing large-time behavior without iterative updates. For random initial conditions where each cell is independently 1 with probability p, the probability P_n(0) that a given is 0 at time n is P_n(0) = \frac{1}{2} + \frac{1}{2} (1 - 2p)^{G(n)}, where G(n) is Gould's sequence giving the number of odd binomial coefficients in the nth row of (equivalently, G(n) = 2^{w(n)} with w(n) the binary weight or popcount of n). This follows from the , as each 's value is the mod-2 sum of G(n) independent initial contributions.

Emergent patterns

Sierpiński triangle

When Rule 90 is initialized with a single live cell at the origin and all others dead, the evolution produces an upward-pointing pattern, where live cells appear at positions determined by the parity of . Specifically, in the nth row (starting from n=0), the cell at position k (from 0 to n) is live the \binom{n}{k} is odd, which corresponds to the bits set in the binary representation of k being a of those in n (via Lucas' theorem). This discrete structure emerges due to the rule's linear nature over GF(2), generating the exact modulo-2 reduction of . The pattern exhibits : the full triangle is composed of three smaller copies of itself—one at the top and two at the bottom-left and bottom-right—each scaled by a factor of 2 in linear dimensions. This recursive composition arises because the evolution from step 2m mirrors the pattern up to step m, combined with shifted replicas, reflecting the rule's modulo 2. The of this is \log_2 3 \approx 1.585, indicating a structure that is more than one-dimensional but does not fill the plane. The connection to modulo 2, where odd entries form the live cells, was recognized in the , predating cellular automata interpretations. In visualizations of the first generations, the pattern begins with a single live cell at step 0, expands to two live cells at step 1 (positions 0 and 1, but centered), and for example, at step 7 forms a sparse triangular with 2^3 = 8 live cells within a of positions, highlighting the fractal's branching. As generations increase indefinitely, the density of live cells approaches 0, since the number of live cells at step n is 2^{\omega(n)} (where \omega(n) is the number of 1-bits in the representation of n), growing slower than the total of 2^n cells. This sparse filling underscores the pattern's efficiency in computational representations. Fractally, the from Rule 90 can be analyzed as the attractor of an (IFS) consisting of three contractive maps, each scaling by 1/2 and translating toward the vertices of an . The discrete grid approximation aligns with this continuous model, preserving under the rule's modulo-2 arithmetic, which ensures that superpositions of patterns remain consistent without . This invariance facilitates exact computation of arbitrary rows using bitwise operations on binary indices.

Stunted trees and clearings

In finite grids or under , the evolution of Rule 90 produces patterns analogous to "stunted ," where halts prematurely due to the limited space and wrapping effects, contrasting with the unbounded expansion seen in configurations. These structures emerge because the additive nature of the rule causes signals from initial live cells to propagate and interfere, forming tree-like branches that terminate when they loop back or overlap destructively. J.C.P. Miller introduced this tree metaphor in 1970 to describe periodic forests generated by linear recurrence relations over , directly applicable to Rule 90's modulo-2 arithmetic, where each "" roots at an initial live cell and branches upward in a triangular representation of the space-time diagram. Triangular clearings appear as empty regions within these patterns, particularly in denser initial conditions, resulting from destructive interference where overlapping branches cancel each other out modulo 2, leaving vacant triangular areas. H. ApSimon extended Miller's work in by enumerating periodic forests classified by the size of their largest clearings, showing that such voids form systematically in bounded setups, with clearings of size up to 3 occurring in 12 distinct forest types under periodic constraints. For instance, starting from two adjacent live cells, the individual Sierpiński-like patterns from each cell superpose, but their overlap in the central region produces even (modulo 2), creating a persistent triangular clearing that bounds the outward growth; over 10-20 evolution steps, this manifests as two partial trees flanking a diamond-shaped void, with branches stunting at the edges of the interference zone. On finite rings with periodic boundaries of length N, boundary effects further stunt pattern development, as propagating signals wrap around and collide after roughly \log_2 N steps, leading to cycles or fixed points rather than continued expansion. Andrew M. Odlyzko analyzed this in , demonstrating that for N = 2^j, the configuration reaches the all-zero state—a stable fixed point—after j steps, while for other N, trees form balanced structures of height D_2(N)/2, where D_2(N) is the 2-adic order, resulting in looped or persistent bounded patterns. These stunted structures exhibit stability through short cycles, maintaining their form indefinitely under the rule's linearity, unlike the infinite case's relentless replication.

Replication dynamics

In Rule 90, an elementary one-dimensional defined by the rule where each cell's next state is the XOR of its two immediate neighbors, sparse initial configurations exhibit a replication process characterized by branching expansion. Starting from a single live cell (state 1), the pattern evolves into a symmetric structure where live cells propagate outward, effectively "replicating" the initial seed through additive superposition modulo 2, leading to multiple branches that mimic the seed's form at subsequent time steps. This branching continues indefinitely on an infinite grid, with the pattern filling space in a fractal-like manner during the initial phases, resembling the . The density of live cells evolves in a manner that reflects the automaton's linear structure. For an initial single live cell, the number of live cells at time step n is given by $2^{\omega(n)}, where \omega(n) denotes the number of 1s in the binary representation of n (the population count or Hamming weight); this sequence is known as Gould's sequence (OEIS A001316). While the absolute number of live cells fluctuates and can grow exponentially in bursts (e.g., reaching 8 at n=7, 16 at n=15), the overall density within the expanding light cone of width $2n+1 remains low, oscillating but averaging to zero asymptotically due to the sparse distribution of 1s amid extensive regions of cancellations from the modulo 2 arithmetic. For more general sparse initials, the density follows similar oscillatory behavior, with periodic modulations tied to powers of 2 in time, but consistently low on average across the grid. On an infinite , the replication dynamics cause patterns to spread at the maximum speed of 1 per step in both directions, as determined by the rule's neighborhood radius, eventually influencing every position within the causal . However, the effective filling is sparse, with large empty (all-0) regions persisting between replicated branches due to destructive interferences in the linear superposition; at times t = 2^k, the configuration consists of two identical copies of the evolved seed separated by a widening band of zeros, preventing uniform saturation. This sparsity arises fundamentally from the additive nature of the rule, where overlapping signals cancel modulo 2, maintaining a global density that does not approach 1 even over long times. Certain configurations in Rule 90 exhibit periodic behavior under the evolution rule. The all-0s state is a fixed point, remaining unchanged at every step since each cell receives 0 XOR 0 = 0 from its neighbors. Additionally, specific finite or periodic seeds can lead to cycles of length 2, where the configuration alternates between two states under repeated application of the rule, though such cycles are finite in number for each period due to the rule's expansive nature. In the long term, the replication dynamics of Rule 90 lead to a where, owing to the rule's surjectivity (every possible has at least one predecessor)—the from sparse initials produces persistently sparse, expanding patterns.

Computational analysis

Predecessors and surjectivity

In cellular automata, the predecessors of a C at time t = n are the configurations at time t = n-1 that evolve into C under the Rule 90 update rule. Due to the rule's additive nature, identifying predecessors reduces to solving a over the GF(2), where each cell's value in the next configuration is the modulo 2 of its left and right neighbors in the previous one. This allows the backward evolution to be formulated as C = A P, where P is the predecessor configuration, A is the infinite tridiagonal update matrix with 1s on the off-diagonals, and all operations are over GF(2). For a single time step, every possible configuration has exactly 4 predecessors, arising from the local rule's structure that imposes two degrees of freedom per cell pair while maintaining consistency across the line; this corresponds to a 2-to-1 branching factor locally, compounded to 4 globally due to the interdependent neighborhood. Extending to n steps, the number of predecessors grows exponentially as $4^n, reflecting the repeated application of the non-injective linear map and the increasing size of the solution space. In finite periodic settings with even length N, this aligns with balanced quaternary trees in the state transition graph, while for odd N, it adjusts to 2 per step initially before stabilizing. Rule 90 is surjective on the space of all bi-infinite binary configurations, meaning every possible configuration is reachable from at least one initial state after any number of steps; this follows from the polynomial representation p_{90}(z) = z + z^{-1} having no zero divisors in the ring of Laurent polynomials over GF(2), ensuring the global map is onto. To compute predecessors explicitly, one finds a particular solution to the linear system via forward propagation from boundary assumptions or matrix methods, then adds elements from the kernel of A, which consists of configurations that evolve to the all-zero configuration under one application of the rule (e.g., all-even or all-odd parity patterns); the non-trivial kernel (dimension 2 per step) accounts for the multiplicity beyond uniqueness. The surjectivity implies no configurations exist without predecessors, enabling complete backward coverage in the configuration space, in contrast to non-surjective rules that orphan certain states. However, the forward evolution loses information due to collisions (non-injectivity), creating ambiguity in reverse reconstruction where multiple histories are consistent with a given present state; this branching structure underscores Rule 90's irreversible dynamics while preserving reachability.

Absence of Gardens of Eden

In cellular automata, a refers to a that has no predecessor, meaning it lies outside the of the and cannot evolve from any prior state. This concept, introduced by , highlights configurations that can only serve as conditions and underscores non-surjectivity in the automaton's . For Rule 90, operating on bi-infinite configurations over \mathbb{Z}, the is surjective, implying every has at least one predecessor and thus no Gardens of Eden exist, either finite or infinite in support. This surjectivity follows from the rule's additive structure over \mathrm{GF}(2), where the local update a_i(t+1) = a_{i-1}(t) \oplus a_{i+1}(t) allows reconstruction of predecessors via linear algebra; specifically, the associated Laurent polynomial z^{-1} + z generates the full configuration space without zero divisors in the infinite domain. Predecessor counting confirms this: each admits exactly four predecessors, which differ by additions (modulo 2) of the period-2 kernel configurations, ensuring the map is onto. In contrast to , a Class IV automaton known to possess Gardens of Eden due to its non-surjective dynamics, Rule 90 as a Class III rule exhibits full surjectivity, ensuring every is reachable from some initial state, though with multiplicity due to non-injectivity. This distinction arises from Rule 90's linearity, which precludes transient structures unique to nonlinear rules like Rule 110. The absence of Gardens of Eden in Rule 90 aligns with the Moore-Myhill theorem, which equates surjectivity to pre-injectivity (absence of indistinguishable ) for cellular on \mathbb{Z}; Rule 90 satisfies these conditions through its algebraic properties, avoiding the finite-case pitfalls observed in bounded domains where odd-parity act as Gardens. While pure 1D Rule 90 admits no Gardens of Eden, extensions to 2D neighborhoods or variants with can introduce unreachable states resembling Gardens, as the added dimensionality or disrupts the linear invertibility.

Applications and extensions

Combinatorial connections

Rule 90 exhibits a profound connection to through its equivalence to the structure of computed modulo 2, where each cell in the automaton's evolution corresponds to a reduced modulo 2. Specifically, starting from a single live cell, the state of the cell at position k after n steps is given by \binom{n}{k} \mod 2, revealing the pattern as the set of positions where the is odd. This modulo-2 reduction highlights the automaton's additive nature over the field , where live cells (1) represent odd parities and empty cells (0) even ones. The number of live cells in each row of Rule 90 aligns with Gould's sequence (OEIS A001316), which counts the odd entries in the nth row of and equals $2^{w(n)}, where w(n) is the number of 1s in the binary expansion of n. This sequence grows multiplicatively based on the binary digits of the step number, providing a direct combinatorial measure of the automaton's density at each time step; for example, at step n=5 (binary 101, with two 1s), there are $2^2 = 4 live cells. The connection underscores how Rule 90 encapsulates the binary weight function in its . Lucas' theorem further elucidates this structure by stating that \binom{n}{k} \equiv 1 \pmod{2} if and only if every digit of k is less than or equal to the corresponding digit of n (i.e., the representation of k is a "" of that of n). This bitwise condition precisely determines the live cells in Rule 90's evolution, linking the automaton's rule directly to arithmetic and explaining the self-similar, fractal gaps in the pattern without requiring explicit computation of large binomials. An intriguing analogy arises with Gilbreath's conjecture from 1958, where iteratively taking absolute differences of consecutive primes yields sequences starting with 1, reminiscent of the binary-structured parities in Rule 90's patterns, though the connections remain exploratory. Beyond these, Rule 90 connects to other combinatorial objects, such as the , a space-filling generated by L-systems that traces the same triangular as the automaton's pattern, and the , which appears in the parity of binary weights underlying the rule's limits and overlaps. Additionally, the rule's linear algebra over GF(2) has implications for , where its primitive polynomial associations enable constructions of maximal-length for error-correcting codes, as seen in linear feedback shift registers mimicking the automaton's evolution.

Emulation by other automata

Rule 90, being a linear additive over GF(2), can be embedded within other elementary cellular automata through specific initial conditions, subspaces, or linear transformations that preserve its XOR-based update rule. For instance, Rule 126 emulates Rule 90 when initialized with periodic conditions of a particular form, such as alternating blocks that filter out nonlinear components, resulting in identical patterns. Similarly, Rule 45 produces a slanted variant of Rule 90's nested structure when started from a single live on a background of repeated blocks, effectively rotating the pattern while maintaining the dimensionality. In Rule 102, another additive rule, Rule 90 dynamics emerge on even time steps under certain linear combinations of states, leveraging the shared mod-2 arithmetic to simulate the neighbor-XOR operation without the self-term interference. Rule 22 exhibits subspaces where Rule 90-like ergodic patterns appear, particularly in analyses of Hausdorff dimensions approaching log₂(3) ≈ 1.585, though full embedding requires restricting to linear subspaces to suppress chaotic divergences.

2D Extensions

In two-dimensional variants, Rule 90's Sierpiński patterns manifest through XOR-based rules applied across rows and columns. For example, XOR cellular automata, where each cell updates as the mod-2 sum of its orthogonal neighbors, generate Sierpiński triangles analogous to the 1D case, with fractal boundaries scaling by powers of 2. In the automaton (B36/S23), a variant, replicator patterns evolve into large Sierpiński triangles filled with self-replicating structures, where the growth rate follows exponential bounds tied to Rule 90's additivity.

Higher Dimensions

Generalizations of Rule 90 to higher dimensions involve linear cellular automata where updates are mod-2 sums over nearest neighbors in d-dimensional lattices, preserving additivity and producing hyper-Sierpiński structures with fractional Hausdorff dimensions. These are emulated in quantum cellular automata (QCA) via layouts that map classical XOR gates to quantum reversible operations, such as ten-cell QCA circuits implementing Rule 90 with periodic boundaries for efficient simulation of linear dynamics.

Non-Cellular Systems

Rule 90 is simulated in linear feedback shift registers (LFSRs) using feedback polynomials equivalent to its neighbor-XOR rule, such as primitive polynomials over GF(2) that generate maximal-length sequences mirroring the automaton's periodic behaviors for pseudorandom number generation. Variants of Conway's soldiers problem incorporate Rule 90-like jumps, where soldier advancements follow mod-2 sums to bound reachability, though full emulation requires restricting to linear subspaces to avoid undecidable configurations.

Practical Implementations

Emulating Rule 90 in environments yields efficiency gains by leveraging additivity for vectorized XOR operations across subspaces. Additive rules like Rule 90 and Rule 102 allow for algebraic optimizations in , such as self-composition techniques that reduce for large-scale evolutions.