An extremely detailed treatment is presented in "An introduction to Kolmogorov complexity and its applications": http://www-2.dc.uba.ar/materias/azar/bibliografia/LiVitanyi1...