Approximating algorithmic complexity K(x) via compression. Compare run-length, LZ77-style, and entropy-based compression on structured, random, and periodic strings. Visualize the incompressibility theorem.
Kolmogorov complexity K(x) = length of shortest program producing x. Uncomputable (reduces to halting problem), but compression ratio approximates it from above. Incompressibility theorem: fraction of strings of length n with K(x)<n-c is at most 2^{-c} — most strings are incompressible. Logical depth (Bennett): time for shortest program to run ≈ measure of organized complexity. Connection to entropy: E[K(X)] ≈ H(X) for ergodic sources.