An extremely detailed treatment is presented in "An introduction to Kolmogorov complexity and its applications":
<a href="http://www-2.dc.uba.ar/materias/azar/bibliografia/LiVitanyi1997AnIntroductiontoKolmogorov.pdf" rel="nofollow">http://www-2.dc.uba.ar/materias/azar/bibliografia/LiVitanyi1...</a>
There are a lot of good recent books on this topic (I don't know if this area is undergoing a revival) :<p>1. N. K. Vereschagin, V. Uspensky, Alexander Shen : Kolmogorov Complexity (English draft in preparation: <a href="http://www.lirmm.fr/~ashen/kolmbook-eng.pdf" rel="nofollow">http://www.lirmm.fr/~ashen/kolmbook-eng.pdf</a>)<p>2. Downey, Hirschfeldt: Algorithmic Randomness and Complexity (<a href="http://www.springer.com/gp/book/9780387955674" rel="nofollow">http://www.springer.com/gp/book/9780387955674</a>)<p>3. Andre Nies: Computability and Randomness (<a href="https://global.oup.com/academic/product/computability-and-randomness-9780199230761?cc=in&lang=en&" rel="nofollow">https://global.oup.com/academic/product/computability-and-ra...</a>)<p>in addition to the now classic book by Li and Vitanyi that others have mentioned.
When two strings have the same Kolmogorov Complexity, one of them might take significantly longer to "decompress". Shouldn't we then say that this string has higher information content?<p>It feels to me like Kolmogorov Complexity (while very elegant) might just be a crude approximation to a measure that also takes into account the time it takes to print the string.
Kolmogorov Complexity is also presented in Chapter 7 of the classic textbook "Elements of Information Theory":
<a href="http://poincare.matf.bg.ac.rs/nastavno/viktor/Kolmogorov_Complexity.pdf" rel="nofollow">http://poincare.matf.bg.ac.rs/nastavno/viktor/Kolmogorov_Com...</a>
An overview with additional references from Marcus Hutter: <a href="http://www.scholarpedia.org/article/Algorithmic_complexity" rel="nofollow">http://www.scholarpedia.org/article/Algorithmic_complexity</a>
I've used it (by using Normalized Compression Distance) in my Master degree.<p>It was very interesting to find out how efficient it was in authorship attribution, even having 100 possible authors.