Computability Learning Seminar

Wednesday, October 7, 2015 3:30 pm - 3:30 pm EDT (GMT -04:00)

Mohammad Mahmoud, Pure Mathematics, University of Waterloo

"Algorithmic Randomness: Introduction to Kolmogorov Complexity"

After we have established the machine existence (Kraft-Chaitin Theorem), this time we are going to give the proofs for the following "desirable" facts about $K$ which we stated before: (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