Kolmogorov Complexity – A Primer (2012)

An extremely detailed treatment is presented in &quot;An introduction to Kolmogorov complexity and its applications&quot;: <a href="http:&#x2F;&#x2F;www-2.dc.uba.ar&#x2F;materias&#x2F;azar&#x2F;bibliografia&#x2F;LiVitanyi1997AnIntroductiontoKolmogorov.pdf" rel="nofollow">http:&#x2F;&#x2F;www-2.dc.uba.ar&#x2F;materias&#x2F;azar&#x2F;bibliografia&#x2F;LiVitanyi1...</a>

There are a lot of good recent books on this topic (I don&#x27;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:&#x2F;&#x2F;www.lirmm.fr&#x2F;~ashen&#x2F;kolmbook-eng.pdf" rel="nofollow">http:&#x2F;&#x2F;www.lirmm.fr&#x2F;~ashen&#x2F;kolmbook-eng.pdf</a>)<p>2. Downey, Hirschfeldt: Algorithmic Randomness and Complexity (<a href="http:&#x2F;&#x2F;www.springer.com&#x2F;gp&#x2F;book&#x2F;9780387955674" rel="nofollow">http:&#x2F;&#x2F;www.springer.com&#x2F;gp&#x2F;book&#x2F;9780387955674</a>)<p>3. Andre Nies: Computability and Randomness (<a href="https:&#x2F;&#x2F;global.oup.com&#x2F;academic&#x2F;product&#x2F;computability-and-randomness-9780199230761?cc=in&amp;lang=en&amp;" rel="nofollow">https:&#x2F;&#x2F;global.oup.com&#x2F;academic&#x2F;product&#x2F;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 &quot;decompress&quot;. Shouldn&#x27;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 &quot;Elements of Information Theory&quot;: <a href="http:&#x2F;&#x2F;poincare.matf.bg.ac.rs&#x2F;nastavno&#x2F;viktor&#x2F;Kolmogorov_Complexity.pdf" rel="nofollow">http:&#x2F;&#x2F;poincare.matf.bg.ac.rs&#x2F;nastavno&#x2F;viktor&#x2F;Kolmogorov_Com...</a>

An overview with additional references from Marcus Hutter: <a href="http:&#x2F;&#x2F;www.scholarpedia.org&#x2F;article&#x2F;Algorithmic_complexity" rel="nofollow">http:&#x2F;&#x2F;www.scholarpedia.org&#x2F;article&#x2F;Algorithmic_complexity</a>

I&#x27;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.

Linux dev&#x2F;random entropy quality check is (was, I have not checked it recently) based on Kolmogorov complexity.

If we&#x27;re doing Kolmogorov complexity reposts: <a href="http:&#x2F;&#x2F;forwardscattering.org&#x2F;post&#x2F;7" rel="nofollow">http:&#x2F;&#x2F;forwardscattering.org&#x2F;post&#x2F;7</a> <a href="http:&#x2F;&#x2F;forwardscattering.org&#x2F;post&#x2F;14" rel="nofollow">http:&#x2F;&#x2F;forwardscattering.org&#x2F;post&#x2F;14</a>