LLM + RoboticsUnit 5 · Generative models & scaling · Day 26

Kolmogorov Complexity and Algorithmic Randomness

The information in one object is the length of the shortest program that prints it. A string is random when no such program is shorter than the string itself.

AuthorsAlexander Shen, Vladimir A. Uspensky, Nikolay Vereshchagin

Year / venue2017 · book, AMS Mathematical Surveys and Monographs vol. 220

Core ideaComplexity = shortest description

Study time4–6 h (selected chapters)

Original: AMS book page (the authors also post a draft on Alexander Shen's homepage) · Code, notebook and exercises: 30u30 Day 26

Start here (no maths needed)

The amount of information in something is the length of the shortest set of instructions that could recreate it, and something is truly random if there's no shortcut.

Think of it like this

You've probably seen a zip file. Zipping a folder makes it smaller by finding patterns. A file that says "ha" a thousand times shrinks to almost nothing, because the computer can just write "ha, 1000 times". A file of random key-mashing hardly shrinks at all, because there's no pattern to use. Kolmogorov complexity is the size of the best possible zip of something. It's the perfect version that no real zip program can always reach.

How it works

Pick something to describe, like a long string of letters.
Look for the shortest computer program that prints exactly that string.
The length of that program is the string's complexity.
Patterned strings have short programs. Random ones don't: the shortest program is basically "print this whole thing".
A surprising fact: no computer can always find the shortest program. So in practice we use real compressors (like zip) to get an estimate.

Why robots care

A robot that has learned how the world works can describe what it sees with fewer "bits", because it can predict most of it. If a robot's sensor readings suddenly stop matching its predictions and become hard to "compress", something unexpected may be happening, like a slipping wheel.

Try it

Describe a chessboard pattern to a friend in one sentence. Now try to describe a random splatter of paint. Which needs more words? That difference is the idea of complexity.
In the demo further down, press Repeating "ab", then Shuffle current. Same letters, but the compressed size jumps, because the pattern is gone.

Words to know

Compression: Making data smaller by using its patterns, like a zip file.
Complexity: Here: the length of the shortest program that recreates something.
Random: Having no shortcut. You can't describe it in fewer bits than it takes up.
Bit: The smallest piece of information: a single 0 or 1.

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings and the "Why it matters for robotics" box, and come back for the rest later.

1. Summary

TL;DR

This is a 500-page textbook from the Moscow school of algorithmic information theory, not a single paper. Its starting point is Kolmogorov's 1960s idea: measure the information in an individual object, such as one string, by the length of the shortest program that outputs it. Patterned strings have short programs. Most strings don't, and those are the random ones. The quantity can't be computed exactly, but any real compressor gives an upper bound. That's the formal version of "compression is understanding", the intuition behind Sutskever's view that good prediction means finding the shortest description of the data.

Definition: C(x) is the length of the shortest program p such that a fixed universal machine U prints x from p.
Language doesn't matter much: switching universal machine changes C(x) by at most a constant (the invariance theorem).
Most strings are incompressible: a counting argument shows fewer than a 2^−k fraction of n-bit strings can be compressed by k bits.
C is uncomputable: no algorithm returns C(x) for every x. Compressors give upper bounds only.
Randomness gets a definition: an infinite sequence is random (Martin-Löf) exactly when its prefixes are incompressible, in the prefix-complexity sense.

2. The core idea

C_U(x) = min { |p| : U(p) = x }                  plain complexity

|C_U(x) − C_V(x)| ≤ c_UV       for all x           invariance theorem
C(x)   ≤ |x| + c                                   "just print it"
#{ x of length n : C(x) < n − k }  <  2^(n−k)      counting bound

K(x): same, but programs must be prefix-free
Σ_x 2^(−K(x)) ≤ 1                                  Kraft inequality

U is a universal machine: think of a fixed programming language that can simulate any other.
|p| is the program length in bits. C(x) is the length of the best one.
Invariance: any language V can be simulated in U with a fixed-size interpreter, so C_U(x) ≤ C_V(x) + (size of the interpreter). The constant depends on U and V, not on x.
Upper bound: the program "print the following n bits" always works, so C(x) never exceeds the length of x by more than a constant.
Counting: there are only 2^n−k − 1 programs shorter than n − k bits. Each prints at most one string. So at most that many n-bit strings out of 2ⁿ can be compressed by k bits. At least one string of every length is fully incompressible.
Prefix complexity K requires that no valid program be the start of another, as with self-delimiting codes. Then the weights 2^−K(x) sum to at most 1 and form a probability-like distribution. Day 27 builds on exactly this weighting.

3. Deep dive

Why it can't be computed

Suppose a program could compute C(x). Then write a short program: "search strings in order and print the first one with C(x) > n". That program has length about log n plus a constant, yet it prints a string whose complexity exceeds n. For large n, that's a contradiction. This is a formal Berry paradox ("the smallest number not describable in fewer than twelve words"). The practical upshot: you can always find a short description, but you can never certify that it's the shortest.

Compressors as computable upper bounds

Any lossless compressor plus its decompressor is a program that prints x. So C(x) ≤ |compressed(x)| + |decompressor| + O(1). Real compressors only find some kinds of pattern. A frequency-based code (Huffman, order-0 entropy) sees symbol counts only. Dictionary methods such as DEFLATE also catch repeats. Neither finds the pattern in the digits of π, which have tiny Kolmogorov complexity. The demo shows the gap between counting symbols and finding structure.

Interactive: compression as a complexity proxy

Bars, in bits: raw size (8 bits per byte), an order-0 entropy bound (symbol frequencies only), and the size after your browser's built-in DEFLATE. DEFLATE output is a computable upper bound on complexity, up to a constant.

Length (chars)

–

Entropy bits/char

–

DEFLATE bits/char

–

Ratio vs raw

–

Try this: load "Repeating ab". Entropy says 1 bit per character, but DEFLATE gets far below that, because it finds the repeat. Now press Shuffle. The letter counts, and so the entropy bound, stay the same. The compressed size jumps, because the pattern is gone. Then try "Counting": a three-line program prints it, yet DEFLATE does worse than even the symbol-count bound. The compressor's bound is valid, just very loose.

Randomness, MDL and learning

For infinite binary sequences the book develops Martin-Löf randomness: a sequence is random if it passes every effective statistical test. The Levin–Schnorr theorem shows this is the same as saying that the prefix complexity of its first n bits stays above n minus a constant. Two very different definitions agree, which is good evidence the concept is right.

For machine learning the useful idea is two-part coding: describe a model, then the data given the model. The total length is an upper bound on complexity, and minimising it is the Minimum Description Length principle of Day 05 and Day 04. Cross-entropy loss on a dataset is a code length too: a model with loss L nats per token can compress the data to about L/ln 2 bits per token with arithmetic coding. Lower loss on Day 25 literally means a shorter description. Days 06 and 07 use compressed size as a practical stand-in for complexity in physical systems.

4. Why it matters for robotics

The link is conceptual. Nobody computes Kolmogorov complexity on a robot. But the ideas show up in practical tools.

Model selection for system identification: choosing between a simple and a detailed dynamics model is a description-length trade-off. Fit plus model size, not fit alone.
World models are compressors: a model that predicts the next sensor frame well encodes it in few bits. Better prediction and better compression are the same thing.
Anomaly detection by surprise: a log segment or sensor trace that compresses much worse than usual under a trained model is a cheap fault signal.
Honest limit: uncomputability means "simplest explanation" is always approximated by some chosen model class. The choice of class decides what counts as simple.

5. How to study it

Don't read all 500 pages. Read the introduction and the opening chapters on plain complexity (definition, invariance, counting, uncomputability). About 2 h.
Then skim the material on prefix complexity and Martin-Löf randomness for the Levin–Schnorr theorem. Skip proofs on the first pass.
In the 30u30 Day 26 folder, read implementation.py (Huffman coding, arithmetic coding, entropy and normalized compression distance). Run train_minimal.py and compare the estimators on different strings.
Work through notebook.ipynb and the five exercises, ending with the incompressibility one.
Stretch: compute the normalized compression distance between short texts in two languages and see whether it clusters them.

6. Self-check

Why does the choice of programming language only shift C(x) by a constant?

Any language can be simulated in the reference language by a fixed interpreter. Prepending that interpreter to the best program costs the same number of bits for every x.

Prove that some string of length n has C(x) ≥ n.

There are 2ⁿ strings of length n but only 2ⁿ − 1 programs shorter than n bits. Each program prints at most one string, so at least one string is left over.

Why can't a compressor tell you the true C(x)?

C is uncomputable. A compressor gives a valid description, so an upper bound, but it can miss patterns, and no algorithm can prove a description is the shortest.

The digits of π look random. Are they Kolmogorov-random?

No. A short program generates as many digits as you want, so the first n digits have complexity around log n plus a constant. They pass many statistical tests, but they're highly compressible in principle.

Why would shuffling a string leave its entropy bound unchanged but increase its compressed size?

Order-0 entropy depends only on symbol counts, which shuffling preserves. Order and repeats are destroyed, and those are what a dictionary compressor exploits.

7. Further reading

Shen, Uspensky and Vereshchagin (2017), the book itself
Li and Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, the standard Western reference
30u30 Day 26: implementation, notebook, cheatsheet, exercises
Next: Day 27, Machine Super Intelligence