Approximate the Kolmogorov complexity K(x) of strings using LZ77 compression. Compare random, structured, and periodic strings. Visualize the complexity spectrum of 2D patterns.
Kolmogorov complexity K(x) = length of shortest program generating x. Uncomputable in general (Chaitin 1975), but upper-bounded by any compression algorithm. LZ compression approximates K(x). Random strings are incompressible: K(x)≈|x|. K(x)/|x|→0 for structured strings. Related to Shannon entropy for i.i.d. sources by AEP.