# 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.)