R12 MDL Identifiability No-Go

Status: rejected as an R12 invention. Description length supplies a valid average-risk regularizer after a representation language is fixed; it does not identify the intended extrapolating program from finite unrestricted traces.

1. Candidate

The candidate was to select the shortest program consistent with a finite set of generator examples and relations, expecting the compact causal rule to beat memorization and therefore extrapolate to arbitrary compositions.

Let U be a prefix universal machine and K_U(p) the code length of program p. For a finite dataset D, idealized MDL chooses a minimum-length program whose predictions agree with D.

2. Exact characteristic-set condition

Let p_star be the intended total target program. A finite dataset D identifies p_star by MDL only if every total program q with

K_U(q) <= K_U(p_star)

that is not extensionally equivalent to p_star disagrees with D. Ties need an additional deterministic rule or strict inequality. This condition is both necessary and sufficient for exact off-sample identification inside the declared program class.

It is not an explanation of extrapolation. It says that D must already be a characteristic teaching set against every shorter incorrect program. Finding or certifying that set carries the full identifiability burden.

3. What survives: an average-risk Occam bound

For iid examples from distribution mu, prefix coding and a union bound imply that every zero-training-error program p simultaneously satisfies, with probability at least 1-delta,

R_mu(p) <= (K_U(p) ln 2 + ln(1/delta)) / n.

Standard noisy versions replace this realizable bound by an empirical-risk term plus a square-root complexity penalty. This is useful regularization and belongs in matched controls. It is a distributional risk statement, not a guarantee on adversarially held-out compositions or arbitrary late queries.

4. Four no-go attacks

4.1 Finite off-support patch

For every finite D, an incorrect program can agree on D and differ at the first untested input. No finite consistency objective distinguishes them without a restricted program class or a characteristic set.

4.2 Delayed sabotage is cheap

A program can run the target until composition length L and then fail. It needs only the target code plus a counter and a self-delimiting description of L, an overhead O(log L). Testing longer finite horizons does not create a qualitative simplicity separation.

4.3 Universal-machine dependence

Kolmogorov complexity is invariant only up to a machine-dependent additive constant. A perverse but universal reference machine can assign a one-bit code to a chosen malicious extrapolator. At the tiny description differences at issue, the representation language is a substantive prior, not a neutral law.

4.4 Ideal selection is uncomputable

Finding the shortest total program consistent with arbitrary data requires solving program equivalence/totality problems. Delayed failures can be placed beyond any computably chosen finite test horizon. The idealized selector is therefore not an executable training mechanism.

5. Prior-art and resource boundary

The surviving theorem is classical Occam/MDL/PAC-Bayes reasoning. Neural compression, minimum circuit size, program synthesis, and Bayesian priors are valid controls, but each inherits a representation language and a hypothesis class. None supplies the missing ordinary-trace theorem that reveals the right latent causal presentation.

6. Verdict

No CPU falsifier is authorized for unrestricted MDL. A later candidate may use description length only after separately proving:

1. a computable restricted language;
2. a polynomial characteristic set generated without target-specific search;
3. robustness to noise and representation changes;
4. a held-out compositional guarantee stronger than iid average risk.

MDL can rank survivors inside a theorem-backed class. It cannot create that class or prove reasoning by itself.