
An introduction to Kolmogorov complexity and its applications
Ming Li, Paul Vitanyi · 1993
Mathematics and physics › Feynman and physics
#4,164 most recommended
Hacker News
10
mentions by 10 people · top 29% of 15,732 books
Open Library
5.00★★★★★★★★★★
1 rating · 5 want to read
Wikipedia
—
No article yet
About the book
The book covers Kolmogorov complexity, the length of the shortest program that produces a given object, and the theory built around it. It is written to be self-contained, first developing the mathematics and computability background it needs, then presenting the theory and its uses in computer science, statistics, physics, and philosophy. Its central claim is that the compressibility of an object measures its regularity in a way that does not depend on any particular machine, up to an additive constant. From this it develops notions of randomness, prediction through the universal distribution, and the minimum description length principle for inductive inference. It also presents the incompressibility method as a way to prove lower bounds and average-case results in algorithms and combinatorics, while noting that Kolmogorov complexity itself cannot be computed exactly.
Written by Claude from what it knows of this book.
What Hacker News says 50% recommend · 0% critical
In the commenters’ own words
OK, here ya go. This list is, for now, just a raw dump of titles and authors. When I have some more time, I'll turn this into a proper blog post with more…
I'm sorry to say this, but your second post also doesn't really address the issue and continues to misunderstand the purpose and definitions of Kolgomorov…
What Open Library readers say 5.00 from 1 rating
- 51
- 40
- 30
- 20
- 10
- 5 want to read
- 0 reading
- 1 have read
Only 1 rating: treat the average as a hint.
What critics say, via Wikipedia
No Wikipedia article about this book yet, so no critics to quote.
Reddit communities — coming later
The threads it came up in
Details
- First published
- 1993
- ISBN
- 9783030112974
- Editions known
- 6 at Open Library
- Open Library
- OL1332298W
Kolmogorov complexity
Read next: its neighbours on the mosaic
Elements of Information TheoryT. M. Cover · 2006 · recommended by 20 people · named together in 3 comments
Introduction to the theory of computationMichael Sipser · 1997 · recommended by 66 people · 2 people recommended both
Elements of the Theory of ComputationLewis, Harry R., and Christos H. Papadimitriou · 1981 · recommended by 5 people · similar by subject and what people say about it
A Computational Introduction to Number Theory and AlgebraVictor Shoup · 2005 · recommended by 4 people · similar by subject and what people say about it
Modern graph theoryBéla Bollobás · 1998 · recommended by 3 people · similar by subject and what people say about it
Introduction to automata theory, languages, and computationJohn E. Hopcroft · 1979 · recommended by 24 people · similar by subject and what people say about it
Proofs and typesJean-Yves Girard · 1989 · recommended by 6 people · similar by subject and what people say about it
Algorithms IlluminatedTim Roughgarden · 2018 · recommended by 9 people · similar by subject and what people say about it
Introduction to probability theoryPaul Gerhard Hoel · 1971 · recommended by 7 people · similar by subject and what people say about it
Theory of computationMichael Sipser · 2007 · recommended by 14 people · similar by subject and what people say about it
Design concepts in programming languagesFranklyn A. Turbak · 2008 · recommended by 7 people · similar by subject and what people say about it
MathematicsAndrei Nikolaevich Kolmogorov · 1962 · recommended by 12 people · similar by subject and what people say about it
Foundations of the theory of probabilityAndrei Nikolaevich Kolmogorov · 1950 · recommended by 2 people · similar by subject and what people say about it
An introduction to probability theory and its applicationsWilliam Feller · 1950 · recommended by 8 people · similar by subject and what people say about it
An Introduction To Lambda Calculi For Computer ScientistsC. Hankin · 2004 · recommended by 2 people · loosely similar by subject
An introduction to information theoryJohn Robinson Pierce · 1980 · recommended by 15 people · similar by subject and what people say about it
Computational complexitySanjeev Arora · 2007 · recommended by 3 people · similar by subject and what people say about it
Computational complexityChristos H. Papadimitriou · 1994 · recommended by 7 people · similar by subject and what people say about it
Information Theory, Inference & Learning AlgorithmsDavid J.C. MacKay · 2003 · recommended by 77 people · similar by subject and what people say about it
ComputationMarvin Minsky · 1967 · recommended by 5 people · similar by subject and what people say about it
The nature of computationCristopher Moore · 2009 · recommended by 10 people · similar by subject and what people say about it
Practical foundations of mathematicsTaylor, Paul · 1999 · recommended by 4 people · similar by subject and what people say about it
Probability and ComputingMichael Mitzenmacher · 2005 · recommended by 4 people · similar by subject and what people say about it
Basic category theory for computer scientistsBenjamin C. Pierce · 1991 · recommended by 12 people · similar by subject and what people say about it