From ``More Is Different'' to Algorithmic Emergence: Why Compression Is the Hard Part

Knowing the microscopic rules of a system is not the same as being able to derive its macroscopic laws — and this paper proves that gap is fundamental, not just practical.

The core idea is simple to state. Suppose you know exactly how a system updates at the microscopic level — every rule, every interaction. Can you derive a compact, predictive description of the system's large-scale behavior? Anderson famously said no in 1972, but his argument was intuitive. This paper makes it precise using Kolmogorov complexity (KC), which measures the length of the shortest computer program that can reproduce a given dataset. A concise macro-law is exactly a short program for the coarse-grained data. The question becomes: can you always find that short program if you know the micro-rules?

The answer is no, for two distinct reasons that compound each other. First, for most datasets, no short description exists at all — most data strings are "algorithmically random," meaning they are their own shortest description. This is not a failure of cleverness; it is a counting argument. There are more possible datasets than there are short programs to describe them, so most datasets are irreducibly complex. Second, even when a short macro-description does exist, no algorithm can reliably find it. Computing KC is provably equivalent to solving the Halting Problem — it is uncomputable. The paper formalizes both obstructions as theorems, and crucially shows they bite even for finite, bounded systems. You do not need infinite lattices or unbounded computation to hit this wall.

The paper distinguishes three flavors of emergence. Weak emergence: the macro behavior is derivable in principle by simulation, just not by any analytic shortcut — computational irreducibility in Wolfram's sense. Strong emergence: for unbounded system families, certain questions about long-run dynamics encode the Halting Problem and become undecidable. Algorithmic emergence (the paper's main contribution): even for a single bounded system, finding the optimally compressed macro-model is uncomputable. This third barrier is strictly different from the other two — it does not require infinite systems, and it is about compression rather than dynamical prediction.

The paper is careful not to be nihilistic. It explains why physics works at all: thermodynamics, hydrodynamics, and renormalization-group theory succeed because they exploit special structure — symmetry, scale separation, self-averaging — that causes the macro configuration space to collapse dramatically. These are real exceptions, and the paper catalogs the mechanisms behind them (central-limit compression, RG universality). But they are exceptions, not the output of any general algorithm. The upshot for science is that empirical macro-experiments are not just convenient — they are logically mandatory. You cannot in general derive thermodynamics from Newton's laws by computation alone. You have to go measure it.