Computability Learning Seminar

Mohammad Mahmoud, Pure Mathematics, University of Waterloo

"Algorithmic Randomness: Introduction to Kolmogorov Complexity"

Last time we saw why the Kolmogorov complexity $K$ can be better than the plain complexity $C$ as it is subadditive and complexity doesn't dip. This time we are going to see more properties showing that $K$ matches our intuition. More precisely, (a) Incompressible (in the sense of $K$) strings have only short runs of zeros (i.e. blocks only consisting of zeros), and (b) Zeros and ones occur balancedly.

MC 5403