12 ms·

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

by devty 10y ago

sewercake 10y ago
http://inference-review.com/article/doing-mathematics-differently 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.
- rfreytag 10y ago
  Kolmogorov-Chaitin Complexity is another term for the same concept (as per the OP Wikipedia article).
mac01021 10y 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-Michael-Sipser/dp/113318779X http://www.amazon.com/Introduction-Theory-Computation-Michae... [2] http://www.amazon.com/Introduction-Kolmogorov-Complexity-Applications-Computer/dp/0387339981 http://www.amazon.com/Introduction-Kolmogorov-Complexity-App...
- Chris2048 10y ago
  I did a uni project based on that second book. Despite the title, it's hard to actually get to practical applications.
- eli_gottlieb 10y 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 10y ago
I like this website a lot for gentle introductions to new topics: https://jeremykun.com/2012/04/21/kolmogorov-complexity-a-primer/ https://jeremykun.com/2012/04/21/kolmogorov-complexity-a-pri...
guiraldelli 10y 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! :)
- mturmon 10y 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.
  - eli_gottlieb 10y ago
    That does tend to happen with incomputable functions. I once got an interesting hobby project out of an AIT paper, though: https://github.com/eligottlieb/Calumbda https://github.com/eligottlieb/Calumbda
    - mturmon 10y ago
      True. I was compelled to write because I've noticed people being seduced by the notion of KC. It tends to be a dead end.
  - curuinor 10y ago
    Computable things include CSSR (http://bactra.org/CSSR/ http://bactra.org/CSSR/), the considerably more bullshit Lempel-Ziv (yeah, like LZ compression) complexity, etc etc etc etc. Lloyd(http://web.mit.edu/esd.83/www/notebook/Complexity.PDF http://web.mit.edu/esd.83/www/notebook/Complexity.PDF) has a supposedly non-exhaustive list, but it is probably exhaustive enough for any purpose. Of those, the useful and non-banal ones in my opinion include Fisher information, Renyi entropy, VC dimension, the many ordinary computational complexities (of course), metric entropy, correlational structure and channel capacity.
curuinor 10y 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.
sklogic 10y ago
A definitive introduction to the field: https://www.cs.auckland.ac.nz/~chaitin/cup.pdf https://www.cs.auckland.ac.nz/~chaitin/cup.pdf

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

by devty 10y ago

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

http://inference-review.com/article/doing-mathematics-differently 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.

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

mac01021 10y 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-Michael-Sipser/dp/113318779X http://www.amazon.com/Introduction-Theory-Computation-Michae... [2] http://www.amazon.com/Introduction-Kolmogorov-Complexity-Applications-Computer/dp/0387339981 http://www.amazon.com/Introduction-Kolmogorov-Complexity-App...

Chris2048 10y ago
I did a uni project based on that second book. Despite the title, it's hard to actually get to practical applications.
eli_gottlieb 10y 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 10y ago

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

guiraldelli 10y 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! :)

mturmon 10y 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.
- eli_gottlieb 10y ago
  That does tend to happen with incomputable functions. I once got an interesting hobby project out of an AIT paper, though: https://github.com/eligottlieb/Calumbda https://github.com/eligottlieb/Calumbda
  - mturmon 10y ago
    True. I was compelled to write because I've noticed people being seduced by the notion of KC. It tends to be a dead end.
- curuinor 10y ago
  Computable things include CSSR (http://bactra.org/CSSR/ http://bactra.org/CSSR/), the considerably more bullshit Lempel-Ziv (yeah, like LZ compression) complexity, etc etc etc etc. Lloyd(http://web.mit.edu/esd.83/www/notebook/Complexity.PDF http://web.mit.edu/esd.83/www/notebook/Complexity.PDF) has a supposedly non-exhaustive list, but it is probably exhaustive enough for any purpose. Of those, the useful and non-banal ones in my opinion include Fisher information, Renyi entropy, VC dimension, the many ordinary computational complexities (of course), metric entropy, correlational structure and channel capacity.

curuinor 10y 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.

sklogic 10y ago

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