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, Nonfiction, Technology, Science

637 pages, Paperback

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.

[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