Kolmogorov Complexity

Kolmogorov complexity is the theoretical study of the shortest description of an object. Formally, the Kolmogorov complexity K(x) of a string x is the length of the shortest program that outputs x on a universal computer and then halts. It is uncomputable — no algorithm can calculate K(x) for arbitrary x — but it serves as the absolute lower bound toward which all practical compression algorithms asymptote.

The incomputability of Kolmogorov complexity is not a practical obstacle but a conceptual anchor. It reveals that compression is fundamentally a search problem over the space of all possible descriptions, and that the search space is too vast to exhaust. This mirrors the deep learning observation that generalization requires implicit compression, and that the optimal compression is never fully reachable.

The minimum description length principle in statistics and machine learning is a computable approximation of Kolmogorov complexity, replacing the shortest program with the shortest description in a restricted language.