An Introduction to Kolmogorov Complexity and Randomness
Anthony Morphett

Abstract:
I will give an introductory overview of Kolmogorov complexity, its
connections with algorithmic randomness, and some important theorems
in the area.  Minimal knowledge of computability and randomness will
be assumed.  References are Downey & Hirshfeldt,
http://www.mcs.vuw.ac.nz/~downey/randomness.pdf and Nies,
http://www.cs.auckland.ac.nz/~nies/Niesbook.pdf

Part 1: Plain & prefix-free Kolmogorov complexity & some properties;
prefix-free machines, Kraft-Chaitin Theorem; Chaitin's Omega

Part 2: Other conceptions of randomness: measure, predictability;
Schnorr's Theorem; Kucera-Gacs Theorem

Part 3: Lowness properties; degrees of randomness.