automata.md

--- title: The automata lead: An elementary cellular automaton is a three-dimensional design read as a rule and Life a nine-dimensional one: what the identity buys, and what it cannot. figure: research-automata slug: automata ---

An elementary cellular automaton is a three-dimensional parity design read as a rule, and Life is a nine-dimensional one. A rule table on k binary inputs is a subset of {0,1}^k, and a design is a subset of the corners of {0,1}^dim; put k = dim and they are one object. This page states what that identity buys - a class lattice, a Walsh profile, a genus and a dimension for every rule, the Moore neighbourhood as the level-1 carpet tile in every dimension, and a decoupling lemma that says which masks carry a rule space of their own - and what it cannot: geometry does not decide surjectivity, Life is not a product of two elementary rules, and no census here can reach universality.

Every claim carries a tag. Proved means the proof is written here or on the page it points to; Verified means recomputed from scratch by a lab study; Conjecture means neither; Refuted means shown false. The generators are lab/rs/automata-census, lab/py/life-census and lab/py/sibling-census. Two demos run the same objects through wasm: the wolfram demo draws the 256 rules from one seed beside their cube classes, and the mrlylife demo runs Life and its siblings on any mask of the tree.

1 The identity

Wolfram's rule N sends the neighbourhood (l, c, r) to 1 exactly when bit 4l + 2c + r of N is set (Wolfram 1983). The design bang dim 3, code N of core fills corner i of {0,1}^3 exactly when bit i of N is set, corner i carrying the digits (x0, x1, x2) with i = 4 x0 + 2 x1 + x2. Under (x0, x1, x2) = (l, c, r) the two are the same subset of {0,1}^3, bit for bit. (Proved by the two definitions; Verified on all 2048 rule cells over the 256 codes, lab/rs/automata-census.)

So every invariant of a design is an invariant of a rule with no translation step: popcount, GF(2) degree, genus, Walsh spectrum, fill polynomial and dimension, all from core, bijection and complexity. The rest of this page asks which of them the dynamics respects.

2 The class lattice

Four groups act on the 256 truth tables. R is the left-right reflection, order 2. H = <reflection, conjugation> is Wolfram's equivalence, order 4, where conjugation complements every input and the output together. B3 is the cube group of bijection, the signed permutations of the three axes, order 48. B3 x Z2 adjoins the output complement, order 96. Each count is taken twice, by orbit walk and by Burnside, and the two agree:

(Verified, lab/rs/automata-census; the 22 and the 14 are the dim 3 row of bijection, so they are Boolean-function counts and nothing about dynamics is claimed for them.)

H and B3 are incomparable subgroups of B3 x Z2 and meet exactly in R. (Proved.) Conjugation complements the output, so it lies outside B3; the axis swap l <-> r is the reflection, so R lies in both; and B3 contains the flip of one input, which is not in H. Hence H meets B3 in R, neither contains the other, and the two reductions 256 -> 88 and 256 -> 22 are two branches joined only at the 14, not a chain. The witness is rule 137: the H class of 110 is 110, 124, 137, 193, and 137 lies outside the 24-rule B3 orbit of 110, so a cube class is not a union of Wolfram classes; the popcounts on that H class are 5, 5, 3, 3, so popcount is not an H invariant. (Verified, lab/rs/automata-census.)

The free 48-element group is not a symmetry of the lattice. A permutation of (l, c, r) that is not the reflection moves the centre off the centre, and the symmetries of the line are translations and reflections, which is why the automata literature classifies by H and its neighbourhood-scaling extensions and not by B3 (Schaller and Svozil 2025). A classification of the 256 rules by B3, with the 22 representatives and the lattice above, is not found in print; the count itself is the classical NP count and is not new.

3 Geometry is not dynamics

Two exact dynamical properties are decided for every rule. Surjectivity of the global map is decided by determinising the labelled de Bruijn graph and asking whether the empty subset is reachable, which terminates on at most 2^4 subsets; injectivity by the pair graph on ordered pairs of de Bruijn nodes with equal output label. Both are decidable in one dimension (Amoroso and Patt 1972), and the de Bruijn route is Sutner 1991; both are undecidable in two dimensions (NKS note, surjectivity), which is why nothing below is said about Life.

• Exactly 30 rules are surjective; the exact preimage-balance test on every word of length 1 to 12 shrinks 70, 34, 30, 30, ... and equals the walk's set from length 3 on. The count is the known one (NKS note, surjectivity). (Verified, two generators, lab/rs/automata-census.)
• Exactly 6 rules are injective, 15, 51, 85, 170, 204, 240, every one surjective, so 6 are reversible. The count is on record without the rule numbers (NKS page 436); the numbers are this study's. (Verified.)
• The reversible six are exactly the B3 orbit of 204, the degree-1 single-axis designs c, l, r and their complements, so reversibility is constant on every one of the 22 cube classes. (Proved that the orbit of 204 is those six: a signed axis permutation sends the single-axis function c to one of l, c, r or its complement, and nothing else; Verified that the six reversible rules are that orbit and that reversibility is constant on all 22 classes, 0 mixed.)
• Surjectivity is not constant on the cube classes. Of the 22, 3 are wholly surjective, 18 wholly non-surjective and exactly 1 is mixed: the class of 30, of size 24, surjective on 30, 45, 75, 86, 89, 101, 106, 120, 135, 149, 154, 166, 169, 180, 210, 225 and not on 54, 57, 99, 108, 147, 156, 198, 201. The witness pair is 30 surjective and 54 not, one orbit apart. (Proved by witness; Verified.)
• Surjectivity is constant on all 88 H classes, 0 mixed. (Verified.) So the lattice symmetry preserves both properties and the cube symmetry preserves only one; the geometry of the design fixes reversibility and does not fix surjectivity.

