Shannon measured the information in a source; Kolmogorov asked a stranger question — how much information is in this one object? His answer: the length of the shortest program that prints it. A repetitive string has a tiny program (low K); a random one has none shorter than itself (K ≈ its length). Down the center: an object goes in, a real lossless compressor returns an upper bound on that shortest length, the verdict comes out. The blue team builds and witnesses it; the red team attacks — and K itself is uncomputable, so every number here is honestly a ceiling, never K.
source A. N. Kolmogorov, Three approaches to the quantitative definition of information, Problemy Peredachi Informatsii 1(1) (1965). Linked: Kolmogorov's own 1965 talk on algorithmic information theory — archive.org/details/kolmogorov-1965talk (companion of the same year; the journal paper is not itself on archive.org — this citation is AMBER). Rendered, not quoted.
The engine is an honest lossless coder: run-length + Elias-γ. Split the bit string into runs of equal bits; write the first bit, then each run length in the self-delimiting γ code (m in binary, prefixed with that many−1 zeros). It is a bijection on codes — decompress(compress(x)) = x — so its output length is a program that prints x. Hence K(x) ≤ |C(x)| + O(1).
The counting theorem (live, right): C is one-to-one, and there are only 2^(n−k) − 1 possible codewords shorter than n−k bits. So of the 2ⁿ strings of length n, fewer than 2^(n−k) can be squeezed below n−k bits. Most strings simply cannot be compressed — for pure counting reasons, no cleverness helps.
| m | Elias-γ | bits |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 010 | 3 |
| 4 | 00100 | 5 |
| 64 | 0000001000000 | 13 |
the-entropy measured the average information of a source — H needs a probability distribution. Kolmogorov drops the distribution: the information is in the single object, defined by the shortest program, no ensemble required. Where Shannon's bit is a rate, Kolmogorov's is a length.
And the arc closes at the-diagonal: K is uncomputable for exactly Cantor's reason. "The shortest program that prints x" cannot itself be computed — assume it could and you build a program that prints "the first string whose K exceeds this program's length," a self-referential contradiction (Chaitin). Each sphere is the next one's premise.
The blue team's live re-check: re-verify losslessness over every string up to length 12, re-confirm the counting bound holds for all k at n = 12, and re-measure the two anchors. If red tampers with the compressor, this badge is where the collision shows.
Kolmogorov complexity is defined on a single finite object, written here as a binary string x. Its raw length n bits is the trivial program "print these n bits." The question is whether a shorter program exists. Structure is what makes one exist:
| object | nature | shortest program |
|---|---|---|
| 0000…0 (64) | maximal structure | tiny — "print 0, 64×" |
| 0101…01 | structured | small — "print 01, 32×" |
| fair coin flips | no structure | ≈ itself (n bits) |
Feed any bit string into the panel below. The compressor never knows the object's structure — it only encodes runs, so its length is an upper bound on the true shortest program, not the shortest program itself.
Type only 0s and 1s (max 128). The compressed length is computed live from the run structure — never looked up.
The counting argument, live. Enumerate all 2ⁿ strings of length n; for each k count how many the real compressor squeezes below n−k bits, and check it against the bound 2^(n−k).
| k | #{ |C(x)| < n−k } | bound 2^(n−k) | holds? |
|---|
What the machine produces, proven: a computable upper bound on K(x) for any object — and a live census showing that of 4096 length-12 strings, only 70 compress at all while 4026 are incompressible. The shortest program itself is marked AMBER: K is uncomputable, so the panel reports a ceiling, and the counting bound proves the ceiling is tight for almost every object.
The blue team's witness (left) re-confirms losslessness and the bound live; the red team (right) swaps in a lying compressor to try to break it.
Worse for anyone wanting a number: K is only defined up to an additive constant (the invariance theorem — change the universal machine, change K by O(1)). So "the" complexity of a short string is not even a fixed integer. The panel is honest about being an upper bound; it never claims to have found the shortest program.
"This tool computes K(x)." Cut. It computes |C(x)|, one weak compressor's output — an upper bound. K is uncomputable; no program returns it for all inputs.
"A high ratio proves the string is random." Cut. It proves only that this coder failed. Proving a specific string incompressible would give a lower bound on K — which Chaitin showed is impossible past a fixed constant.
"Kolmogorov defined it first and alone." Kept, corrected. Solomonoff (1960) and Chaitin (1966) reached the same idea independently — hence Kolmogorov–Chaitin–Solomonoff complexity.
The red team's move: swap in a "compressor" that shaves one bit off every string (return x minus its last bit). It looks like a free win — but 2ⁿ strings cannot fit in 2^(n−1) codes, so two must collide and it cannot be lossless. Window 7 is watching.
Activate it and the witness recomputes: decompress no longer inverts compress, and a concrete collision appears (two objects, one code). The badge turns red. Nothing is faked — the pigeonhole violation is real and it is caught.