Research results · autonomous run · 8 August 2026
A function’s complexity as its distance from a constant.
Not a program that computes f(x). A sequence of overwrites, each one naming a subset of the
input domain using structure the type already provides, and repainting the function’s value there.
Complexity is the cheapest such sequence, in bits. Learning is picking the cheapest one consistent with the data.
The whole domain, repainted rule by rule
19 683 fields — one pixel each. Hover to inspect. Recomputed live.
Layout is the field index in base 3: horizontal position encodes cells 1–5, vertical position cells 6–9.
The self-similar texture is the type Field = Coor² → Cell.
The brief
A deliberately non-standard notion of complexity
The task set one hard constraint: do not turn this into program synthesis. The object whose complexity matters is the extensional function itself, the value table, and a description is a sequence of structurally defined transformations that turns a constant function into that table.
The second constraint was methodological: find the smallest set of mechanisms. If the formalism starts accumulating auxiliary states, special cases and bookkeeping, that is evidence the abstraction has not been found yet. Singletons, orbits, multiplicity classes and threshold regions must not be four primitives; they must be four faces of one.
What came back
- Three primitives: a structured domain, a priced subset description, one overwrite. Everything else is derived.
- A reduction that turns minimising a certificate into a shortest path in a small lattice, and never touches the 4^19683-vertex function graph. Verified against brute force.
- Exact optima for all 256 functions on two 8-point domains, so heuristics can be scored against truth, not against each other.
- An incremental learner that reaches the true optimum on 92% of them, and recovers tic-tac-toe from a quarter of its table.
- Two honest failures, reported below rather than buried: a rare-class accident, and a cost model that is only an upper bound on the intended one.
Deliverable A
Three primitives
Everything in the project is one of these, or is derived from them.
P1
Structured domain
A finite set presented by a type expression over bare sets with +, ×,
→. The expression induces an automorphism group and a family of derived maps
q : X → V into structured value spaces.
P2
Priced subset description
A walk through a prefix-free choice tree; each node charges log₂(#options). The subset is a fiber of a tupled derived map. Descriptions are syntax; subsets are semantics; equal extensions collapse to the cheapest description.
P3
Overwrite
The single transformation.
TS,y(g)(x) = y if x ∈ S
= g(x) otherwise
Structure generating structure
The interesting question was never “what is a subset” but “what makes a subset cheap”. Four canonical operations generate the whole map family, and the fourth is just “do it again to what you got” — which is where the higher-order structure the brief was hunting for actually comes from.
The cost model
Every atom is priced by the choices its derivation makes. Nothing else is charged.
With |Y| = 4 the constant start costs 3 bits and every rule pays 3 bits of overhead. Everything above that is structure you had to name.
Where the bits go
pick an atom familyFact 1 — the singleton is not an exception
A single point is the fiber of the tupled evaluation map over all nine of its cell values: nine choices, full price. There is no “change one point” primitive; there is only structural specification, continued until nothing is left to share. Universality follows for free, and complexity degrades smoothly to the cost of writing the table out, which is exactly what the tiny-domain experiments measure.
Fact 2 — the settled-set reduction
Later overwrites win, so only the last write at each point matters. Read a certificate backwards: rule i settles the points of Sᵢ that no later rule touches, and f must equal yᵢ there. So:
This is the discrete geometry the brief was reaching for. The naive picture (functions as vertices, overwrites as weighted edges) is correct; the test suite confirms it by brute force on a micro-domain. It is just useless directly. The reduction replaces it with a graph that never mentions intermediate extensions at all.
Instrument
Take a field apart
Click cells to cycle empty → X → O. Everything on the right is derived from the type, then fed to the learned certificate, by the same code path the experiment used, re-implemented here and checked against it.
- field index
- 0
- counts (X,O,·)
- 0, 0, 9
- #X − #O
- 0
- N₍₃,₀,₀₎ · N₍₀,₃,₀₎
- 0 · 0
- line profiles
Rules apply top to bottom and the last match wins. That is the whole semantics. It is also why the learned simple certificate is cheaper than the hand-written one in the brief: Draw needs no “and no winning line” clause, because the two win-rules overwrite it afterwards.
Deliverable E
What was learned, and what it cost
Two targets. simple is the extension of the hand-written certificate in the brief. legal is the stricter reachable-terminal classification; its class sizes reproduce the known 626 / 316 / 16 counts exactly, which is a real check on the implementation, not a formatting choice.
START: everything → Illegal [ 3.00 bits] OVERWRITE #Empty=0 → Draw [ 12.81 bits, |S|=512] OVERWRITE N(0,3,0)≥1 → OWon [ 14.40 bits, |S|=4435] OVERWRITE N(3,0,0)≥1 → XWon [ 14.40 bits, |S|=4435] ────────────────────────────────────────────── TOTAL 44.61 bits, 3 rules · 100.00% on 14 809 unseen
START: everything → Illegal [ 3.00 bits] OVERWRITE #X−#O=1 & N(0,3,0)=0 & N(3,0,0)≥1 → XWon [ 36.95 bits, |S|=626] OVERWRITE #X−#O=0 & N(3,0,0)=0 & N(0,3,0)=1 → OWon [ 36.95 bits, |S|=316] OVERWRITE N(1,2,0)≥4 & N(2,1,0)≥3 → Draw [ 25.80 bits, |S|=44] ────────────────────────────────────────────── TOTAL 102.70 bits, 3 rules · 99.65% on 14 729 unseen
Verified here, in your browser
The table is not copied from the run log. This page enumerates all 19 683 fields, recomputes both targets and both certificates from the definitions, and fills the numbers in. If the reimplementation disagreed with the reported run, you would see it.
| Rule | Bits | |S| computed | |S| reported | Points it settles | Semantically exact? |
|---|
Prediction quality against the alternatives
| Method | Model bits | Test accuracy | Notes |
|---|---|---|---|
| Learned certificate (legal) | 102.7 | 99.65% | 3 rules; X and O rules exact |
| Learned certificate (simple) | 44.6 | 100.00% | 0 errors of 14 809 |
| Memorise the training labels | 9 908 | — | predicts nothing off-sample |
| Majority class | ~2 | 95.12% | the bar a rare-class problem sets |
| 1-nearest neighbour, Hamming on cells | 5 000 rows | 94.30% | below majority; metric locality is the wrong bias here |
| Random labels, n=1 000 | 938 | 86.00% | below majority; every accidental rule that fires off-sample is wrong |
1-NN losing to the majority class is worth a second look: it is not a broken baseline, it is the point. Two fields one cell apart routinely have different labels, so distance in cell-space carries almost no signal. The structural language is not competing on data efficiency. It is competing on having the right notion of nearby.
The core claim
Natural functions get short certificates. Random ones do not.
The brief was explicit that high accuracy is not the interesting outcome. The interesting outcome is an asymmetry: the intended function compresses dramatically, and a random labelling of the same domain, through the same language and the same learner, does not. If random labels got short certificates, the coding scheme would be leaking information.
| Run | n | Raw repairs | Raw bits | Recompressed | Rules | Bits / example | Test acc. |
|---|
The raw column is the certificate before recompression: one rule per repair, hundreds of bits. Almost all of the compression is done by the local moves, not by the incremental pass, which is the argument for keeping both.
Deliverable C
Ground truth on domains small enough to solve
Before tic-tac-toe: two 8-point domains where the true minimum certificate can be computed for every one of the 256 boolean functions by exhaustive Dijkstra over settled sets. This is what makes the rest of the project falsifiable: the incremental learner is scored against optimality, not against another heuristic.
Selected function
Its provably optimal certificate on T1
Cost
Three sanity results that had to hold
- Reduction is exact. On a micro-domain the settled-set optimum equals brute-force Dijkstra over all |Y|^|X| functions, for every target. The compression of the geometry loses nothing.
- No leakage. Random functions land near the median and the worst function sits at extensional cost. A prefix-free code cannot compress noise, and empirically it does not.
- Planted certificates. For 200 random 2-rule certificates the exact optimum is ≤ the planted cost in 100% of cases.
The named cases
| Function | T1 | T1′ | Optimal description |
|---|---|---|---|
| constant | 2.00 | 2.00 | no rules |
| dictator x[0] | 8.58 | 8.58 | one evaluation fiber |
| majority | 10.58 | 24.92 | a threshold on a count |
| singleton {aaa} | 10.58 | 15.75 | it is the count-fiber #a=3 |
| singleton {aab} | 15.17 | 15.75 | x[2]=b & #a=2 — successive refinement |
| parity | 19.17 | 31.51 | two count fibers |
| worst case | 28.34 | 29.51 | ≈ writing the table out |
The two singletons are the argument in miniature. {aaa} is symmetric, so it is already a count fiber and costs the same as majority. {aab} is not, and has to be refined into place at full price. Same mechanism, different residual symmetry.
Deliverable D
Repair is the right shape. It is not sufficient alone.
The brief’s main algorithmic hypothesis was that a wrong prediction should trigger a small local search: the cheapest describable subset containing the offending point that contradicts nothing already seen, rather than resynthesis. That held. What it needed on top was a set of moves that undo choices.
The finding that mattered
The moves that repair a certificate are edits of the choice tree that prices it. Adding an atom is making one more choice; removing one, or replacing it with something broader, is undoing a choice. Lifting prof[row1]=(3,0,0) to N₍₃,₀,₀₎ ≥ 1 literally forgets which line. That is what generalisation is here. The search never manipulates syntax trees; it walks the cost structure itself, and semantically equal descriptions collapse because everything is memoised by extension.
And the global greedy baseline (cost-effectiveness covering, the textbook move) is worse than incremental repair (9% optimal vs 43%). It commits early to large rules that force expensive later patches. That is direct evidence for the brief’s hypothesis about the shape of the search.
The four local moves
- prune — drop a rule whose removal keeps the certificate consistent. Principled.
- broaden — delete a choice point from a description, then re-specialise minimally if the broader rule now claims points of another class. Principled: it is the ∃-lift along a structural family.
- merge — replace several same-output rules by one, found by the same search with “must contain a point” generalised to “must contain a set”. Added during the project, in response to a failure; improved every configuration.
- replay — re-run on a reordered stream. Honestly labelled as engineering, not theory. That it still contributes means the local move set is incomplete.
When greedy repair fails
Two characteristic failures, both named and measured:
- Tiling — a run of individually-cheapest medium subsets where one general rule plus exceptions was cheaper.
- Order traps — an early cheap rule that forces expensive later patches.
Roughly 40% of tiny functions need some recompression; about 8% are still not optimal even with the best of ten presentation orders. Order dependence is the residual, and it is reported rather than averaged away.
The honest part
Where it breaks: a 25.8-bit accident
On the legal target there are only 16 draws in 19 683 fields, and orbit sampling shows the learner just 4 of them. The cheapest rule consistent with those four is not the correct one. It is this:
“At least four lines with one X and two O’s, and at least three with two X’s and one O.” It is true of every draw it was shown, and of nothing else it was shown, so it is admissible, and it is cheap. It is also true of 44 fields in total, of which only the 4 observed draws are draws; it overwrites 16 genuine X-wins and relabels 24 illegal positions, and it misses all 12 draws it never saw. The correct rule (#Empty=0 & N₍₃,₀,₀₎=0 & N₍₀,₃,₀₎=0 & #X−#O=1) costs about 46 bits. With four examples, MDL is right to prefer the accident.
The accident’s extension, computed live
every field the rule fires onThe 44 fields it claims — coloured by what they actually are
The 16 real draws — how many does it catch?
This is a data-adequacy failure, not a coding leak
The distinction matters and the project makes it carefully. A coding leak would mean the language can compress arbitrary labellings, and the random control rules that out. What happened instead is that the observations do not yet falsify the cheap wrong rule. The prediction is quantitative: the accident should die when enough draws are seen that patching it costs more than the ~20-bit gap it enjoys.
The failure produced the missing move
An intermediate version made things worse when shown more draws: it stacked a second accidental Draw rule that overwrote 60 real X-wins, dropping XWon accuracy to 87.3%. Two accidents now cost more than one correct rule: the global optimum had flipped, but no local move could reach it. Repair proposes a rule for one point; broaden edits one rule. Nothing could propose one rule for two rules’ worth of responsibility. That gap is exactly the merge move, which was then implemented.
With merge, the same run gives 110.5 bits at 99.82% with X and O rules perfect, and the Draw rule becomes the partly-semantic cell(1,1)=O & #X−#Empty≥5 & N₍₃,₀,₀₎=0 — “full board, no X line, O in the centre”. Still an accident. Still, given the data, the right call.
Per-class accuracy across every configuration
| Target / sampling | Train n | Draws seen | Bits | Illegal | XWon | OWon | Draw | Overall |
|---|---|---|---|---|---|---|---|---|
| simple / orbit | 4 874 | 16 | 44.6 | 100% | 100% | 100% | 100% | 100.00% |
| simple / iid | 5 000 | 7 | 78.8 | 100% | 100% | 100% | 100% | 100.00% |
| legal / orbit | 4 954 | 4 | 102.7 | 99.83% | 96.60% | 100% | 0% | 99.65% |
| legal / iid | 5 000 | 1 | 100.9 | 99.99% | 100% | 100% | 20% | 99.91% |
| legal / orbit+rare (with merge) | 4 958 | 8 | 110.5 | 99.87% | 100% | 100% | 0% | 99.82% |
Note the trade in the last row: showing more draws makes the certificate more expensive and the X rule perfect. Accuracy on the rare class stays at zero because eight examples still are not enough to price the correct rule below the accident. That is the model working as specified, not an implementation bug.
Positioning
What the neighbours actually optimise
The survey holds one discriminator throughout: what is the primitive object each line of work minimises? That is the question that separates this construction from ordinary program synthesis, and it is the question the brief asked for.
| Field | Primitive object it optimises | Relation |
|---|---|---|
| MDL rule lists (Proença & van Leeuwen; RIPPER; CN2) | ordered (predicate, output) list, first-match-wins | Closest existing formalisation. A last-write-wins certificate is a decision list read backwards. But the subset language is arbitrary Boolean conjunctions over given attributes, with no type-derived structure, no symmetry pricing. |
| Kolmogorov structure function (Vereshchagin & Vitányi; Gács–Tromp–Vitányi) | two-part code: a set containing the data + the residual | The deepest formal ancestor of the trade-off. This project is an effective, finite, typed specialisation of it. The no-leakage requirement is exactly Kraft validity. |
| Stabilizer chains & canonical forms (Sims; McKay, nauty) | coset indices; canonical representatives | Structurally the closest match to the cost mechanism: coset indices are literally the “#choices” whose log is charged. The gap: that literature never treats them as description length inside a learning objective. |
| Program synthesis with library learning (DreamCoder, FlashFill) | a DSL program tree computing f(x) | Precisely the framing the brief ruled out. Nothing found in this cluster optimises edit sequences on an extension. |
| Version spaces (Mitchell; Hirsh) | the set of consistent hypotheses, via S/G boundaries | The classical analogue of “a correctly predicted example still shrinks the space”. Here the version space is not stored; it is an admissibility predicate derived from two bitmasks on demand. |
| Transformation monoids (Krohn–Rhodes; Even & Goldreich) | shortest generator word for a monoid element | κ(f) is a weighted word metric in the monoid generated by overwrites. No prior framing found of function complexity as shortest word from a constant function with bit-weighted generators. |
| Species & association schemes (Joyal; Bannai & Ito) | equivariant functors; orbit-defined relation algebras | The right language for the derived-map family, and it grounds “structure generates structure” as functor composition, but it supplied no mechanism the project didn’t already need. |
| Theory revision (FORTE; FRINGE; Wrobel) | a logical theory hill-climbed by typed edit operators | The closest behavioural match to incremental repair. Heuristic, no bit accounting, edits act on syntax rather than on semantically deduplicated subsets. |
Finding. No located prior work treats function complexity as weighted edit distance from a constant function, via edits on type-canonical structural subsets with explicit log₂(#choices) costing, combined with incremental MDL repair. The three nearest anchors above are each missing a different one of the three ingredients. The synthesis appears to be new, stated as a search result, with the searches listed, not as a claim of priority.
Limits
What is still wrong, in the author’s own account
Flat pricing is an upper bound
Choosing one cell of nine costs log₂9 regardless of how much symmetry remains. The intended scheme prices each choice by the alternatives inequivalent under the stabiliser of the choices already made — two-part orbit coding. A corner among the three cell-orbits: log₂3 + log₂4 ≈ 3.58 flat-priced at 3.17, but a corner followed by a symmetric continuation should cost only log₂3.
Flat pricing keeps the code prefix-free (Kraft mass ≤ 1 per family, tested), so nothing leaks. It just overprices highly symmetric subsets. Specified, not implemented.
The unification is not complete
The hoped-for single object holding prediction, constraints and allowed modifications was found only partially. The settled-set chain unifies the certificate with its own search space, and admissibility derives the version space from the observations, but the observations themselves stay a plain partial function.
The honest formulation: the learner state is a pair of partial functions of the same kind, one compressed and one extensional. Nothing forbids compressing the second by the same machinery; no way was found to merge them without losing what was actually observed.
The five experiments that would most reduce uncertainty
| # | Experiment | What it would settle |
|---|---|---|
| 1 | Stabiliser-refined pricing — implement the two-part orbit code with Schreier–Sims machinery | The single most theory-relevant unknown. Prediction: general rules get relatively cheaper, so raw repair becomes less myopic and leans less on broadening. |
| 2 | Exact optima at tic-tac-toe scale — A*/branch-and-bound on the settled-set lattice with the 523-atom library | κ(legal) is currently bounded from one side only: ≤ 102.7 bits given the library. The true gap of the incremental learner on a real domain is unmeasured. |
| 3 | Rare-class economics — sweep draw coverage and find where the correct rule overtakes the accident | A clean quantitative prediction of the MDL account: the accident should die when patching it costs more than the ~20-bit gap it enjoys. |
| 4 | A second type — 4×4 boards, or Coor replaced by a bare 3-set, which changes the derivable line family | Confirms the structure-dependence result at scale rather than on 8 points. |
| 5 | Reuse discounts over a corpus — one function’s certificate making structures cheap for the next | Library learning at the level of derived maps rather than programs. Specified in the formalism; single-function experiments gave it nothing to bite on. |
The method, stated as a method
The merge move was not designed in advance. It was found by localising a failure (a configuration where more data made the result worse), naming the move that was missing, implementing it, and re-running everything. The project recommends that loop explicitly, and item 1 above is the next place to point it. That is a more useful deliverable than any single number on this page.
Primary sources
Read the actual documents
Nothing here is a substitute for them. Everything on this page is drawn from these files.