Automata Census

• Reads the 256 elementary cellular automata as the 256 base-2 designs of bang dim 3, then measures how much of the design tree survives as dynamics.
• The dictionary: Wolfram's rule N sends the neighbourhood (l,c,r) to 1 exactly when bit 4l + 2c + r of N is set, and the design code N fills residue corner i exactly when bit i of N is set, with corner i carrying digits (x0,x1,x2) and i = 4 x0 + 2 x1 + x2. So rule N and bang dim 3, code N are the same subset of {0,1}^3 under (x0,x1,x2) = (l,c,r), bit for bit.
• Six groups act on the 256 truth tables and each class count is taken twice, by orbit walk and by Burnside: R the left-right reflection of order 2, H = <reflection, conjugation> of order 4 which is Wolfram's equivalence, the flips-only subgroup of order 8, the permutations-only subgroup of order 6, the cube group B3 of signed axis permutations of order 48, and B3 x Z2 of order 96 with Z2 the output complement.
• One printed line per rule: the B3, H and B3 x Z2 representatives and orbit sizes, popcount, GF(2) degree, genus, the four Walsh level sums Sigma_0..Sigma_3, and the affine flag. Popcount over 8 is Langton's lambda.
• Two exact dynamical invariants per rule. Surjectivity is decided by determinising the labelled de Bruijn graph from the full node set and asking whether the empty subset is reachable, which terminates on at most 2^4 subsets and needs no word-length bound; it is corroborated by the exact preimage-balance test on every word of length 1 to 12. Injectivity is decided by the pair graph on ordered pairs of de Bruijn nodes with equal output labels, pruned to the nodes lying on bi-infinite paths.
• The single-seed census evolves one live cell on a line of width 2T+1+2 pad with constant-0 boundary, crops the central 2T+1 window and compares only that. Every depth is run at pad = T and pad = 2T and the two must agree cell for cell, which is what is asserted; scaling the width with T alone is circular. It counts distinct diagrams as exact sets and up to left-right reflection, records the neighbourhoods each rule ever meets on the whole evolved padded line, and measures how far the occurring key over-separates the diagram.
• The gasket section matches rules 60, 102 and 90 against the four base-2 dim 2 codes of fill 3, cell for cell to level 8, under two renderers: one written here and mrlycore::tensor::Tensor::fractal.
• The rule 150 section proves the diagram is an XOR substitution by the GF(2) identity (1+x+x^2)^(2n) = (1+x^2+x^4)^n, then closes the cell count and the adjacent-pair count of the first 2^k rows in exact integers, re-deriving what OEIS A087206 and A071053 already state.
• Structural laws are asserted; the study exits nonzero if one fails. Headline counts are printed.

RUN

• CARGO_BUILD_JOBS=4 cargo run --release -p automata-census
• About half a second; prints only, writes nothing, and holds one 256-rule diagram batch at a time, six batches in all, T = 64, 128, 256 at pad = T and pad = 2T; the batch is about 34 MB at T = 256.

WITNESSES

