An introduction to Kolmogorov complexity and its applications (Q5915950)

See the reviews of the first, second and third editions [Zbl 0805.68063; Zbl 0866.68051; Zbl 1185.68369]. Authors' preface to the fourth edition: The area of Kolmogorov complexity or algorithmic information theory is now an established discipline. This is a corrected and expanded version of the earlier editions. From the back cover: 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 features: describes the mathematical theory of Kolmogorov complexity, 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 Kolmogorov complexity 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 Kolmogorov complexity, and examines different physical theories from a Kolmogorov complexity 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.