The Walsh transform on this page is taken on (-1)^f, W(S) = sum_x (-1)^(f(x) + S.x), so the weight-zero level sum is Sigma_0 = 8 - 2 popcount on every rule. (Proved: W(empty) = sum_x (-1)^f(x) counts the zeros minus the ones.) Section 6 uses the 0/1 convention instead and says so. The multiset of |W| at each character weight is a B3 invariant on all 256 rules, and the signed level sums Sigma_j are not: the B3 orbit of 110 carries 6 distinct Sigma vectors. (Verified.)

The card of rule 110, the rule Cook 2004 proves Turing universal. Its B3 orbit is the 24 rules 61, 62, 91, 94, 103, 110, 118, 122, 124, 155, 157, 167, 173, 181, 185, 188, 199, 203, 211, 217, 218, 227, 229, 230, none surjective, none reversible, all of degree 3, popcount 5 and genus compound, with one Walsh amplitude profile. No invariant of the design separates 110 from a class-mate; the single-seed diagrams of section 5 separate all 24, and the occurring neighbourhood set splits 122 and 218, which meet only the 5 neighbourhoods 00110111, from the other 22, which meet all 8. (Verified, lab/rs/automata-census.)

4 The additive bridge

Where the rule is affine over GF(2) the space-time diagram from one seed is a design of the tree. Rule 60 read rightward from the seed is bang dim 2, code 13; rule 102 read leftward is bang dim 2, code 14; rule 90 in the sheared coordinate j = (t + i)/2 is bang dim 2, code 13; each matches cell for cell at levels 1 to 8 and each is the unique match among the fill-3 codes 7, 11, 13, 14. (Verified, two renderers, lab/rs/automata-census.) The Laurent polynomials are the ones of Martin, Odlyzko and Wolfram 1984: rule 90 is x + x^-1, rule 150 is x + 1 + x^-1; that paper observes rule 90's dimension log2 3 and does not name Pascal. Rule 60 is x_i + x_(i-1), the binomial recurrence over GF(2), so its rows from one seed are the rows of Pascal's triangle mod 2, A047999, by induction on the row. (Proved.)

Rule 150 is not a design of the tree but an XOR substitution. Its rows are (1 + x + x^2)^t over GF(2), and (1 + x + x^2)^2 = 1 + x^2 + x^4 because the cross terms come in pairs, so (1 + x + x^2)^(2t) = (1 + x^2 + x^4)^t: row 2t is row t spread by two, and row 2t + 1 is row 2t xor its two unit shifts. (Proved; Verified on rows 0 to 128.) Its row populations are A071053. (Verified, 65 terms.)

Let P(k) be the live cells in rows 0 .. 2^k - 1 and B(k) the adjacent live pairs summed over the same rows. Then P(k+1) = 4 P(k) - 2 B(k) and B(k+1) = 2 P(k) - 2 B(k). (Proved.) Row 2t has the cells of row t at even positions, |r_t| of them and no adjacent pair. Row 2t + 1 keeps those and adds the odd position 2i + 1 exactly when one of i, i + 1 is live in row t, which happens 2(|r_t| - B_t) times, so it has 3|r_t| - 2B_t cells; its adjacent pairs are (2i, 2i + 1) with i live and i + 1 dead and (2i - 1, 2i) with i live and i - 1 dead, 2(|r_t| - B_t) in all. Summing over t < 2^k gives the system. The matrix has trace 2 and determinant -4, so P(k+1) = 2 P(k) + 4 P(k-1) with P(0) = 1, P(1) = 4, hence P(k) = c (1 + sqrt5)^k + (1 - c)(1 - sqrt5)^k with c = (5 + 3 sqrt5)/10, equivalently P(k) = 2^k F(k+2) with F the Fibonacci numbers, and the growth exponent is exactly log2(1 + sqrt5) = 1.6942419. (Proved; Verified at k = 0..12, P(12) = 1544192, with B(0..11) = 0, 2, 4, 16, 48, 160, 512, 1664, 5376, 17408, 56320, 182272.) Nothing in this paragraph is new: P(k) is A087206, whose entry already carries the recurrence and 2^n Fibonacci(n+2), and whose sum relation to A071053 is on the A071053 entry; the eigenvalue method is Willson 1987 and the number log2(1 + sqrt5) is stated in NKS note, rule 150, the theorem being Willson's and the number the note's. The study re-derives them.

The 16 affine rules a0 + a1 l + a2 c + a3 r split by the weight of the linear part: 2 constants, 6 of one variable, 6 of two, 2 of three. Under B3 that is five classes, the constants 0 and 255 being fixed by every input flip; under B3 x Z2 the constants merge and there are four. (Proved by the count; the 16 are Verified by the degree sweep of lab/rs/automata-census.)

5 The single seed

One live cell on a line of width 2T + 1 + 2 pad with constant-0 boundary, evolved T steps and cropped to the central 2T + 1 window; every depth is run at pad = T and at pad = 2T and the two must agree cell for cell, which is the stability check.

