Gardens of EdenThe Patterns With No Yesterday
A cellular automaton is a machine for making tomorrow out of today. Feed it a row of cells and it hands you the next row, forever. But run it backward and a strange thing appears: some patterns have no yesterday. Nothing the rule can do produces them. They can be drawn, but never grown. These are called Gardens of Eden, and below you can hunt for them by hand, then meet the exact count of them, per ring size, for rules whose sequence has never been catalogued.
1. The machine that makes tomorrow
Pick a rule. Draw a starting ring, or shuffle one. Each step, every cell looks at itself and its two neighbours and decides its next state by the rule's little lookup table. The ring wraps: the last cell and the first are neighbours. Time runs downward.
2. The hunt for a lost yesterday
Here is one step of the same machine, laid out plainly. Edit the TODAY ring to any pattern you like. The machine then searches every possible yesterday for one that becomes it. Most patterns have one. Some have none at all: those are the Gardens of Eden.
3. Counting the un-producible
For a ring of n cells there are 2n possible patterns. How many of them are Gardens of Eden, with no predecessor at all? That count, as n grows, is a sequence, and it turns out to depend sharply on the character of the rule. Three regimes appear.
The bijective rules (shifts, the identity, the negations) are perfectly reversible: every pattern has exactly one yesterday, so there are no orphans, ever. The linear rules like rule 90, the one that draws the Sierpinski triangle, are subtler. On an infinite line they miss nothing, yet on a finite ring they leave gaps in a strict arithmetic pattern (rule 150 has orphans on a ring of n cells exactly when n is a multiple of 3). And the complex rules, rule 30 and rule 110 and the rest, are riddled with orphans at nearly every size, in counts that follow no formula anyone has found.
One quiet surprise lives in rule 30, the rule Mathematica once used as its random number generator. Its orphans thin out: at ring size 10 about one pattern in ten has no yesterday, at size 20 about one in fifty, at size 40 about one in fifteen hundred. The fraction falls to zero. And yet the raw number of orphans climbs forever. Rule 30 can eventually produce almost any pattern you name, but on every ring, without exception, a few remain that it never will.
The check
Every number on this page is recomputed in your browser as you read, three ways that must agree. The Garden of Eden count is found by brute force (build every one of the 2n patterns, run the rule, and see which patterns are never the output) and, independently, by a transfer matrix over the automaton's de Bruijn graph (a pattern has a predecessor exactly when a certain product of small boolean matrices has a nonzero trace). A third method, a constraint search around the ring, decides any single pattern on its own. The verdict banners above come from that third method; the census strip comes from the first two; the panels below report whether they match.
Offline, the same three methods plus an independent Python reimplementation agree on
every term, with the reversible rules pinned to zero and the constant rules to
2n minus 1 as controls: node research/ca-garden-of-eden/verify.mjs
reports 19 of 19, verify.py reports 15 of 15. The count sequences for rules
30, 110, 184, 22, 126, 54 and 146 were checked against the OEIS on 2026-07-19 and found
absent; they are staged with b-files to n=64 for a citable deposit in
oversight/oeis/ca-garden-of-eden/.
Honest apparatus
- What is proven. That the six reversible elementary rules have no orphans on any ring, and that the constant rules leave exactly 2n minus 1, are proved (bijections; and a single-image map). The de Bruijn transfer-matrix method is a standard, exact construction; it agrees with brute-force enumeration on every ring size where brute force is feasible (to n = 24 for rule 30).
- What is observed. That rule 30's orphan density falls to zero while its count grows without bound is computed, not proved here: it is the directly measured behaviour out to n = 64. The claim that the count sequences follow no closed form is a statement about the present state of knowledge, not a proof of impossibility.
- What is a free choice. The ring (periodic) boundary. A different boundary, an infinite line or a fixed edge, gives different counts. On the infinite line the Garden-of-Eden question is governed by the Moore and Myhill theorem (a rule has an orphan iff it is not surjective); the finite-ring counts here are a distinct object, and are why rule 90 shows orphans on a ring though it is surjective on the line.
- Absence is a checked claim, not a permanent one. "Absent from OEIS" means no match on 2026-07-19 by the literal digit strings and by keyword. The OEIS grows; a later reader should recheck before citing.
- Sources. E. F. Moore, "Machine models of self-reproduction" (1962); J. Myhill,
"The converse of Moore's Garden-of-Eden theorem" (1963); S. Wolfram, A New Kind of
Science (2002), for the rule numbering; D. Lind and B. Marcus, Symbolic Dynamics
and Coding (1995), for image counting of sofic shifts. Engine and verifiers:
research/ca-garden-of-eden/.
A layer in the small-true-discoveries program: take a clean object, compute an integer sequence exactly by several independent methods, find it absent from OEIS, show the check, and name the open edge. Sibling to One Word Apart and The Lights That Hide.