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