• Rule N and bang dim 3, code N are the same subset of {0,1}^3, agreeing on all 2048 rule cells over the 256 codes. (Proved by definition; Verified.)
• The class counts are 160 under R, 88 under H, 46 under flips, 80 under permutations, 22 under B3 and 14 under B3 x Z2, each taken twice and agreeing. (Verified.)
• H and B3 are incomparable subgroups of B3 x Z2 and meet exactly in R, so the reduction 256 -> 88 and the reduction 256 -> 22 are two branches, not a chain, joined only at 14. (Verified; proof on automata.md.)
• W is computed on (-1)^f, W(S) = sum_x (-1)^(f(x) + S.x), so the weight-zero sum is Sigma_0 = 8 - 2 popcount on all 256 rules; lab/py/life-census uses the 0/1 convention, where Sigma_0 is the fill. (Proved, W(empty) counts zeros minus ones; Verified.)
• 16 rules are affine; genus splits iso 52, axis 18, comp 186 over the rules and iso 10, axis 2, comp 10 over the 22 B3 classes, with orbit sizes {1, 2, 4, 6, 8, 12, 24}. (Verified.)
• Exactly 30 rules are surjective, by the de Bruijn subset walk. The balance test shrinks 70, 34, 30, 30, ... over word lengths 1 to 12 and equals the walk's set from length 3 on. (Verified, two generators.)
• Exactly 6 rules are injective, 15, 51, 85, 170, 204, 240, and every one of them is surjective. (Verified.)
• The reversible six are exactly the B3 orbit of 204, the degree-1 single-axis designs. Reversibility IS constant on every B3 orbit, 0 mixed of 22, so B3 fails only on surjectivity. (Verified.)
• Of the 22 B3 classes, 3 are wholly surjective, 18 wholly non-surjective and exactly 1 is mixed: the class of rep 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. So surjectivity is not a B3 invariant, with witness pair 30 surjective and 54 not, sharing one orbit. (Proved by witness; Verified.)
• Surjectivity is constant on all 88 H classes, 0 mixed. (Verified.)
• The single seed gives 143 distinct space-time diagrams and 89 up to left-right reflection, with class-size histogram {1: 118, 2: 13, 4: 4, 8: 4, 16: 4}, identical at pad = T and pad = 2T and the same at T = 64, 128 and 256. (Verified.)
• The occurring neighbourhood set is the same at T = 64, 128 and 256, with sizes {4: 64, 5: 16, 6: 16, 7: 36, 8: 124}. (Verified.)
• The key of a rule is its occurring set, measured on the whole evolved padded line, together with the rule restricted to that set. Equal key implies equal diagram, 0 failures over all 65536 ordered pairs. The converse fails: the key takes 152 values against 143 diagrams, so it over-separates. The 16 rules it splits are 23, 31, 55, 63, 87, 95, 119, 127, which all give the blinking diagram, and 151, 159, 183, 191, 215, 223, 247, 255, which all give all ones from t = 1; they sit in 2 diagram classes carrying 4 and 7 keys, 11 in all. Measured on the cropped window instead the key would be complete, 143 keys, since inside the window either group of eight meets only 000, 001, 010, 100, 111 and agrees there; the split comes from the boundary neighbourhoods at the ends of the padded line. (Verified for the 152; the 143 on the window is Proved on automata.md.)
• Rule 60 read rightward from the seed is bang dim 2, code 13, rule 102 read leftward is bang dim 2, code 14, and rule 90 in the sheared coordinate j = (t+i)/2 is bang dim 2, code 13, each matching cell for cell at levels 1 to 8 and each the unique match among the fill-3 codes 7, 11, 13, 14. (Verified, two renderers.)
• The rule 150 rows are (1+x+x^2)^t over GF(2), so row 2t is row t spread by two and row 2t+1 is row 2t xor its two unit shifts, checked on rows 0 to 128. The diagram is therefore an XOR substitution. (Proved; Verified.)
• The rule 150 row populations for t = 0..64 are OEIS A071053, whose name is the same object. (Verified.)
• Let P(k) be the live cells in rows 0..2^k - 1 and B(k) the adjacent filled pairs summed over the same rows. Spreading and shifting give P(k+1) = 4 P(k) - 2 B(k) and B(k+1) = 2 P(k) - 2 B(k), a matrix of 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). The growth exponent is exactly log2(1+sqrt5) = 1.6942419. Both P and B are counted off the evolved diagram and the two-term system is asserted at k = 0..11, with B(0..11) = 0, 2, 4, 16, 48, 160, 512, 1664, 5376, 17408, 56320, 182272. (Verified at k = 0..12, P(12) = 1544192; proof of the system on automata.md.)
• P(k) over rows 0..2^k - 1 is OEIS A087206, not a running partial sum of it; A087206 %N already carries a(n) = 2 a(n-1) + 4 a(n-2), its %F already carries a(n) = 2^n Fibonacci(n+2) and the (1 +- sqrt5) form, and A071053 %F already carries Sum_{k = 0..2^n - 1} a(k) = A087206(n). The study re-derives them; nothing here is new. (Verified.)
• The multiset of |W| at each character weight is a B3 invariant on all 256 rules, while the signed level sums Sigma_j are not: the B3 orbit of 110 carries 6 distinct Sigma vectors. (Verified.)
• The B3 orbit of 110 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 the Walsh amplitude profile constant. None of the invariants computed here separates 110 from a class-mate. (Verified.)
• On that orbit the single-seed diagram separates 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.)
• The H class of 110 is 110, 124, 137, 193 with popcounts 5, 5, 3, 3, so popcount is not an H invariant; 137 and 193 are outside the B3 orbit of 110. (Verified.)