Watch: Kolmogorov Complexity
The length of the shortest program that reproduces a given string, a measure of how much information one specific object carries, approximated in practice by how well it compresses.
Transcript
Imagine you want to describe a piece of text. Its Kolmogorov complexity is the length of the shortest computer program that can generate that exact text and then stop.
For example, a million characters of the letters A and B repeated has very low complexity, because a simple three-line loop can recreate it. But a million characters of random coin flips has high complexity. There is no shortcut; the shortest description is the string itself.
In the real world, we cannot mathematically calculate this absolute minimum. Instead, we use file compressors like gzip to find a practical upper bound. This works because compression and prediction are actually the same problem. A language model that predicts the next word accurately is also a highly efficient compressor.
This brings us to conditional complexity, which measures how much new information a text adds if you already have access to another source. If that other source is an artificial intelligence model's training data, a page that just repeats the common consensus adds almost nothing. It has low conditional complexity. But a page with a new measurement, a fresh date, or an unseen result has high conditional complexity. This is the only kind of content that actually changes what the model can produce.
This mathematical lens helps us detect computer-generated filler, compare documents without complex training, and prevent models from overfitting. It reminds us that true information is not about how much we write, but how much we reveal that is genuinely new.