Agency Requires Coarse-Graining: The Optimal Projection Cannot Be Uniformly Derived

You can't algorithmically find the best way to simplify yourself — and this paper proves it.

Any agent that persists over time — a cell, a brain, a robot — doesn't regulate its behavior from a full microscopic description of itself. It works from a compressed summary: a self-model plus the world variables that matter for staying alive. The question this paper asks is sharp: can you always compute the best such summary? Not just any useful one, but the shortest description that still captures everything relevant to the agent's survival target. The answer is no, and the proof is tight.

The paper first establishes that a bounded, "good enough" regulatory summary always exists for any persisting agent — this follows from earlier BCOM results showing that persisters already carry a compact self-code. So the problem isn't vacuous. The interesting move is what comes next: proving that no single algorithm can take an arbitrary agent's microdescription and return the optimal compressed summary. The proof works by reduction. The authors define a "targeted Kolmogorov structure function" — essentially, the best model of bounded complexity that preserves all information about a specific target — and show that computing it is as hard as the halting problem. The special case where the target is the agent's own persistence variables is exactly the regulatory coarse-graining problem. So optimal regulatory compression inherits the same uncomputability.

Two theorems do the work. Theorem A says there's no uniform procedure that returns a near-minimal regulation-sufficient projection across the full class of agents — hard instances exist even in recursively enumerable families. Theorem B is cleaner: it proves the targeted sufficient projection is uncomputable in the abstract, then reads off the regulatory consequence as a corollary. This ordering matters — the authors are careful not to smuggle the conclusion into the definition of "regulation." A concrete bonus result (Corollary C1) says the optimal Markov blanket — the boundary between agent and world — is also uncomputable and generically non-unique, which formally grounds an earlier BCOM conjecture about boundary fuzziness.

The paper is careful about what it doesn't claim. Uncomputability here is uniform and worst-case: it rules out one algorithm that works for all agents, not computation in specific structured cases. Good-enough projections can still be found by evolution, learning, development, culture, or direct computation when the problem has exploitable structure. The "crack points" of the targeted structure function — where a small increase in model complexity buys a large drop in residual uncertainty — are natural targets for such open-ended search, even without a universal stopping certificate. The core claim is precise: agency requires coarse-graining, and optimal regulatory coarse-graining is not uniformly derivable. Anderson's "More is Different" intuition, now with a theorem underneath it.