An Introduction to Kolmogorov Complexity and Its Applications

by Li Ming, Paul Vitányi

With this book, the authors are trying to present in a unified treatment an introduction to the central ideas and their applications of the Kolmogorov Complexity, the theory dealing with the quantity of information in individual objects. This book is appropriate for either a one- or two-semester introductory course in departments of computer science, mathematics, physics, probability theory and statistics, artificial intelligence, and philosophy. Although the mathematical theory of Kolmogorov complexity contains sophisticated mathematics, the amount of math one needs to know to apply the notions in widely divergent areas, is very little. The authors' purpose is to develop the theory in detail and outline a wide range of illustrative applications. This book is an attempt to grasp the mass of fragmented knowledge of this fascinating theory. Chapter 1 is a compilation of material on the diverse notations and disciplines we draw upon in order to make the book self-contained. The mathematical theory of Kolmogorov complexity is treated in chapters 2-4; the applications are treated in chapters 4-8.

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

546 pages, Hardcover

First published May 6, 1993

About the author

There is more than one author with this name

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