Kolmogorov-Chaitin Complexity

Algorithmic incompressibility: random vs structured strings

String Input

Length: ā€”
LZ76 complexity: ā€”
Normalized K: ā€”
Entropy rate h: ā€”
gzip ratio: ā€”
LZ complexity
Entropy h
K(x) = length of shortest program outputting x. Incomputable in general (halting problem).

LZ76 (Lempel-Ziv '76): computable lower bound. Counts distinct subword complexity. K(x)/n ā†’ h(source) for ergodic processes.

Incompressible strings: most n-bit strings have K(x) ā‰„ nāˆ’O(1). Random = maximal complexity.