• The 256 rules give 143 distinct diagrams, 89 up to left-right reflection, with class-size histogram {1: 118, 2: 13, 4: 4, 8: 4, 16: 4}, the same at T = 64, 128, 256 and at both pads. (Verified, lab/rs/automata-census.)
• The occurring neighbourhood set, the set of the 8 neighbourhoods a rule ever meets, is measured on the whole evolved padded line and is the same at the three depths, with sizes {4: 64, 5: 16, 6: 16, 7: 36, 8: 124}. (Verified.)
• The key of a rule is its occurring set together with the rule restricted to it, measured on that same region. Equal key implies equal diagram, 0 failures over all 65536 ordered pairs: two rules that agree wherever either one is ever asked cannot differ on the seed. (Proved, and the check is the exhaustive one.) The converse fails: the key takes 152 values against 143 diagrams, the 16 rules 23, 31, 55, 63, 87, 95, 119, 127, all the blinking diagram, and 151, 159, 183, 191, 215, 223, 247, 255, all ones from t = 1, sitting in 2 diagram classes that carry 4 and 7 keys, 11 in all. The split is a boundary artefact. Inside the cropped window the eight rules of either group meet only 000, 001, 010, 100, 111 and agree on all five, so they share one window key; at the ends of the padded line they meet the boundary neighbourhoods 011 and 110 and what those seed, and differ there. Restricting the occurring set to the window only coarsens a key, and equal window keys still force equal window diagrams, because the one cell outside the window that a window edge reads is a background cell whose neighbourhood also occurs inside the window at the same step; so on the cropped window the key takes exactly 143 values, one per diagram. (Proved.)

6 Life as a design

Life runs on the Moore neighbourhood, the 3 x 3 block minus its centre. That block is a design of the tree in every dimension. At side 3 the coordinate values are 0, 1, 2 and the only odd one is 1, so the single cell with every coordinate odd is the centre (1, ..., 1); the level-1 side-3 tile of the design "void iff every coordinate is odd" is therefore the full 3^dim block minus its centre, which is the dim-dimensional Moore neighbourhood. (Proved.) In the plane that design is bang dim 2, code 7, the Sierpinski carpet of core, of dimension log(8)/log(3) = 1.892789, and the tile equals the crate's Moore array cell for cell at dim 1, 2, 3, fills 2 of 3, 8 of 9 and 26 of 27. (Verified, lab/py/life-census.) The Life demo runs Conway's rule on those eight cells, the side-3 carpet tile with its centre popped, seeded by soup, glider or R-pentomino and run to its fate.

An outer-totalistic rule is a birth set B and a survive set S inside {0..8}, and as a design it is the dim 9 Boolean function f(c, n) = [c = 0][|n| in B] + [c = 1][|n| in S] on the centre c and the eight outer bits n. Outer-totalistic means a level set on the eight outer axes for each value of the centre, so there are 2^18 such rules, and the totalistic rules, level sets of all nine, number 2^10, every one isotropic. (Proved; Verified.) The numbers below are lab/py/life-census.

• Life, B3/S23, has fill C(8,3) + C(8,2) + C(8,3) = 140 of 512, so its lambda = 140/512. Fill over 2^dim is Langton's lambda, the fraction of rule-table entries with a live output (Langton 1990), by definition and not by a theorem; the edge-of-chaos hypotheses built on lambda are the ones Mitchell, Hraber and Crutchfield 1993 contest, and nothing of that kind is claimed here. (Proved; Verified.)
• At base 2 the dimension of core is log2(fill) = dim + log2(lambda), so at fixed dim it is a strictly increasing function of lambda and across dimensions it is not a function of lambda; for Life, dim 9 and log2(140) = 7.129283. (Proved; Verified.)
• Life has GF(2) degree 8 with 184 monomials. Its Walsh level sums in the 0/1 convention, W(S) = sum_x (-1)^(S.x) f(x), so that Sigma_0 is the fill, are 140, 308, -224, -896, -168, 840, 448, -224, -196, -28, and the squares over the 512 subsets sum to 71680 = 512 * 140, Parseval for a 0/1 function. (Verified, checked against a generating identity derived from the support alone.)
• Life is neither a level set of the popcount under any of the 512 flips nor a subcube support, so its genus is compound. (Verified.)
• The fill histogram over the 2^18 rules is mirror symmetric about 256, takes 479 of the 513 values and peaks at fill 256 with 3270 rules; the 34 unreachable fills are 5, 6, 7, 13, 14, 15, 21, 22, 23, 41, 42, 43, 49, 50, 51, 69, 77 and their mirrors, so lambda has gaps near both ends. 165 rules share Life's fill. (Verified.)
• Genus over the 2^18: isotropic 2044, axial only 4, compound 260096. (Verified.)
• The degree composition law: deg(B, S) = deg(B) when B = S, and max(deg(B), 1 + deg(B xor S)) otherwise. (Proved: f = g_B + c (g_B xor g_S) with g_B = [|n| in B], and g_B xor g_S = [|n| in B xor S]; the B = S case is the one where the second term vanishes, and the empty rule of degree -1 is why it is a case and not a formula. Verified on all 2^18.) The degree histogram is -1: 1, 0: 1, 1: 6, 2: 24, 3: 96, 4: 384, 5: 1536, 6: 6144, 7: 24576, 8: 98304, 9: 131072; count sets of degree at most d number 2^(d+1), and the rules of degree at most d number 2 * 4^d for d = 1..8. (Verified; the product form Proved from the law.)
• Exactly 8 life-like rules are affine over GF(2). (Proved: affine means f = alpha c + beta (n1 + ... + n8) + gamma, so B and S are each empty, full, the odds or the evens and share beta; that leaves the four degenerate rules and B1357/S1357, B1357/S02468, B02468/S1357, B02468/S02468. Verified by the degree of all 2^18.)
• The nine-cell XOR B1357/S02468 is the sum mod 2 of all nine Moore cells, with generating polynomial (1 + x + x^2)(1 + y + y^2) = k(x) k(y), k the rule 150 kernel, so every slice from one seed is the outer product of two rule 150 rows, its population is the rule 150 population squared, and at t = 2^j it is nine copies of the seed at spacing 2^j. (Proved: F^t = k(x)^t k(y)^t, the state at generation t of an odd-rule automaton being F^t by Theorem 1 of Sloane 2015; Verified cell for cell to t = 64.) Its population is A246035, whose entry already states a(n) = A071053(n)^2. (Verified, 20 terms.)
• Fredkin's replicator B1357/S1357 is the sum mod 2 of the eight outer cells only, kernel k(x) k(y) - xy, which is not a product; at t = 2^j it is the outer product with the centre copy removed, eight copies, because the rule 150 row has a live centre at t = 2^j. Its population is A160239, and the two sequences differ from t = 1, so the eight-cell and the nine-cell rule must never be conflated (Sloane 2015). (Proved; Verified at t = 1, 2, 4, 8, 16, 32, 64 and 20 terms.)

