Kolmogorov complexity K(s), and two computable lower bound functions prog1(s), prog2(s). The horizontal axis (logarithmic scale) enumerates all strings s, ordered by length; the vertical axis (linear scale) measures Kolmogorov complexity in bits. Most strings are incompressible, i.e. their Kolmogorov complexity exceeds their length by a constant amount.