K(x) = the length of the shortest program that prints x. Most strings have no short program — and you can prove it by counting, without ever running a single program. There are 2n strings of length n but only 2n−1 programs shorter than n, so at least one string is incompressible. A real compressor gives only an upper bound; and K itself can never be computed. Every claim here is runnable.
source A. N. Kolmogorov, “Three approaches to the quantitative definition of information” (1965) — independently Solomonoff (1960) and Chaitin (1966). Room: THE MACHINE. Rendered, not quoted.
Andrei Nikolaevich Kolmogorov (1903–1987), Moscow, gave information a second face in 1965: not Shannon’s average surprise across a source, but the complexity of one single object — the length of the shortest program that reproduces it.
Ray Solomonoff reached the same idea by 1960 (inductive inference), and Gregory Chaitin independently by 1966. The three names sit over the same definition; SONIA ties the keeper to Kolmogorov.
K(x) = min { |p| : U(p) = x }
The length of the shortest program p that, run on a fixed universal machine U, outputs x. Fixing a different U changes K only by a constant (the invariance theorem). A string is incompressible when K(x) ≥ |x|: no program describes it more briefly than writing it out.
Lengths 0,1,…,n−1 give 1+2+…+2n−1 = 2n−1 programs shorter than n — strictly fewer than the 2n strings of length n. By pigeonhole at least one n-bit string has K(x) ≥ n.
Stronger: fewer than 2n−c strings have K < n−c, so the fraction compressible by ≥ c bits is < 21−c (for c=10, < 1/29). Most strings are incompressible. No sampling — pure combinatorics.
Set a length n (for the exact count), a compression margin c, and a string to hand a real compressor. The generator is fixed-seed — the “random” string is deterministic, never Math.random.
Part A — the counting bound (exact, LIT):
—
| compress by ≥ c bits | fraction < | 21−c | decreasing? |
|---|
Part B — a specific compressor gives only an upper bound AMBER K(x) ≤ |C(x)| + O(1):
The counting half is settled forever: incompressible strings must exist, and almost all strings are incompressible. The compressor half only ever supplies an upper bound — RLE shrinks the periodic string but cannot shrink the fixed-seed one. K itself stays out of reach (window 5).
No total program computes K(x) for every x. If one did, a short program could search for the first string with K(x) ≥ m and print it — a string it just proved needs a long description, produced by a description shorter than m. Contradiction (a Berry / halting argument).
“A good compressor can shrink any file by at least a bit.” Cut. Pigeonhole: a length-reducing injective map from 2n strings into the 2n−1 shorter codes must collide. No lossless coder shrinks every input.
“Enough cleverness compresses random data.” Cut. The counting bound is exact and shape-blind — almost all strings are incompressible; a fixed-seed high-entropy string is one of them.
“K is just the size of the best zip.” Cut. A zip is one upper bound, K(x) ≤ |C(x)|+O(1). True K is uncomputable — no program returns it for all x.
The red team asserts a compressor that losslessly shrinks every n-bit string by at least one bit — mapping all 2n strings into codes of length < n, of which there are only 2n−1. The pigeonhole witness recomputes and turns red: two strings must share a code.
Claim a coder that shrinks all 2n strings into fewer than 2n shorter codes and the map cannot stay injective — a forced collision means the “compression” is lossy. The witness catches it live.