7 The dictionary

A MrlyMath automaton is a triple (dim, mask, kind). The mask is a base-2 design at odd side side and level level, drawn as its side^level tile, centred, with the centre popped; the offsets are the filled cells minus the centre, m of them. Kind GENERAL is any Boolean function of the centre and the m mask cells, 2^(2^(m+1)) rules; kind LIFE is outer-totalistic, f(centre, count over the mask), written B/S with B, S subsets of {0..m}, 2^(2(m+1)) rules. The dependency set is S = {0} union offsets, since the centre is always read, and m is the mask's budget, the largest count it can reach. The crate draws the mask with mrlymath::life::design_mask(dim, code, side, level) and steps a LIFE rule with mrlymath::life::next_grid, which counts over the mask and reads the centre through birth against survive.

Rung 1 with kind GENERAL is Wolfram's 256; rung 2 with kind LIFE is the 2^18 of section 6; the Cantor rung shares Life's rule space on a one-dimensional mask, and is the sibling of section 11. (Proved by the counts; Verified, lab/py/sibling-census.) Rule 110 is not outer-totalistic: 001 -> 1 and 100 -> 0 share the centre and the count, and the same pair excludes 30 and 184; exactly 64 elementary rules are. (Proved by the two neighbourhoods; Verified.)

8 The tower

Two isotropic families at side 3, level 1, in every dimension: family A, "at most one odd coordinate", codes 3, 7, 23, 279 at dim 1..4, and family B, "not every coordinate odd", codes 1, 7, 127, 32767. At side 3 a cell's popcount is its number of coordinates equal to 1. Family B excludes exactly the centre, 3^dim - 1 cells, the Moore neighbourhood of section 6. Family A keeps the 2^dim cells with no odd coordinate and the dim 2^(dim-1) with exactly one, 2^(dim-1)(dim + 2) in all: 3, 8, 20, 48. As popped masks they coincide iff 2^(dim-1)(dim + 2) = 3^dim - 1 for dim at least 2, which holds at dim 2, 8 = 8, and fails from dim 3 on, 20 < 26 and 48 < 80, the gap at dim 3 being the six face centres of popcount 2; at dim 1 both masks are {-1, +1}, since popping removes the centre. (Proved; Verified at dim 1..4, lab/py/sibling-census.)

So the Moore neighbourhood is the level-1 carpet tile in every dimension, while the Menger tile bang dim 3, code 23 is a different mask from dim 3 on: Menger-Life, section 11, is not Life on the 26-cell neighbourhood.

9 Decoupling

Take a dependency set S = {0} union offsets in Z^dim, the subgroup Lambda = <S> it generates, an arbitrary local rule phi : {0,1}^S -> {0,1} and the global map F(x)(p) = phi((x(p + s))_(s in S)).

The decoupling lemma. Proved. For every coset p + Lambda, F(x) restricted to the coset depends only on x restricted to the coset, because every p + s with s in S lies in p + Lambda. So F is the direct product over Z^dim / Lambda of one automaton per coset, and when Lambda has rank dim each factor, read in a Z-basis of Lambda, is the automaton with the same rule phi on the dependency set S written in those coordinates, which now generates Z^dim. Hence a mask of index |Z^dim / Lambda| > 1 runs that many independent interleaved copies of an index-1 mask under the same rule, and the two rule spaces are the same set of functions phi; when the rank is below dim the factors are infinitely many copies of a lower-dimensional automaton. Only an index-1 mask carries a rule space not already present on a smaller mask.

In one dimension the index is the gcd of the offsets. The parity tile at side 2r + 1 has offsets {-r, -r + 2, .., r} minus 0, all of the parity of r and two of them differing by 2, so the gcd divides 2 and the index is 2 when r is even and 1 when r is odd: sides 3, 5, 7, 9 give 1, 2, 1, 2. The Cantor tower at level level has positions with ternary digits in {0, 2}, all even, and centre (3^level - 1)/2 of the parity of level, so its index is 2 at even level and 1 at odd level: levels 1, 2, 3 give 1, 2, 1. (Proved for all sides and levels; Verified to side 9 and level 3, lab/py/sibling-census.)

