Kolmogorov complexity for people who write code

This post is the one to read if the rest of the computational series has seemed hand-wavy about the word complexity. The quantity underneath everything is Kolmogorov complexity, and the reason it needs careful handling is that it is formally uncomputable, which sounds like a reason to abandon it, and is actually a reason to handle it like load: with respect, and never at full strength.

The definition

The Kolmogorov complexity of a string x, written K of x, is the length of the shortest program that outputs x and halts. That is the whole definition. The K of a file containing a million digits of pi is small, because a short program generates them. The K of a file containing a million coin flips is close to the file itself, because no program shorter than the file describes it. Complexity is the length of the description, not the size of the thing.

Three properties matter. It is machine-independent up to a constant, once you fix a universal machine, and the constant washes out for long strings. It is uncomputable: no algorithm takes x and returns K of x, because that would solve the halting problem. And it is approximable from above: any compressor gives you an upper bound, because the compressor’s output plus the decompressor is a program for your data. You can never prove a string simple, only demonstrate it. You can prove a string complex only in the trivial sense that nothing compressed it.

What you can do with an uncomputable quantity

The move that makes Kolmogorov complexity usable is to relativise it. K of x given y, the length of the shortest program that outputs x when handed y for free, is still uncomputable, but the structure of results about it survives, and in practice you substitute real compressors and real model classes. A gzip of your data is an upper bound on its complexity under general English-ish structure. A polynomial fit is an upper bound under smooth structure. A neural network that predicts your series is an upper bound under whatever structure the network can express.

Every one of these is a claim of the form: here is a description language, and here is how long your data is in it. The two-part MDL post formalises that, and it is why the plateau argument can run at all. The theorem does not need the true K. It needs a fixed description language and the fact that compression, once you have absorbed all the structure the language can express, stops improving.

The trap I fell into, so you do not have to

The early framework papers defined novelty through the complexity of rule-sets, which in this light was an attempt to use raw, unrelativised K as an observable. That fails three ways at once. You cannot compute it. You cannot pin it down across observers, because the machine constant is not small at the scales that matter. And worst, it is self-referential in the bad direction: measuring the complexity of your own discovery process is measuring with the thing being measured.

The repair is the substitution above. Novelty is not K of nature. Novelty is the drop in your data’s description length when a new structure enters your model class. The description length is computable, the model class is stated, and the drop is a number two people can disagree about only by disagreeing about the model class, which is now an explicit argument instead of a hidden one.

The takeaway for programmers

If you write code, you already have the right instinct: the best abstraction is the shortest program that covers your use cases. Kolmogorov complexity is that instinct made into a measure, and its uncomputability is the formal statement that you can always be surprised by a shorter abstraction. Science, in this reading, is the search for shorter programs for the same data, and a saturated field is one where the current program is already within a constant of the best possible. The next post in this series looks at the one approach to spacetime that treats reality the same way: as something whose shortest description is the physics.