An Introduction to Kolmogorov Complexity and Its Applications

by Ming Li

This must-read textbook presents an essential introduction to Kolmogorov complexity (KC), a central theory and powerful tool in information science that deals with the quantity of information in individual objects. The text covers both the fundamental concepts and the most important practical applications, supported by a wealth of didactic features. This thoroughly revised and enhanced fourth edition includes new and updated material on, amongst other topics, the Miller-Yu theorem, the Gács-Kučera theorem, the Day-Gács theorem, increasing randomness, short lists computable from an input string containing the incomputable Kolmogorov complexity of the input, the Lovász local lemma, sorting, the algorithmic full Slepian-Wolf theorem for individual strings, multiset normalized information distance and normalized web distance, and conditional universal distribution.Topics and describes the mathematical theory of KC, including the theories of algorithmic complexity and algorithmic probability; presents a general theory of inductive reasoning and its applications, and reviews the utility of the incompressibility method; covers the practical application of KC in great detail, including the normalized information distance (the similarity metric) and information diameter of multisets in phylogeny, language trees, music, heterogeneous files, and clustering; discusses the many applications of resource-bounded KC, and examines different physical theories from a KC point of view; includes numerous examples that elaborate the theory, and a range of exercises of varying difficulty (with solutions); offers explanatory asides on technical issues, and extensive historical sections; suggests structures for several one-semester courses in the preface. As the definitive textbook on Kolmogorov complexity, this comprehensive and self-contained work is an invaluable resource for advanced undergraduate students, graduate students, and researchers in all fields of science.

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

818 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