The census over every base-2 design at dim 1, 2, sides 3, 5, 7, 9, levels 1..3, is 195 distinct masks: 95 of index 1, 70 of index 2, 18 of index 4 and 12 of rank below dim, which splits as 16, 11 and one empty mask at dim 1 and as 79, 59, 18 and 11 at dim 2; at dim 2, side 3, the diagonal mask bang dim 2, code 9 has index 2 and the von Neumann mask bang dim 2, code 6 index 1, while the both-even mask bang dim 2, code 1 at level 2 has index 4. Every decoupling mask at dim 1 equals index interleaved copies of its rescaled mask under the same rule, 16 mask-and-kind pairs, 40 steps, cell for cell. (Verified, lab/py/sibling-census; the equality is the lemma.)

10 Life is not a product

For elementary rules f, g the composite f.g applies f along every row and then g along every column; on a 3 x 3 block it is g(f(row0), f(row1), f(row2)), top row first, a dim 9 design like Life. Columns first is g.f on the transposed block.

Life is not a composite. Proved. Suppose B3/S23 = f.g. With the top and bottom rows zero, Life on the middle row (l, c, r) is l c r: survival needs l = r = 1 and birth never happens with two neighbours at most. That value equals g(f(000), f(row1), f(000)), a function of f(row1) alone; since l c r is not constant this function is a bijection of {0,1}, so f is AND3 or NAND3 and is constant on every row other than 111. Now take the block with rows 110, 000, 100, centre dead with count 3, where Life gives 1, and the zero block, where Life gives 0: every row of both is other than 111, so f takes one value on all six rows and the composite answers the two blocks alike. Contradiction; and Life is transpose-symmetric, so the other order fails too.

The exhaustive check agrees. The 65536 ordered pairs give 32260 distinct 9-input rules; B3/S23 occurs 0 times; the two orders agree for 2160 pairs; 1080 pairs are transpose-symmetric and 1048 carry the full dihedral symmetry of the square; 1036 pairs are outer-totalistic and realise exactly 10 life-like rules: the two constants, the centre B/S012345678 and its negation, AND9 = B/S8, NOR9 = B0/S, OR9 = B12345678/S012345678, NAND9 = B012345678/S01234567, the nine-cell XOR B1357/S02468 from 150.150 and 105.105, and its negation B02468/S1357. Every one is affine or a threshold at 0 or 9; no rule with a proper birth window is a composite. (Verified, exhaustive, lab/py/sibling-census.) That the 10 are exactly the outer-totalistic composites is Verified and not Proved.

The six reversible rules give the trivial class. f.204, f.170, f.240 are f on the middle, lower and upper row, since 204, 170 and 240 read the centre, the right and the left cell, and f.51, f.85, f.15 are their negations. (Proved by the six truth tables; Verified for all 256 f.) So 110.204, 110.170, 110.240 are rule 110 up to a vertical shift, universal by Cook 2004 with nothing new, and 110.51, 110.85, 110.15 are rule 145 = NOT 110 on rows, about which nothing is claimed.

11 The siblings

Three automata of the dictionary that are not on record, with what is proved and what is only searched. The generator is lab/py/sibling-census.

Cantor-Life, (1, {+-5, +-7, +-11, +-13}, LIFE) with B3/S23, the Life rule on the level-3 Cantor mask.

• Of the 8192 seeds of width at most 14 on a constant-0 line, 6113 die, 2003 reach a still life, 76 an oscillator with period in {2, 3, 4, 6}, none moves and none is undecided at 256 generations. Soups of 1024 cells die or freeze below 4 percent density, one run of period 6. (Verified; no mover over width 14 is a negative, not a proof.)
• The smallest still life is {0, 5, 7, 12}, four cells each reading exactly two others through +-5, +-7; the smallest oscillator is {0, 1, 2, 3, 7, 8}, period 2. (Verified.) No still life has fewer than four cells, at any width. (Proved: a live cell survives only with count 2 or 3, so in a three-cell pattern a < b < c every cell reads both others, which puts b - a, c - b and their sum c - a all in {5, 7, 11, 13}; no two elements of that set sum to a third, since the sums run 10, 12, 14, 16, 18, 20, 22, 24, 26. One or two cells read at most one other and die.)
• Four other rules on the same mask, soups of 1024 cells at three densities: B36/S23 behaves like B3/S23 with activity still lingering at density 0.5, B2/S sustains a soup near density 0.18, B3/S012345678 freezes near 0.65 at the densities 0.25 and 0.5, and B3678/S34678 dies, fills the ring or holds a long period at a density between 0.3 and 0.9. (Conjecture; the evidence is the soup runs of lab/py/sibling-census.)
• The nine-cell XOR B1357/S02468 on this mask is multiplication by K = 1 + sum_o x^o in GF(2)[x]/(x^1024 - 1). Its period on the ring of 1024 divides 256, and equals 256 on generic soups. (Proved: by Frobenius K^256 = 1 + sum_o x^(256 o); the eight offsets split four and four over the classes 1, 3 mod 4, so the eight terms pair off as x^256 four times and x^768 four times and cancel, giving K^256 = 1; while K^128 = 1 + sum_o x^(128 o) has support {0, 128, 384, 640, 896} and is not 1, so a soup returns at 256 exactly when K^128 does not fix it. Verified on every soup at three densities.)

