# Structural description complexity and incremental learning by extensional transformations

Research prototype for the program laid out in `prompt.md`: the complexity of a
finite extensional function `f : X → Y` is defined as the minimum bit-cost of a
sequence of *overwrite transformations* `T_{S,y}` that turns a constant
function into `f`, where each subset `S` is specified using structure
canonically induced by the *type* of `X`, and learning from partial data is
outer-level MDL over such certificates, performed incrementally by cheapest
local repair.

## Documents

| file | content |
|---|---|
| `formalism.md` | Deliverable A — the minimal formalism (3 primitives), the settled-set reduction, the induced discrete geometry |
| `memo.md` | Deliverable F — research memo: what unified, what failed, experimental findings, answers to the 20 questions of `prompt.md` §16 |
| `literature.md` | Literature survey with the primitive-object comparison the task asks for |
| `results/` | JSON outputs and logs of all experiments |

## Code

| file | content |
|---|---|
| `src/certlang/core.py` | Atoms, subset descriptions and their bit costs, certificates (overwrite sequences), exact optimum via backward Dijkstra over settled sets, cheapest-admissible-subset repair search, incremental learner, prune / replay / broaden recompression, global greedy baseline |
| `src/certlang/domains.py` | Tiny structured domains `V^P` (P a sum of bare blocks) for exhaustive experiments |
| `src/certlang/tictactoe.py` | The tic-tac-toe type, its derived structure (counts, line family, line profiles, profile counts, count comparisons), targets, D4 orbits, orbit-stratified sampling |
| `experiments/exp_tiny.py` | Deliverable C/D — exact optima for all 256 functions on two 8-point domains; incremental vs exact; structure dependence; planted certificates |
| `experiments/exp_ttt.py` | Deliverable E — full 19683-field experiment: learning from ~25% of fields, baselines, random-label control, train-size sweep |
| `tests/test_core.py` | Invariants, incl. equality of the settled-set reduction with brute-force search over the full function graph |

## Run

```bash
python3 tests/test_core.py          # ~2 s
python3 experiments/exp_tiny.py     # ~1 s
python3 experiments/exp_ttt.py      # ~5-10 min (numpy required)
```

## Headline results

- **Exact tiny domains** (`|X|=8`, all 256 functions, true optima by exhaustive
  settled-set Dijkstra): S3-symmetric functions cost ~11.4 bits on average vs
  ~20.3 for arbitrary ones; the same 256 extensions cost +3.0 bits on average
  when the domain's type has less symmetry; random functions approach
  extensional cost (no leakage — the coding is prefix-free by construction).
- **Incremental repair** with recompression (prune + replay + structural
  broadening + merge) reaches the true optimum on 92% of all functions (best
  of 10 presentation orders; 60% for a single order), mean overhead < 1%.
- **Tic-tac-toe** (learn from ~4950 of 19683 fields, predict the rest): the
  task statement's target compresses to a **3-rule, 44.6-bit certificate with
  100.00% accuracy on all 14809 unseen fields** (`Draw if #Empty=0`, then
  `OWon if N(0,3,0)>=1`, then `XWon if N(3,0,0)>=1` — cheaper than the
  hand-written certificate, by exploiting overwrite order); the stricter
  reachable-terminal target compresses to 3 rules / 102.7 bits at 99.65%,
  with the X-rule covering exactly the 626 legal X-wins. Memorizing the
  training labels would cost ~10000 bits. A random-labeling control stays
  near-incompressible (~0.9 bits/example, growing linearly) and generalizes
  below the majority-class baseline.