Kolmogorov Complexity K(x) of a string x is the length of the shortest program on a universal Turing machine that outputs x. It is uncomputable in general (by reduction to the halting problem), but compressors give upper bounds.
K(x) ≤ |x| + O(1) | K(x) ≥ |x| for most strings | K(xy) ≤ K(x) + K(y) + O(log min(K(x),K(y)))
A string is
Kolmogorov random (Martin-Löf random) if K(x) ≥ |x| − c for some constant c. The normalized compression distance (NCD) approximates the information distance between two strings. The visualization shows run-length complexity and entropy as proxies for algorithmic complexity.