Menger-Life, (3, Menger 20, LIFE), the Life rule on the 20 offsets of {-1, 0, 1}^3 with at most one zero coordinate, the level-1 tile of bang dim 3, code 23 popped.

• The leak lemma. The mask layer dz = 0 is the 4 in-plane diagonals and the layers dz = +-1 are full 8-cell Moore rings, so a cell in a plane reads its in-plane diagonal count plus the Moore counts of the cells directly above and below, and a cell one above the plane reads exactly the Moore count of the cell below it. For a plane configuration every cell with Moore count 3, dead or alive, sends a birth to the cell above and the cell below, and the in-plane rule counts 4 diagonals only; so Menger-Life restricted to a plane is not Life, and leaks out of the plane whenever a Moore-3 cell exists. (Proved by the layer decomposition.)
• The block stack. A plane 2 x 2 block at the set of heights H: a footprint cell at height h counts [h in H] + 3[h - 1 in H] + 3[h + 1 in H], so a live cell sees 1, 4 or 7 and dies, and a dead cell sees 3 exactly when one of its two neighbouring heights is live; a cell beside the footprint sees at most [h in H] + 2([h - 1 in H] + [h + 1 in H]), never 3 while H has a single parity. So H_(t+1) = {h : exactly one of h +- 1 in H_t}, rule 90 along the normal with the parity alternating, the blocks sit at the odd binomials of row t and the population is 4 * 2^popcount(t) by Gould's count A001316. (Proved; Verified to t = 8.)
• The soup census, 100 rules with B, S inside {3, 4, 5, 6} of size 1 or 2 plus B3/S23, 101 in all, on a 32^3 torus, 4 runs each spread over two densities, 200 generations: 310 runs are still active, with density between 0.186 and 0.305, 77 die, 14 fix, 3 are periodic, none exceeds 0.4; the 76 rules active in all four runs span 0.193 to 0.305; the 22 rules quiet in all four are every rule of birth {5} or {6} together with B4/S5 and B4/S6; B3/S23 holds density 0.20. (Verified.)
• No mover appears for any of the 101 rules from 200 random 5^3 seeds each on a re-centred field, exact while the extent stays at most 22, 128 generations: the 20200 fates are 7957 deaths, 12131 growing, 69 still lifes, 38 oscillators, 5 undecided, 55 of the still lifes sitting under B5/S34, B6/S34 and B56/S34; B3/S23 grows from all 200. (Verified negative.)

110.110, rule 110 on rows then on columns, a (2, Moore, GENERAL) rule of the dictionary that is not outer-totalistic.

• The bounding box of every finite pattern grows without bound. (Proved.) Under rule 110 the cell left of the leftmost live cell of a nonempty row sees 001 -> 1 and the one beyond sees 000 -> 0, so the leftmost live cell moves left by exactly one; the rightmost live cell sees x10 -> 1 and stays, and the cell right of it sees 100 -> 0. The row pass therefore moves the left edge of the box by -1 and fixes the right edge, and it preserves the set of nonempty rows; the column pass does the same to the top and bottom edges and preserves the set of nonempty columns. So the upper-left corner moves (-1, -1) each generation and the lower-right corner is fixed. (Verified on all 511 3 x 3 seeds to t = 96.)
• Population growth is Verified only: at t = 96 the 511 seeds run from 2704 to 5794 live cells, and torus soups under 110.g for g in {204, 170, 110} climb from density 0.30 to about 0.57, and to 0.41, 0.45, 0.46 for g = 54, 30, 90, with churn between 0.42 and 0.58 and none periodic by 512 generations. (Verified.)

12 The ceiling

• Membership in the Wolfram classes is undecidable (Culik and Yu 1988), and intrinsic universality is undecidable and recursively enumerable (Ollinger 2009). So no census on this page classifies a family as universal, and a mover census is not a universality result.
• Rule 110 is Turing universal (Cook 2004); whether it is intrinsically universal is open, and its Turing universality does not give intrinsic universality (Ollinger 2009).
• The trivial class of section 10 is closed by conjugacy: three shifts of 110, universal with nothing new, and three shifts of 145, about which nothing is known here.
• Because universality is recursively enumerable, an honest new claim is one witness: a simulation of one fixed universal automaton inside the candidate. For Cantor-Life or Menger-Life that means a mover, a still life that reflects it and a collision table before any gate; the census finds still lifes and oscillators on both masks and no mover, so the first brick is missing.
• Bulking is a quasi-order on space-time diagrams up to packing, iterating and shifting (Delorme, Mazoyer, Ollinger and Theyssier 2011a, Delorme, Mazoyer, Ollinger and Theyssier 2011b); a Kronecker level change of the mask is not a bulking, so "one level simulates the level below" is a claim to prove, not a citation. By the decoupling lemma it is false where the higher level decouples, and open at the index-1 levels.

13 The waves

