Synopses & Reviews
"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.
Synopsis
Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. It 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 hints to solutions of problems, as well as a great deal of new material not included in the first edition.
Table of Contents
Preliminaries.- Algorithmic Complexity.- Algorithmic Prefix Complexity.- Algorithmic Probability.- Inductive Reasoning.- The Incompressibility Method.- Resource-Bounded Complexity.- Physics, Information, and Computation