Reproducing the Symbolic Systems of A New Kind of Science

An engineering walkthrough · the nks-symbolic project · June 2026

This is the record of reproducing, in a small Rust engine, essentially every quantitative experiment published about symbolic systems in Wolfram’s A New Kind of Science: the rewriting systems of §3.10, their combinator relatives, and the cellular-automaton emulations behind the book’s universality argument. It is also a record of how — the dead ends, the conventions that had to be excavated, and the places where the reproduction overtook the original.

Every discrepancy met along the way — 264 vs 263, the 7050, the “≈49”, the edge zeros — resolved to a counting convention or a definition. Not one was a behavioral disagreement with the book.

• 1. The semantics contract
• 2. Golden numbers, and a race against the kernel
• 3. Numbering every symbolic system
• 4. The combinator corpus, exhaustively
• 5. The universality bridge
• 6. The figures themselves
• 7. What remains
• Appendix A — the reproduction ledger
• Appendix B — the crate
• Appendix C — implementation notes

1  The semantics contract

The book defines an evolution step as Mathematica’s expr /. rules (p. 102; notes b and i). We treated that as a formal contract: on curried expressions it is a pre-order traversal — try the rules at each node, first match wins; on a match, emit the instantiated right-hand side and descend into neither the replacement nor the matched region; otherwise head, then argument. The consequences are subtle enough that each gets a test mirroring a kernel one-liner:

• a /. {a→b, b→c} ⇒ b — replacements are never rescanned;
• f[a] /. {a→g, f[g]→X} ⇒ f[g] — parents match against their original children;
• f[a] /. {f[a]→X, a→b} ⇒ X — outermost position beats rule order;
• rules fire at atoms and in head position; repeated names demand identical matches; _ binds nothing.

Process. wolframscience.com 403s generic fetchers; plain curl with a browser user-agent got every page. The decisive move came before any Rust was written: a local Wolfram kernel pinned the canonical trajectory — first six states verbatim, twelve leaf counts, and “evolves after 264 steps” resolved to first fixed state at 263. Coding against pinned ground truth, the whole suite passed on its first run.

Beyond the book. The book had one implementation; now there are two. A differential fuzzer runs random rule systems on both engines and compares every state of every trajectory string-exactly against wolframscript: 48 random systems, the canonical trajectory, and a state 1,500 steps and ~1,500 levels deep — all byte-identical.

2  Golden numbers, and a race against the kernel

Page 103 makes two crisp claims, and both land: a fixed configuration of 256 opening + closing brackets after “264 steps” (fixed_at = 263), and 65,536 bracket pairs after “65,555 steps” (fixed_at = 65,554) — one counting convention, confirmed twice. The conserved quantity of note (e), val(f[a]) = 2val(f) + val(a), holds at every step, predicts both endpoints, and later became the tool for manufacturing benchmark systems of any size.

Process. The 65,555-step run was the first real failure: retaining the trajectory held billions of shared nodes and the OS killed the process. The fix — streaming evolution, one state retained — brought it to 173 s in 182 MB. The deeper lesson: fixed points run 65,536 levels deep, so nothing may recurse on expression depth. Even Drop is a hand-written worklist; the standard destructor would overflow unwinding a fixed point.

