Section 1
Some configurations have no parents
Take a cyclic tape of length N — a ring of N black or white cells. Apply an elementary CA rule: each cell looks at its left neighbour, itself, and its right neighbour, then flips or stays according to the rule table. The result is a new configuration. Repeat.
Most configurations can be reached from something. A Garden of Eden cannot. No matter what configuration you start from, no matter how many steps you take, you will never land on it. It can only appear as the very first row — placed by hand, not generated by the rule.
The state space for a tape of length N has 2N configurations. The orphan count tells you how much of that space is unreachable — how many configurations the rule permanently crushes into oblivion after the first step.
Section 2
How to find them: the de Bruijn graph
Walk the graph to find orphans.read in layers
Start here Orphans are configurations that nothing maps to. Build a small graph where edges record "this triple of cells produces this output bit." A length-N orphan is an N-bit string that isn't spelled out by any closed walk of length N in that graph.
High school The graph has 4 vertices — the four possible 2-cell overlaps (00, 01, 10, 11). Each vertex has two outgoing edges, one for each possible cell value on the right. Edge (ab → bc) carries the label produced by applying the rule to the triple abc. A closed walk of length N spells out an N-bit string. If a string can't be spelled by any closed walk, it's an orphan — nothing maps to it.
Undergrad More precisely: for an elementary CA with radius 1 (neighbourhood size 3), the de Bruijn graph has 22 = 4 vertices (pairs of bits), with edges for each 3-bit window labeled by the rule output. Reachable length-N configurations on a cyclic tape correspond to labels of closed walks of length N in this graph. The number of such closed walks is tr(AN) where A is the adjacency matrix (weighted by output). Orphan count = 2N − reachable. Surjectivity is equivalent to the graph being strongly connected in a suitable sense — formalized by the Amoroso–Patt (1972) algorithm for deciding surjectivity in O(22r) for radius-r CAs.
Going deeper On infinite tapes, surjectivity is decidable via the same de Bruijn machinery; Amoroso & Patt (1972) gave the algorithm. Sutner's work on CA transition graphs characterizes the full image structure. Kari (1992) showed that for 2D cellular automata the surjectivity question is undecidable — the elementary case is the easy one. Wuensche & Lesser's atlas of basins of attraction gives another window on orphan structure via backward iteration. The census shown here was computed by forward enumeration: apply the rule to every configuration, mark the image, count the unmarked. Equivalent in result to the de Bruijn walk count, simpler to code for small N.
Section 3
The census
All 88 inequivalent elementary CAs, sorted by orphan count. Rules related by reflection (left↔right) or colour complement are treated as equivalent; the smallest rule number in each class is the representative. Surjective rules — those with orphan count zero — are highlighted.
| Rule | Equiv. class | Class | Orphans | Fraction | Surjective |
|---|---|---|---|---|---|
| Loading… | |||||
Equivalence classes. Two rules are equivalent when one can be obtained from the other by reflecting the neighbourhood (swapping left and right) or complementing all colours (black↔white) or both. This gives exactly 88 equivalence classes among the 256 rules. Each class is represented by its smallest member. For example, Rule 30's class is {30, 86, 135, 149}.
Section 4
What the table shows
The census reveals how compressive each rule is — how much of state space becomes permanently unreachable after a single step.
Rule 0 and the constant rules
Rule 0 maps every configuration to the all-zero row. At N = 16, all 65,535 other configurations are orphans — 99.998% of state space is unreachable. Rule 0's complement (Rule 255) does the same in the other direction.
Rule 110: non-surjective
Rule 110, the simplest known universal elementary CA, has 102 orphans at N = 8 and 37,542 at N = 16 — 57% of state space vanishes. Universality and surjectivity are independent properties.
Rule 30: not surjective here
Rule 30 has orphans at every finite cyclic N tested: 33 at N = 8, 280 at N = 12, 2,337 at N = 16. The orphan fraction shrinks with N — 12.9% at N = 8, 6.8% at N = 12, 3.6% at N = 16. Rule 30 is not surjective even in the infinite limit — the de Bruijn graph has dead states, and configurations like ...0011... have no predecessor at any N. The famous open Rule 30 question is different: whether the centre column under a single-cell seed is statistically random (Wolfram 2002, p. 871).
Rule 90: XOR-linear, not always surjective
Rule 90 computes XOR(left, right). The map is linear over 𝔽2, so the orphan structure is the kernel structure of a circulant matrix. At every even N tested the kernel has dimension 2 (spanned by the two alternating-parity patterns), giving 75% orphans regardless of N: 192 at N = 8, 3,072 at N = 12, 49,152 at N = 16. At odd N the kernel is still non-trivial (50% orphans), so Rule 90 is never surjective on a finite cyclic tape. Martin, Odlyzko & Wolfram (1984) worked out the full kernel-dimension formula in terms of the factorisation of xN−1 over 𝔽2.
Surjective rules at all tested N
Exactly 4 of the 88 equivalence class representatives are surjective at N = 8, 12, and 16: Rules 15, 51, 170, and 204. These are the invertible constant-type rules — identity, NOT, and their colour-swap partners. Each maps configurations bijectively; no orphans exist at any N.
Most rules are strongly compressive
At N = 16, the median orphan fraction across all 88 rules is above 50%. Dynamics compress state space hard — the typical trajectory erases more than half the landscape on the very first step.
Section 5
What about infinite tapes?
On an infinite tape, the orphan count grows roughly as αN · 2N with α ∈ (0, 1) for non-surjective rules — exponentially many orphans, but exponentially fewer than the total configuration count. For surjective rules, the orphan count stays zero at every length.
Surjectivity on the infinite tape is decidable. Amoroso & Patt (1972) gave the algorithm: construct the de Bruijn graph for the rule, check whether the graph admits an Eulerian cover of a certain kind. For elementary CAs (radius 1), the graph has only 4 vertices and 8 edges — the check runs in constant time. For radius-r rules it costs O(22r).
Rule 30 is not surjective: the de Bruijn graph identifies explicit unreachable patterns at every length. The orphan fraction does shrink with N, but never to zero. The well-known Rule 30 conjecture is about something else entirely — the statistical randomness of the centre column from a single-cell seed (Wolfram 2002, p. 871).
For 2D cellular automata, the question is harder: Kari (1992) showed surjectivity is undecidable for two-dimensional CAs. The elementary case is genuinely tractable. That tractability ends at one dimension.
Section 6
Reversibility is rarer still
Surjectivity means every configuration has at least one predecessor. Reversibility (injectivity) means every configuration has exactly one. The distinction matters: a surjective rule might send two different states to the same successor, while a reversible rule is a true bijection — every step has a unique undo.
Of the 88 inequivalence classes, exactly four contain rules that are bijective on every finite cyclic tape: the classes represented by Rule 15 (NOT left), Rule 51 (NOT centre), Rule 170 (shift left), and Rule 204 (identity). Including reflections and complements, those four classes cover the rules {15, 51, 85, 170, 204, 240}. Every other ECA collapses some configurations together at some N, leaving orphans behind. The classical setting is Hedlund (1969), who characterised the bijective endomorphisms of the full shift; on finite cyclic tapes the question reduces to invertibility of a circulant matrix over 𝔽2.
The reversible rules are a strict subset of the surjective ones. Surjectivity without reversibility means the map is many-to-one on some configurations and one-to-none on others — exactly the orphan structure this census measures.
A dedicated page on reversibility — Only four are reversible — walks through it.