An Introduction to Kolmogorov Complexity and Its Applications

by Ming Li, Paul Vitányi

"The book is outstanding and admirable in many respects. ... is
necessary reading for all kinds of readers from undergraduate students
to top authorities in the field." Journal of Symbolic Logic
Written by two experts in the field, this is the only comprehensive
and unified treatment of the central ideas and their applications of
Kolmogorov complexity. the book presents a thorough treatment of the
subject with a wide range of illsutrative applications. Such
applications include the randomeness of finite objects or infinite
sequences, Martin-Loef tests for randomness, information theory,
computationla learning theory, the complexity of algorithms, and the
thermodynamics of computing.
It will be ideal for advanced undergraduate students, graduate
students, and researchers in computer science, mathematics, cognitive
sciences, philosophy, artificial intelligence, statistics, and
physics. the book is self-contained in that it contains the basic
requirements from mathematics and computer science. Included are also
numerous problem sets, comments, source references, and himnts to
solutions of problems.
In this new edition the authors have added new material on circuit
theory, distributed algorithms, data compression, and other topics.

Genres: Mathematics, Computer Science, Textbooks, Computation, Nonfiction, Technology, Science

637 pages, Hardcover

First published May 6, 1993

Reviews

[Nick Black]

I'm more excited about this than any textbook I've read all year. It's absolutely awesome thus far. Kolmogorov complexity is so deep in computer science -- in a way, I feel that it *is* computer science, i.e. "necessary and sufficient" as we dorks like to say -- yet understood or even known by so few. I'm hoping that when done with this, my understanding of my discipline will be as broadened and freshened as it was upon reading classics like Hennessy and Patterson's Computer Architecture A Quantitative Approach, Van Roy and Haridi's Concepts Models and Techniques of Computer Programming, Pierce's Types and Progamming Languages, or indeed even Dijkstra's A Discipline of Programming.

Nothing will ever compare to first looking into SICP, though :D.

I'm expecting some hard slogging, but it's wonderfully written thus far. A real treasure.

[Bria]

Not as much a textbook as it is a compilation of the authors' papers and other results they thought relevant. Or at least, not a textbook meant for stupid people like me who don't have a strong background in the field already. Not very much is explained very thoroughly, most proofs are expected to be easy to understand without connecting the dots, and when they do deign to spell something out for us poor souls who might possibly be struggling to follow the steps, they quickly add that this is the last time they'll do anything so base, so the reader had best instantly understand how it works from here on out. Still, it's practically the only textbook on the subject, so if you want to learn about Kolmogorov complexity in more detail than wikipedia provides, but with marginally more explanation than you get from reading original papers, I guess this is the way to go.

I should also add that the set of all times that I have looked in the index and actually found a reference to the thing I am looking for - a thing that I know they have explicitly defined and discussed somewhere in the text - is a meager set.

[Tiasa Mondol · Rating 5 out of 5]

One of the greatest books written on Information Theory.

[S. · Rating 5 out of 5]

Superb! The only real defect of text is the number of forward references it makes; it is annoying to have to jump forward because the proof of Lemma n relies on Lemma n+k which in turn relies on Lemma n+k+m. It is probable that a significant rewrite could avoid such issues, but would be more effort than it is worth. The text is otherwise nearly perfect.

[rohola zandie · Rating 4 out of 5]

This is an in depth book on information theory from the kolmogrov point of view. It requires some heavy math background but it may not be ideal for someone who is looking for applications