An introduction to Kolmogorov complexity and its applications

What Hacker News says

1. bo1024Oct 2019
   CS is like math, not philosophy -- the fundamental ideas are gradually refined by a community, and eventually someone puts them into a book. Usually there are many books and people have different favorites.

   So the closest parallels are original research papers like Turing's and Shannon's; but you're probably better off reading more recent textbooks.

   That said, to balance out the heavy emphasis on programming and engineering books here, some recommendations:

   - Sipser. Introduction to the Theory of Computation.

   - Russell, Norvig. AI: A Modern Approach.

   - For algorithms I don't have a preference. There is Dasgupta-Papadimitriou-Vazirani; Cormen-Leisersen-Rivest-Stein; Kleinberg-Tardos; and more.

   A bit farther from core CS, I also like:

   - Cover, Thomas. Elements of Information Theory.

   - Li, Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications

   Show morethread
2. guiraldelliMay 2016
   The standard reference is "An Introduction to Kolmogorov Complexity and Its Applications", from Ming Li and Paul Vitányi. It is the "must-go" for the subject.

   An introductory chapter is available in the "Elements of Information Theory" of Thomas Cover and Joy Thomas.

   The field is called "Algorithmic Information Theory" and some of the big names in it are: Ray Solomonoff, Gregory Chaitin, Ming Li, Paul Vitányi, Chris Wallace, David Dowe, Markus Hutter, Jürgen Schmidhuber, Jorma Rissanen, among others. All of these guys are great writers and have breakthrough ideas!

   If you are interested in "real world" applications of Kolmogorov complexity, I recommend you to take a look at MDL (Minimum Description Length) and MML (Minimum Message Length).

   I hope you will enjoy the references! :)

   Show morethread
3. mafribeFeb 2016
   I'm sorry to say this, but your second post also doesn't really address the issue and continues to misunderstand the purpose and definitions of Kolgomorov complexity.

   The fact that for any specific string S you can find a language L such that the Kolgomorov complexity K(L, S) is 0, is not that interesting.

   1. For any specific L, you can only play this trick (hardcoding a target string) for a finite number of strings. That means for essentially all strings (all but a small finite number) the trick is irrelevant.

   2. There is no free lunch: The trick you use to bring down the Kolgomorov complexity K(L, S) down to 0 increases the complexity of L. This can be taken into account, see "conditional Kolgomorov complexity".

   The book "An Introduction to Kolmogorov Complexity and Its Applications" by Li and Vitányi explains this, and much more in great detail, and is highly recommended.

   Show morethread
4. orangecatMay 2011
   do you have any resources that are more rigorous?

   For light bedtime reading, there's An Introduction to Kolmogorov Complexity and Its Applications: http://www.amazon.com/Introduction-Kolmogorov-Complexity-App...

   That is, the laws of thermodynamics concisely phrase the increasing entropy of the universe with a low Komolgorov complexity, suggesting that the mechanics of the universe operate with a low Komolgorov complexity.

   I'd agree with that.

   Show morethread
5. sbOct 2009
   Thanks for the video, I will watch it. The interested readers might want to try the book "An Introduction to Kolmogorov Complexity and its Applications" by Li and Vitanyi (the 3rd edition came out recently). It is comparatively expensive, but Vitanyi's CWI site holds additional material.
   thread
6. arketypMar 2024
   Thanks, I had to dig. I read about it in [1]. Mises was concerned about the formalization of probability theory. It seems the idea appears at least as early as in his 1919 paper [2].

   [1] An Introduction to Kolmogorov Complexity and Its Applications, M. Li & P. Vitnányi

   [2] Grundlagen der Wahrscheinlichkeitsrechnung, R. von Mises

   thread