Kolmogorov Complexity (2014) [pdf]

http://informationtheory.weebly.com/uploads/2/4/6/2/24624554/kolmogorov_complexity.pdf

by rfreytag • 10 years ago

73 21 10 years ago

informationtheory.weebly.com

devty• 10 years ago

Cool. Can anyone tell me what keywords may be useful in exploring this topic? Textbooks?

sewercake• 10 years ago

http://inference-review.com/article/doing-mathematics-differ...

While I don't have a text book for you, I found this article by Gregory Chaitin (a notable academic in the same sphere as kolmogorov et al) to be very exciting / enlightening.

rfreytag2• 10 years ago

Kolmogorov-Chaitin Complexity is another term for the same concept (as per the OP Wikipedia article).

mac01021• 10 years ago

Sipser's undergraduate textbook on the theory of computation[1] has a single, very nice, introductory chapter on the topic.

If you want to get technical and deep, you probably want [2] (An introduction to Kolmogorov complexity and its applications). It's pretty hard, though. Not for the faint of heart.

[1] http://www.amazon.com/Introduction-Theory-Computation-Michae...

[2] http://www.amazon.com/Introduction-Kolmogorov-Complexity-App...

Chris2048• 10 years ago

I did a uni project based on that second book. Despite the title, it's hard to actually get to practical applications.

eli_gottlieb2• 10 years ago

If you want to get technical and deep, you probably want [2] (An introduction to Kolmogorov complexity and its applications). It's pretty hard, though. Not for the faint of heart.

Basically, learn real analysis first, with emphases on topology and measure theory. Then tackle Kolmogorov complexity theory.

cJ0th• 10 years ago

I like this website a lot for gentle introductions to new topics: https://jeremykun.com/2012/04/21/kolmogorov-complexity-a-pri...

guiraldelli• 10 years ago

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! :)

mturmon4• 10 years ago

Yet, having studied the chapter in Cover and Thomas, and worked with people who have tried to apply the idea as an inference tool, and listened to talks by David Dowe explaining MML and its relation to MDL -- I have come away with the impression that the intellectual interest in Kolmogorov Complexity is much, much greater than its actual usefulness.

sklogic• 10 years ago

A definitive introduction to the field: https://www.cs.auckland.ac.nz/~chaitin/cup.pdf

curuinor3• 10 years ago

Badii and Politi 1997 is fun and interesting reading. Try Lempel-Ziv complexity for some hilarious idiocy and statistical Grassberger complexity for some less idiotic thought. Logical depth. Symbolic dynamics.

glenjamin• 10 years ago

You might also find this video relevant, it's entitled "Kolmogorov Music", and attempts to apply the ideas from the paper to musical notation.

https://www.youtube.com/watch?v=Qg3XOfioapI

rfreytag2• 10 years ago

Excellent talk with great pointers to other material.

If you have a pointer to Fogus' talk he mentioned, titled: Macronomicron, well, that sounds intriguing.

XaspR8d• 10 years ago

Michael Fogus. "The Macronomicon". Clojure Conj 2011.

video: https://www.youtube.com/watch?v=0JXhJyTo5V8&list=PLZdCLR02gr...

slides: http://blog.fogus.me/2011/11/15/the-macronomicon-slides/

batz• 10 years ago

Komolgorov, Hofstadter, Autechre, and LISP.