Open dataset + dependency-free engine for the normalization geometry of the untyped λ-calculus (SN / WN / separators), built around the open Barendregt–Geuvers–Klop conjecture. Smallest closed WN-but-not-SN term = natural size 13; closed-term counts
  • JavaScript 45%
  • Python 27.4%
  • CSS 20.3%
  • HTML 7.3%
Find a file
Repository files (latest commit first)
Filename Latest commit message Latest commit date
Peter Lodri 9511298b1d add Croissant JSON metadata and cosign artifact signing workflow
croissant.json: ML Croissant 1.0 (JSON-LD) dataset card for the census,
describing all distribution files and the full RecordSet schema for
census_dataset.csv so dataset search tools can index it automatically.

sign-artifacts.yml: keyless cosign signing via GitHub Actions OIDC.
On push to data/autoresearch/*/run_meta.json, finds newly added files,
signs each with cosign sign-blob --bundle, and commits the .sigstore
bundles back to the repo for tamper-evident artifact provenance.
2026-06-11 03:54:10 +02:00
.claude Add project settings: disable commit-signature trailer + safe-default permissions 2026-06-10 18:44:52 +02:00
.github add Croissant JSON metadata and cosign artifact signing workflow 2026-06-11 03:54:10 +02:00
data chore: add Frictionless Data datapackage for autoresearch dataset 2026-06-10 22:41:02 +02:00
docs census: extend to n=55 (MC tail), trim plan for reproducibility, decidability-horizon note; sync report data 2026-06-10 17:09:04 +02:00
report pages: restore Actions deploy of report/ (lost in history rewrite) + legacy /report/* redirect via 404 page 2026-06-10 18:47:54 +02:00
src census: extend to n=55 (MC tail), trim plan for reproducibility, decidability-horizon note; sync report data 2026-06-10 17:09:04 +02:00
.gitignore chore: neutralize gitignore comment 2026-06-10 18:51:41 +02:00
.nojekyll Canonical MIT LICENSE (fix GitHub detection); add .nojekyll for Pages 2026-06-10 16:50:10 +02:00
BACKERS.md Community health (CoC, SECURITY, SUPPORT, ROADMAP, BACKERS, CI, issue/PR templates) + README badge row 2026-06-10 17:56:26 +02:00
CITATION.cff λ-normalization census: open dataset, dependency-free engine, BGK conservation lab, interactive report 2026-06-10 16:48:38 +02:00
CODE_OF_CONDUCT.md Community health (CoC, SECURITY, SUPPORT, ROADMAP, BACKERS, CI, issue/PR templates) + README badge row 2026-06-10 17:56:26 +02:00
CONTRIBUTING.md λ-normalization census: open dataset, dependency-free engine, BGK conservation lab, interactive report 2026-06-10 16:48:38 +02:00
croissant.json add Croissant JSON metadata and cosign artifact signing workflow 2026-06-11 03:54:10 +02:00
LICENSE Canonical MIT LICENSE (fix GitHub detection); add .nojekyll for Pages 2026-06-10 16:50:10 +02:00
PRIVACY.md LTS kernel (6.18.35) panel; export Sponsors profile (SPONSORS.md); contact → cabotage@pm.me 2026-06-10 17:42:06 +02:00
README.md README: wire in research.crabcc.app / crabcc.app / peterl.dev; LLM-use disclaimer; clean branch metadata 2026-06-10 18:38:23 +02:00
ROADMAP.md Community health (CoC, SECURITY, SUPPORT, ROADMAP, BACKERS, CI, issue/PR templates) + README badge row 2026-06-10 17:56:26 +02:00
SECURITY.md Community health (CoC, SECURITY, SUPPORT, ROADMAP, BACKERS, CI, issue/PR templates) + README badge row 2026-06-10 17:56:26 +02:00
SPONSORS.md SPONSORS: per-tier welcome messages + webhook/email pipeline note 2026-06-10 19:16:17 +02:00
SUPPORT.md Community health (CoC, SECURITY, SUPPORT, ROADMAP, BACKERS, CI, issue/PR templates) + README badge row 2026-06-10 17:56:26 +02:00
USAGE.md docs: kernel reference → 6.18 LTS 2026-06-10 17:42:41 +02:00

λ-Normalization Census

Code: MIT Data: CC BY 4.0 OEIS A275057 deps: none CI Sponsor Wiki PRs welcome Code of Conduct

A reproducible open dataset + engine for the normalization geometry of the untyped λ-calculus, built around the open Barendregt–Geuvers–Klop (BGK) conjecture (does weak normalization imply strong normalization in pure type systems?).

We classify λ-terms as SN (strongly normalizing), separator (weakly normalizing but not strongly — the "WN∖SN gap"), or non-WN, by exhaustive enumeration and Monte-Carlo sampling, and we tabulate quantities that — as far as the literature shows — were previously unrecorded.

Headline results

  • Smallest closed WN-but-not-SN term has natural size 13: (λa.λb.b) Ω (an erasing function applied to Ω). Apparently undocumented; the WN∖SN gap is not tabulated in the combinatorics-of-λ literature.
  • The separator-density curve (WN∖SN fraction vs term size) — measured here, plotted in the report — appears to be new.
  • Model validated: our closed-term count sequence is exactly OEIS A275057 (Lescanne 2016, natural-size de Bruijn).
  • Consistent with theory, honestly framed: Bendkowski–Grygiel–Lescanne–Zaionc (2017) prove SN-density → 0 in this model; our decided-SN stays ≥ 99% because the non-SN mass hides in a growing undecided tail (a "decidability horizon"). This is the opposite of David et al. (2013), whose size convention (variables cost 0) gives SN-density → 1.
  • BGK conservation lab (companion): exhaustive check that the erasure-free λI fragment has 0 separators across 3.13 M terms, the perpetual-strategy law (diverges ⟺ ¬SN) holds with 0 violations / 762 k, and Klop's ι-translation transfer SN(M) ⟺ SN(ι(M)) holds with 0 violations / 711 k.

Repository layout

src/                 pure-stdlib Python engine (no dependencies)
  bgk_lab.py           reduction-graph analyzer (SN/WN deciders, perpetual strategy, ι-translation) + BGK experiments
  debruijn_census.py   natural-size de Bruijn counter + uniform sampler + classifier (the census)
  normalize_check.py   standalone β-reduction sanity checks
  build_census_dataset.py   assembles the open dataset (JSON + CSV) with Wilson CIs
data/                open data
  census_dataset.{json,csv}   per-size SN/SEP/NWN/UND counts, densities, CIs, smallest-separator witness
  bgk_lab_results.json        full BGK lab run (7 experiments)
  crabcc_kernel_index.json    bonus: crabcc symbol-index stats of Linux 6.18 LTS
docs/                research notes (fully cited)
  normalization-census.md
  bgk-conjecture-deep-dive.md
report/              self-contained interactive report (open report/index.html)

Reproduce

No dependencies — just Python 3.9+ (standard library only).

# the normalization census (exact n≤16, Monte-Carlo to n=55) — writes JSON to stdout
python3 src/debruijn_census.py census > my_census.json

# rebuild the open dataset (JSON + CSV) from a run
python3 src/build_census_dataset.py

# the BGK conservation / separator / perpetual / ι-translation lab (arg = seconds/experiment)
python3 src/bgk_lab.py 240   > bgk_results.json

# sanity self-tests (counts vs OEIS A275057, sampler exactness, classifier preview)
python3 src/debruijn_census.py selftest

The census is embarrassingly parallel (multiprocessing); it was run on a 16-core box but scales to any core count.

The dataset

data/census_dataset.csv columns: n, method, total, SN, SEP, NWN, UND, decided, dens_SN_of_total, dens_SN_of_decided, dens_SEP_of_decided, frac_undecided. method is exact (full enumeration, n≤16) or montecarlo (K=50 000 uniform samples). SN = strongly normalizing, SEP = separator (WN∧¬SN), NWN = no normal form, UND = undecided within the engine's bounded reduction-graph caps (node 3000, size 200). Monte-Carlo rows carry Wilson 95% CIs in the JSON.

Interactive report

Live: research.crabcc.app — the research microsite (crabcc design system). Or open report/index.html locally — self-contained (ECharts + Cytoscape + KaTeX vendored, opens offline): the conservation experiments, the separator-density curve, the reduction-graph zoo, and a crabcc × Linux-kernel bonus panel.

Provenance & honesty

This is machine-assisted research: experiments were designed, run, verified, and written up with substantial assistance from large language models (Claude, Gemini, NotebookLM, and DeepSeek), then cross-checked against primary sources (cited in docs/). Every quantitative claim is computed, not asserted. We distinguish proven theorems (cited) from our empirical measurements, and we state the undecided remainder explicitly. The BGK conjecture itself remains open; nothing here resolves it — the experiments corroborate the mechanism (erasure as the obstruction to WN⟹SN).

Citing

See CITATION.cff. Please also cite the primary sources in docs/ (Bendkowski–Grygiel–Lescanne–Zaionc 2017; David et al. 2013; Lescanne / OEIS A275057).

License

Code: MIT. Data & docs: CC BY 4.0.

Acknowledgements

Standing on: Church (1941); Barendregt, Bergstra, Klop, Volken; Sørensen; Geuvers; de Vrijer; David–Grygiel–Kozik–Raffalli–Theyssier–Zaionc; Bendkowski–Grygiel–Lescanne–Zaionc; Lescanne (OEIS A275057). Tooling: crabcc.

Newsletter & privacy

Updates across crabcc, Vaked, and the research — opt-in newsletter + cross-project info at crabcc.app/about. Data practices: PRIVACY.md — minimal collection, no ad trackers, removal on request (cabotage@pm.me).


If this is useful for your work, sponsorship supports continued open compute + data.