A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Kolmogorov complexity K(x) of a string x is the length of the shortest program (on a fixed universal Turing machine) that outputs x and halts. It measures the intrinsic information content of an individual object, independent of any probability distribution. A string like "0101010101..." has low K (a short loop generates it), while a truly random string has K approximately equal to its length (no program shorter than the string itself can produce it). Kolmogorov complexity is uncomputable — there is no algorithm that takes x and returns K(x) — but it provides the foundation for algorithmic randomness, connects to Shannon entropy via the expected K of random strings, and gives a rigorous definition of individual-object randomness.
Shannon entropy measures the average information content of a random source. But what about the information content of a specific, individual string — say, the digits of pi, or a specific DNA sequence, or a particular file on your disk? Kolmogorov complexity provides the answer: K(x) is the length of the shortest program that produces x.
The definition requires fixing a universal Turing machine U. The Kolmogorov complexity K_U(x) = min{|p| : U(p) = x}, where |p| is the length of program p. The invariance theorem states that K_U(x) and K_{U'}(x) differ by at most a constant (depending on U and U' but not on x), so the choice of reference machine affects complexity by at most an additive constant. This justifies treating K(x) as a property of x itself.
Strings fall on a spectrum. Highly regular strings (like "000...0" or "0101...01") have low K — a short program generates them. Random-looking strings with no discernible pattern have K close to their length — the shortest program is essentially "print the string literally." This gives a rigorous definition of algorithmic randomness: a string x of length n is random if K(x) >= n - c. Most strings are random in this sense (by a counting argument: there are more strings than short programs), and this matches the AEP's statement that most sequences from a fair source are "typical."
The uncomputability of K(x) is fundamental, not practical. No algorithm can compute K for all inputs. This means we can never know for certain that a given string is truly random (has high K), though we can establish upper bounds by finding short programs. Despite this uncomputability, Kolmogorov complexity is profoundly useful as a theoretical tool: it provides the cleanest definition of randomness, underpins the minimum description length (MDL) principle in statistics, connects to Godel's incompleteness theorems, and gives insight into the foundations of probability and induction. The normalized information distance d(x,y) = (K(x|y) + K(y|x)) / K(x,y) is a universal similarity metric that, while uncomputable, inspires practical compression-based similarity measures used in clustering and classification.