In 1972, the condensed-matter physicist Philip W. Anderson published a four-page essay in Science with a title that became a slogan: “More Is Different.” His target was a seductive idea. If the laws of particle physics are fundamental, then perhaps every higher-level science is, in principle, just those laws worked out in sufficient detail.
Anderson accepted reduction but rejected that constructive leap. Knowing the lower-level rules, he argued, does not mean that we can simply reconstruct chemistry, materials, biology, or psychology from them. Half a century later the slogan is famous, but the missing step in the argument has remained surprisingly hard to state.
Our new BCOM working paper, From “More Is Different” to Algorithmic Emergence: Why Compression Is Already Hard, tries to isolate it. The tool is algorithmic information theory. The result is not that higher levels violate microscopic laws. It is almost the opposite: even when the microscopic evolution is completely lawful and easy to generate, discovering a compact higher-level description is a different computational problem.
Running the world is not the same as understanding it
Suppose someone hands you a microscopic update rule, the information selecting a particular realization, and the observation procedure. For a finite experiment you can, in principle, simulate forward and print the resulting record. Call that generation.
Science usually wants something else. Fluid mechanics does not carry the position of every molecule. It keeps fields such as density, velocity, and temperature. Hodgkin and Huxley did not track every ion in a membrane; they found a small set of variables whose equations reproduce the electrical behavior that matters. A useful theory decides what distinctions to keep, what detail can be ignored, and how the retained variables fit together in a reusable model.
This is the paper’s basic separation: determination is not construction. A lower-level description may determine what happens once the realization is fixed. It need not tell a finite observer which variables are worth retaining, whether those variables admit a compact theory, or how to find that theory.
Compression — but compression of what matters
Algorithmic information theory gives an ideal language for the problem. In standard notation, the Kolmogorov complexity K(x) of a finite record x is the length of the shortest halting program that prints it. A million digits of π can look statistically messy while still having a short generating program. Algorithmic complexity asks not how irregular data look, but how short their best description can be.
There is an important scientific twist. A useful theory is not normally a lossless compressor of every microscopic fact. It is a meaningful reusable lossy compression. The observer first chooses a representation ρ that keeps distinctions relevant to the task and discards others; a model M then organizes what remains into variables that can be reused across realizations and tested on new data.
This also prevents a trivial answer. The map that sends every state to zero compresses perfectly and explains nothing. Relevance has to be fixed independently of the compression itself.
Barrier one: a simple law need not make the record simple
Consider a ring of n binary cells. At every tick the whole pattern rotates one place. The rule fits in a sentence. Now observe only the leading cell. After n ticks you have seen every bit of the initial ring, in order.
The instantaneous observation is maximally coarse — one bit out of n — but the history need not be compressed at all. Information hidden at one moment can flow into later observations.
The lesson is simple. A short law does not imply a short realized record. The information may reside in the initial condition, boundary conditions, or whatever selects one realized history from all the possibilities allowed by the law. Before asking whether a theory can be found, we must first ask whether useful compression exists at all.
Barrier two: if compression exists, there is no universal finder
Now suppose we are on the favorable branch: a shorter description really does exist. Can an algorithm that always terminates be guaranteed to find one?
No. If such a procedure existed, we could feed it arbitrary finite strings and use its answer to decide whether a shorter halting program exists. That would solve an undecidable problem related to halting.
There is, however, a positive asymmetry. We can run candidate programs in parallel. If a short one eventually halts and prints the data, we have a finite witness of success. What we do not have is a universal stopping bell telling us when all still-running shorter candidates can safely be abandoned.
no shorter program seen yet ⇏ none exists
Barrier three: even near-optimality has no universal guarantee
Perhaps we should ask for less. Forget finding the very shortest description; can some guaranteed-to-halt method at least stay within a fixed number of bits of the best one?
Again, no. For every total procedure that always returns a valid description, and for every proposed tolerance c, there are compressible records on which an explicit competing program beats the returned description by more than c bits. In the usual classical notation, this says that the procedure’s excess length above K(x) is unbounded.
The relational formulation matters. The theorem need not be read as requiring an observer to possess an exact numerical value of K(x). Its operational content is simply that a shorter competitor can exist — indeed, can be explicitly exhibited in the proof — while no total constructor enjoys a universal bound on how much worse its answer can be.
Where the infinity went
This is also where the result differs from famous examples of undecidability in physics. A finite-tape Turing machine has only finitely many configurations. Run it long enough and it either halts or repeats a configuration, after which its future is periodic. Halting is therefore decidable for the fixed finite machine — perhaps painfully expensive, but decidable.
Physical undecidability results such as the Ising constructions of Gu and collaborators or the spectral-gap theorem of Cubitt, Pérez-García, and Wolf obtain their unbounded computation from an infinite or thermodynamic-limit family. A macroscopic observable, phase, or spectral property is arranged to depend on whether an embedded computation halts. At any fixed finite size, the corresponding mathematical problem becomes computable in principle.
Our construction barriers need no infinite physical system. Every experiment, state space, horizon, and data record in the theorem is finite. The unbounded resource has moved elsewhere: into the space and running time of possible descriptions. Candidate programs are finite strings, but there is no computable bound on how long a short candidate may run before halting.
- No useful compression: the retained record simply contains too much realization-specific information.
- No universal model builder: useful compression exists, but no total procedure is guaranteed to find it or stay uniformly near the best description.
- No computable macro map: a higher-level variable is specified in advance, but its value cannot be computed uniformly from the microscopic description.
- No computable long-run answer inside a known model: the macroscopic update rule itself may be known and computable step by step while an asymptotic question about it remains undecidable.
These are not the same theorem. But they share a theme: microscopic specification does not automatically provide every higher-level object or answer an observer may want.
Emergence moves to the observer
The paper therefore treats algorithmic emergence not as a magical property stamped onto certain pieces of matter, but as an event in the life of a finite observer: the acquisition of a useful pair (ρ,M).
The map ρ decides which distinctions to retain. The model M gives those retained variables a compact, meaningful parameterization that can be reused on new data. The same organization may be a discovery for one observer and already part of another observer’s background knowledge. Nothing in the substrate arrives with its preferred macrovariables highlighted.
One might hope that requiring genuine scientific structure — relevance, reuse, and transfer to held-out data — avoids the computational barriers. The paper constructs a hard family showing that it does not: both the discovery obstruction and the unbounded-regret obstruction survive even when the target is a reusable scientific model rather than a one-off code.
Why science works anyway
Worst-case impossibility is not a theory of scientific failure. Real science succeeds because it almost never searches the space of all possible programs.
Take the Curie–Weiss magnet. Its permutation symmetry makes the energy depend only on the average magnetization
That symmetry points directly toward a useful representation. In other systems, conservation laws, locality, scale separation, analytic structure, or empirical closure play the same role. They restrict the candidate representations and models enough that search becomes manageable. Renormalization works because symmetry and scale organize which variables and couplings can matter. Hodgkin and Huxley combined inherited electrical structure with carefully measured constitutive relations. Science advances by accumulating such restrictions.
The important word is not merely restricted but searchable. A narrower class is useful only when there is an effective way to explore it and know when the relevant search is complete. Within such classes we can sometimes prove optimality. What the theorems rule out is a universal guarantee over unrestricted descriptions.
No universal certificate of arrival
This leaves a striking asymmetry. Improvement is often finitely witnessable: exhibit a better theory and the old one is shown to be suboptimal. Global optimality is another matter. A fixed sound, effectively axiomatized formal theory cannot certify arbitrarily large specific lower bounds on Kolmogorov complexity; Chaitin’s result is a limit on one formal system’s reach, not a claim that every difficult instance lies forever beyond every stronger theory.
And there is a philosophical distinction worth keeping separate. The paper studies what finite procedures can construct or certify. It does not need to decide whether an uncertifiable mathematical or physical proposition nevertheless has an observer-independent truth value. Standard classical K-notation is a convenient mathematical benchmark; the operational barriers can be stated directly in terms of finite programs and the existence of shorter descriptions.
Science can certify many of its wins. What it lacks is a universal certificate that the search is over.
Anderson wrote that “the ability to reduce everything to simple fundamental laws does not imply the ability to start from those laws and reconstruct the universe.” The point can now be sharpened. The laws may tell us how to generate a realization. They do not write the textbook: they do not automatically choose the variables, discover the useful compression, or certify that no better description remains.
That is not a failure of reduction. It is a limit on construction — and a clue to why successful science is necessarily cumulative, selective, and open-ended.