The Wolf Reads AI: Day 23: Kolmogorov Complexity and Algorithmic Randomness
Authors: Andrei Shen, Vladimir Uspensky, Nikolay Vereshchagin
Published: 2017
Read the PDF here. Find the book at the American Mathematical Society bookstore.
🧠 The Main Idea
What does it mean for something to be random?
What does it mean for something to be simple?
Kolmogorov Complexity gives us a radical way to answer both:
The complexity of a string is the length of the shortest computer program that can produce it.
A string is random if no shortcut exists—no smaller program can reproduce it. It’s incompressible.
This book by Shen, Uspensky, and Vereshchagin explores that idea from every angle—bridging computation, probability, and information theory into one sweeping framework.
🔍 Why It Still Matters
Kolmogorov Complexity shapes how we think about data, patterns, and learning—even if we can’t compute it exactly:
In data compression, where meaning hides in patterns
In machine learning, when we aim to generalize rather than memorize
In anomaly detection, where something “too weird” signals a deeper pattern
In theoretical AI, as we consider the limits of what a system can learn
At its heart is a deep truth:
The best explanation is the shortest one that still works.
If GPT-4 had a guiding principle, it wouldn’t be “know everything.”
It would be: Find the shortest true story.
⚙️ How It Works
Kolmogorov Complexity (KC) is usually written like this:
K(x) = length of the shortest program p such that p outputs x
A string like "111...1" repeated 1000 times? KC is low — easy to generate.
A random-looking 1000-bit string with no pattern? KC is high — no shortcut.
The book introduces:
Plain and prefix complexity — dealing with how we write and decode programs
Algorithmic randomness — when strings pass every statistical test for randomness
Incompressibility lemmas — showing that most strings simply can’t be shrunk
📎 Key Concepts Explained
Algorithmic Randomness
A string is algorithmically random if no program shorter than the string can generate it. It looks random — and is random, by the logic of compression.
Prefix-Free Coding
To keep math clean, programs must be self-contained — one can’t be the prefix of another. This prevents confusion when decoding.
Incompressibility
Most strings can’t be compressed. If you find one that can, you’ve probably uncovered structure, meaning, or a regularity worth investigating.
Memorable Quote from the Book
“Randomness is a lack of pattern. A string is random if it is incompressible.”
✏️ Editor’s Note
This isn’t just math.
It’s philosophy, logic, and computer science rolled into one.
Kolmogorov Complexity and Algorithmic Randomness teaches us how to think—not just about AI, but about explanation itself. It’s a mirror for our models, and maybe for us.
🎙 Podcast Note:
The podcast accompanying this article is created with Google NotebookLM. The two hosts you hear are AI-generated. They dive into the subject material with great enthusiasm. Every once in a while, they miss a detail. Today, they referred to this article as a “paper.” A minor detail. This is a short article, not a paper, which would be a much longer work with detailed citations. (Although, admittedly, when I have the time, I do sometimes provide detailed citations for my articles. Today is not that day.) More AI paper fun tomorrow.
Coming Tomorrow
🧮 Minimum Description Length (MDL) — the idea that the best model is the one that explains the data in the fewest bits.
Think of Occam’s razor, but with math.
#KolmogorovComplexity #AlgorithmicRandomness #WolfReadsAI #InformationTheory #Compression #ShenUspenskyVereshchagin #AIphilosophy #SutskeverPapers #OccamsRazor #ComplexityScience
Share this post