Beyond the book — by an asymptotic margin. On identical Nest[# /. rule &, …] workloads, cross-verified state by state:

The gap is a complexity class, not a constant: our totals grow as m², the kernel’s as m^3.04 across the whole range. Probes isolated why: the kernel’s no-match scan is excellent (linear; 8.6 ms over 65k nodes), but a rewrite at depth d costs it O(d²) to rebuild, versus O(d) for a persistent shared tree. The extrapolated week is moot anyway — with default settings the kernel hard-crashes building a fresh 16k-deep chain in one pass, a wall the big run would hit near depth 10⁴.

3  Numbering every symbolic system

To enumerate symbolic systems efficiently you need what the book never gives them: a rule number. The indexing is built on Szudzik’s elegant pairing function (NKS 2006) — pair(x,y) = y²+x if x<y, else x²+x+y — a bijection whose inverse needs one integer square root, and which fills square shells:

Expressions number recursively (atoms first, then f[a] = unpair(n−A)), making the enumeration depth-ordered and downward closed. A system is pair(lhs_id, rhs_id) over {e, x, y, z}, with a restricted-growth condition giving each rule exactly one id. The paper’s own fixtures anchor it — Cantor order really does put s[s][s][s] at number 741 — and a closed-form Catalan–Stirling count cross-validates the id scan through every class up to (4,4). The p. 102 rule is system 7432.

Walking the enumeration, concretely

Decode the first ids and the depth shells fill in order — everything of height h before anything of height h+1:

System ids stream the same way — identities flagged, α-duplicates silently absent:

$ nks-symbolic enumerate --from 0 --to 40 --list
0     1+1   id   e -> e
2     1+1   -    _ -> e
3     1+1   id   x_ -> x
16    1+2   -    e -> e[e]
17    1+2   -    _ -> e[e]
20    2+1   -    e[e] -> e
24    2+2   id   e[e] -> e[e]
26    1+2   -    x_ -> e[x]
30    2+1   -    e[_] -> e
31    2+1   -    e[x_] -> x
34    2+2   -    e[_] -> e[e]
35    2+2   id   e[x_] -> e[x]
37    1+2   -    x_ -> x[e]
ids 0..40: 40 scanned, 13 canonical systems (4 identity)

$ nks-symbolic id decode --kind rule 7432
e[x_][y_] -> x[x[y]]
lhs_id 36  rhs_id 86  leaves 3+3  vars 2  identity false

And here is the enumeration behaving — every canonical non-identity system among the first forty-odd ids, run from the book’s initial condition, with the p. 102 rule closing the set from id 7432:

Sweeping the space is then just an id range. Every system with both sides of height ≤ 3 — ids 0…163,215 — classifies in 3.3 seconds: 11,713 canonical systems; 10,868 fix, 49 go periodic, 331 outgrow the cap, 465 run on irregularly (specimens like 14462, x_[x_][y_] → y[e][x[e]], wander aperiodically). The book’s taxonomy, as a histogram:

The p. 104 figure itself is reproduced too. Its six rules exist only in the page image, so they were transcribed from magnified crops of the 1588-pixel scan and validated by running them: the regenerated panels match the printed morphologies, and the maximum size-differences (48, 25, 8, 1260, 1802, 483) land on the printed plot axes (≈40, 30, 6, 1500, 2000, 400).

4  The combinator corpus, exhaustively

The densest published dataset is the combinator-properties note (p. 1122): a behavioral census of SK expressions by size, under exactly the §3.10 step. Every number reproduces — and the full census sharpens what the book sampled:

The size-8 sweep takes 0.75 s and turns “it appears that 49 show exponential growth” into a hard census — including a find the note doesn’t mention: its period-3 case has a sibling, s[s][s][s[s]][s][s[k]], also period 3. Trajectory details land exactly: the “7050” is the repeating cycle’s maximum (the transient peaks at 8156); the 1263→17 case fixes at step 97 under the same convention as p. 103; the two size-7 growers hit Depth 14 at steps 26 and 25 and stay.

The single-combinator system of note p. 1123 got the treatment its minimality claim invites: all 1,033,412 single-symbol expressions of sizes 1–14, swept. Sizes ≤13 all fix; at size 14 exactly three grow — the two s→j[j] translations of the SK growers plus the book’s verbatim third. The book asserted; the sweep proves it in five minutes.

5  The universality bridge

The later chapters — nearly missed, recovered by a reader’s instinct that more material existed — carry the book’s universality argument over two constructions. Both run.

Symbolic systems emulate cellular automata (note p. 1113): ten rules — eight transcribing the CA table over {p, q} = {0, 1}, two sweeping the tape — with the exact correspondence CA step t = symbolic step t(t+n+3). States at aligned steps decode literally:

Combinators emulate rule 110 (notes pp. 1121–1122; the p. 713 figure). Each ingredient was rebuilt and verified in sequence — the ToC abstraction algorithm, Church numerals, the generic cell-update combinator (size 61 for rule 90, as printed), the verbatim size-16 rule-90 combinator, pair-encoded cell lists — then w, the one-full-step combinator, transcribed from the note’s deeply nested text: 674 leaves, and repeatedly applying it reproduces rule 110 row by row, at a cost matching the note’s “roughly (100+35n)t + 33t²”:

rule 110: w size 674 leaves; 1155 passes for t=3, n=7   (note's rough formula: 1332)
rule  90: w size 672 leaves; 1155 passes for t=3, n=7   (note's rough formula: 1332)

6  The figures themselves

Matching the book’s aesthetics was its own small reverse-engineering job: the original page scans, magnified, dictated italic serif on a character grid, white-filled near-square boxes over opaque outlined gray bands, no step numbers, and a rule icon that is itself a variable-flow diagram. The generator reproduces all of it for any system — then goes one step past the book’s grayscale:

7  What remains

The honest remainder, none of it load-bearing: the inner-part depth pattern and steps-to-fix bound of note (e); the tree-form and Polish-notation representations (notes h, c); the h[t] size-formula case at combinator size 8; a growth-rate fitter to reconcile the book’s eyeballed “≈49 exponential” with our hard 70-system census; the operator-algebra translation (p. 1172); the confluent-emulation variant (note 9.11). Each is a bounded afternoon.

Appendix A — the reproduction ledger

Appendix B — the crate

CLI: run (summary | exprs | sizes | brackets | matches), reduce, id encode/decode, enumerate, survey rules|inits. examples/p102.rs replays the book checks; examples/trace_svg.rs draws every trace figure here; docs/fig_*.py regenerate the rest.

Appendix C — implementation notes

• Iterative everything. No engine path recurses on expression depth — scan, equality, printing, hashing, the invariant fold, and a worklist Drop. Recursion survives only where input size bounds it.
• Sharing is the asymptotic edge. Persistent trees make RHS duplication O(1), let successive states share structure, and make fixed-point checks effectively free via cached hashes — precisely where the m²-vs-m³ gap against the kernel comes from.
• Pre-order indices as coordinates. Tracing reports matches as pre-order positions, skipping matched interiors arithmetically (2n−1 nodes); a parallel walk pairs each match with its replacement. Order preservation means connector bands never cross.
• Checked u128 ids; saturating leaf counts — sizes can grow as power towers (note (g)).
• Fixture discipline. Every golden constant traces to the book’s text, a kernel evaluation made before the code existed, or a deterministic run cross-checked against an independent book number. The differential fuzzer keeps all three honest.
• Figures. One glyph per character cell keeps italic serif on the layout grid; bands beneath paper-filled boxes, as the original scans dictate; raster-heavy panels flatten to PNG because strict viewers strip data-URIs nested inside SVG.
• Operational scars. One wolframscript per license seat; kernel tests run serially; a crashed kernel reports as a “license error” and parks its seat for a minute. Heavy sweeps live behind --ignored.

The nks-symbolic repository · sources: wolframscience.com/nks (§3.10 pp. 102–104 and notes; notes pp. 1113, 1121–1123, 1145, 1172; main text pp. 711–714) and szudzik.com/ElegantPairing.pdf.