• Larger than Life counts neighbours through a box of range r, and its bugs, still lifes and oscillators at range r are rescaled copies of those at smaller range (Evans 2001, Pivato 2007), so the box carries one scale; a design mask replaces the box by a Kronecker tile at level level, so one count carries level nested scales at once, where the Larger than Life, SmoothLife and Lenia sources read here use box, disk and ring kernels (Rafler 2011, Chan 2019).
• A window rule on a mask of budget m is two closed windows on count/m: a dead cell is born when its count lies in [ceil(b_lo m), floor(b_hi m)] and a live cell survives when it lies in [ceil(s_lo m), floor(s_hi m)]; Evans' Bugs is the box r = 5 of budget 120 with birth [34, 45]/120 and survive [34, 58]/120 (Evans 2001). The count is the circular convolution of the grid by the mask on a power-of-two torus, mrlynum::fft::convolve rounded, and that step agrees cell for cell with the direct step mrlymath::life::next_grid under a wrap boundary on the Moore mask and on the level-2 carpet mask, 8 steps. (Verified, mrlydemo::chladni.) A still is a run of zero churn at step 64, and a ring still is a still whose peak ring has gain at least 3, the ring's mean power over the mean across all rings, of wavelength at most twice the mask side.
• Riesz product. The DFT of the popped design mask at level level and frequency xi on an N torus is prod over j = 0..level-1 of P(side^j xi / N) minus the tile's centre value, P the level-1 tile polynomial sum over tile cells e of exp(-2 pi i theta . e): the offsets are digit sums, the exponential sum factorises, popping subtracts one term; it is the finite truncation of the infinite-product transform of a self-similar measure (Tsujii 2012, Morrison 2004, Liu, Wang and Zheng 2026). (Proved; Verified by lab/py/kernel-waves at codes 7, 6, 9, levels 2 to 4, all 256 x 256 frequencies, error below 2.5e-12.)
• Kill test. A Larger-than-Life still on a 256 torus from a density-0.5 soup, 64 steps, is read through the peak ring k* of its power spectrum on the rings k <= 128, the mask through the first minimum k_min and first side lobe k_2 of its ring-mean transform; under Bugs, a wide survive that keeps the Bugs birth with S[0.28, 0.60], and a narrow birth no mask of the seven reaches a ring still at one seed, 0 of 21, and the wide survive leaves the soup unchanged on the three masks of 512 cells or more in the sweep, the box r = 13 at 728 cells and code 7 at levels 3 and 4, so the laws are tested over a grid of 180 window rules at two seeds, 2520 runs, 176 ring stills. (Verified, lab/py/kernel-waves.)
• The wavelength is not the mask width: k* sits within one ring of k_min in 25 of 176 ring stills, 21 on the under-resolved side-81 mask; the box r = 5 holds 25 stills at k* = 30..36 against k_min = 24 and k_2 = 32, 7.1 to 8.5 cells of wavelength for a mask 11 wide. (Refuted, lab/py/kernel-waves.)
• The wavelength is the mask's first negative lobe: on box r = 5, code 7 levels 2 and 3 and code 9 level 3 every one of 130 ring stills has k* inside the negative band of the ring-mean signed transform, k*/k_2 from 0.77 to 1.17; three of 176 fall outside, box r = 13 at k* = 10, code 7 level 4 at k* = 2, code 6 level 3 at k* = 8, every one read on the rings k <= 128, which drop the Fourier corners. (Verified on four masks; Refuted as a universal law, lab/py/kernel-waves.)
• The ring moves inside the lobe, never out of it: box r = 5 spreads k* = 30..36 across the grid rules and seeds, one rule reading 32 at one seed and 36 at the other, so the seed moves k* as far as the rule; the carpet family's median wavelength over side is 0.729 at levels 2 and 3, the mask's own 256/k_2/side. (Verified, lab/py/kernel-waves.)
• Reading: a still lives where the kernel transform is negative, its count anti-correlated with its state, and the windows freeze it there; the side-81 mask needs a 1024 torus to resolve. (Conjecture.)
• The Chladni figures of a design are the nodal domains of its Laplacian eigenvectors (Chladni 1787). On the carpet cell graph, 4-neighbour adjacency and the combinatorial Laplacian D - A at A the adjacency matrix and D its diagonal of degrees, the strong nodal domain counts of the returned eigenvectors are 1, 2, 2, 4, 4, 4, 4, 5, 8, 8, 8, 8 at level 3 and 1, 2, 2, 4, 4, 4, 4, 5, 4, 4, 8, 8 at level 4, where the 4, 4 at eigenvector index k = 9, 10 is 64 cells at |v| = 1.4e-7 counted as signed and reads 8, 8 at tolerance 1e-6; every one of the 512 and 4096 satisfies Courant nu_k <= k at every tolerance from 1e-12 to 1e-6, though the theorem only promises nu_k <= k + r - 1 at multiplicity r (Davies, Gladwell, Leydold and Stadler 2001); half the indices are degenerate, 262 of 512 and 2062 of 4096, with multiplicities up to 4 and 20 (lab/py/carpet-nodal).
• On a degenerate eigenvalue the count depends on the basis: at the double eigenvalue k = 6, 7 the two returned vectors have 4 domains and their sum and difference 6, under the bound 7, at both levels; the counts on this page are facts about the returned basis, never about the eigenspace (lab/py/carpet-nodal).
• The control is the square grid, 22 x 22 and 64 x 64, where the separable cosine basis has exactly (p + 1)(q + 1) domains for the mode with p and q sign changes along the axes; the mean of nu_k / k over k >= 2 is 0.605 and 0.536 on the carpet against 0.508 and 0.465 on the separable grid and 0.433 and 0.330 on the grid's returned basis (lab/py/carpet-nodal).
• The top eigenvector changes sign across every edge on all four graphs, the carpet being bipartite, so nu_N = N up to the 12 cells at level 4 that fall below the zero tolerance 1e-9 (lab/py/carpet-nodal).

14 The atlas

• The atlas is a census of mrlylife over presets: the seed is a side-3 design class repeated t by t at odd t and padded to the canvas by half the difference; the mask is a popped design or the seed board copied; the rule is one of the fifteen count sequences or B3/S23, read at the mask's own budget, with two switches, the zero roll and the one roll, deciding whether the counts 0 and 1 stay in it; the boundary is wrap or constant; a run of T generations ends dead, still, in a loop of its length, or timed out; and every settled frame is read as a design through fill, topology, symmetry, the full-square spectrum and the Kronecker block test (mrlylab::atlas, lab/rs/life-atlas).
• Sublattice lemma. When every mask offset lies in dZ^2 and zero is outside birth, a frame A (x) B on the dn torus steps to A' (x) B, A' one step of the same rule on the quotient torus under the mask over d: the count at a cell in position p of its tile is B(p) times the quotient count, and a cell at an empty position reads zero. (Proved; Verified frame by frame on 16 runs of the mini preset, all 16 rules.)
• Closure has one proved backbone and it is the literature's: an odd rule, whose cell turns on exactly when its neighbourhood holds an odd count, is multiplication by the neighbourhood's kernel over GF(2), so from a single seed step 2^k is that seed copied at the neighbourhood's offsets scaled by 2^k (Sloane 2015), as section 6 works out on the Moore mask. The mini preset runs with the rolls off and holds no odd rule, so every frame below is a threshold frame.
• The mini preset runs 848 of 1120 nominal cells, 272 dropped as duplicate masks: 585 die, 43 still, 60 loop, 160 time out with no mover; with the rolls off the design sequences leave at most one count inside budget 8, the budget of 45 of the 53 mask cells, and 448 of their 477 runs die. (Verified.)
• Closure. Of 103 settled frames, 34 distinct up to the dihedral group and torus translation, tested at every torus shift and both cuts: in place 72 are confined to one block of the cut, 4 are full tilings, 1 is the board footprint, and the 3 proper cuts are the lemma's index-9 mask, no index-1 frame cutting properly; after a torus shift 6 index-1 frames do, all at cut 9, the corner seed's 16-cell still, four 2x2 blocks at spacing 3, on Moore and on the two-bar and cross masks, and the two-bar seed's 36-cell still on the cross mask. So a threshold rule on an index-1 mask can carry a design to a design, but only through a shifted lattice, and only in 6 of 48 index-1 settled runs. (Verified.)
• The stills. Of 21 stills from tessellation 3, the 5 whose peak ring sits on the seed comb are lattice-mask tilings or four-cell frames of share 0.06 on the index-2 corner mask; every Moore still peaks at ring 1, 4 or 6 against comb 9 and lobe 9, so the comb is not where a still of an index-1 mask lives. (Refuted, witness in lab/rs/life-atlas.)
• The heatmap's median level set cuts properly in 9 of 848 runs in place and 10 after shifts, and on the settled runs exactly where the settled frame does; the heatmap is a design no more often than the frame. (Verified.)
• Replaying the generator's own quests at seeds 1 to 64 under its default caps, lab/rs/still-hunt scores 4626 frames: 609 pass its ring cut (peak-ring share at least three times a random field's share at the same ring, wavelength at most twice the mask side), 426 of 1043 frames on basic-path masks, 76 of 92 on copy masks, 107 of 3491 on side-3 masks; only 3 of the 64 settled stills pass, all on side-3 masks; 149 of the 562 hits past generation 0 peak at ring 1 or 2 of their field, the crop's own envelope, 66 of them on the copy path, which is one quest with its own canvas as mask. (Verified.)
• On the 176 resolved drawn-mask frames (crop at least four mask sides, generation above 0, 15 chapters of correlated frames) the peak ring sits in the mask's first negative lobe in 52 and within half a ring of the seed comb in 77 against 53 by chance, so neither the lobe law of section 13 nor the comb product law survives the sequence rules; the witness is seed 3, chapter 1, mask side 23, peak ring 11 against lobe 13 to 22 and comb multiple 10. (Refuted.)
• At canvas cap 512 and mask cap 128, seeds 65 to 68, the one drawn-mask still found, seed 66 with a copy mask of side 75 on a board of 5 by 5 tiles, peaks at wavelength 51 cells, 0.68 mask sides, inside its lobe 8 to 13; the replay reproduces mrlygame::quest cell for cell on seeds 1, 4, 7 and 9, the four cheapest single-attempt quests. (Verified.)

Where the numbers live

lab/rs/automata-census is the 256-rule census: the class lattice, surjectivity and reversibility, the Walsh profiles, the single-seed diagrams and the additive bridge. lab/py/life-census is the 2^18 census and the two XOR rules on the Moore neighbourhood. lab/py/sibling-census is the dictionary, the tower, the decoupling census, the composite census and the three siblings. lab/py/kernel-waves is the Riesz product and the kill test of section 13, lab/py/carpet-nodal its nodal domains; mrlylab::atlas is the census engine of section 14, lab/rs/life-atlas its mini preset and lab/rs/still-hunt the generator's quests replayed and scored; the chladni demo runs a Larger-than-Life soup on any design mask by FFT beside the mask's spectrum and the still's. The wolfram demo and the mrlylife demo run the same objects in the browser. The Boolean-function side of the same designs is bijection and complexity; the designs themselves are core.