An Introduction to Kolmogorov Complexity and Its Applications

Front Cover
Springer Science & Business Media, 1997 - Computers - 637 pages
4 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.
  

What people are saying - Write a review

User Review - Flag as inappropriate

This is a great book. See reviews on Amazon.

Contents

Preliminaries
1
12 Prerequisites
6
13 Numbers and Combinaorics
8
14 Binary Stings
12
15 Asymptotic Notation
15
16 Basics of Probability Theory
18
17 Basics of Computability Theory
24
18 The Roots of Kolmogorov Complexity
47
Inductive Reasoning
315
52 Solomonoffs Theory of Prediction
324
53 Universal Recursion Induction
335
54 Simple PacLearning
339
55 Hypothesis Identification by Minimum Description Length
351
56 History and References
372
The Incompressibility Method
379
61 Three Examples
380

19 Randomness
49
110 Prediction and Probability
59
111 Information Theory and Coding
65
112 State x Symbol Complexity
84
113 History and References
86
Algorithmic Complexity
93
21 The Invariance Theorem
96
22 Incompressibility
108
23 C as an Integer Function
119
24 Random Finite Sequences
127
25 Random Infinite Sequences
136
26 Statistical Properties of Finite Sequences
158
27 Algorithmic Properties of C
167
28 Algoithmic Information Theory
179
29 History and References
185
Algorithmic Prefix Complexity
189
31 The Invariance Theorem
192
32 Sizes of the Constants
197
33 Incompressibility
202
34 K as an Integer Function
206
35 Random Finite Sequences
208
36 Random Infinite Sequences
211
37 Algorithmic Properties of K
224
38 Complexity of Complexity
226
39 Symmetry of Algorithmic Information
229
310 History and References
237
Algorithmic Probability
239
41 Enumerable Functions Revisited
240
42 Nonclassical Notation of Measures
242
43 Discrete Sample Space
245
44 Universal AverageCase Complexity
268
45 Continuous Sample Space
272
Universal AverageCase Complexity Continued
307
62 HighProbability Properties
385
63 Combinatorics
389
Graphs
396
65 Compact Routing
404
66 AverageCase Complexity of Heapsort
412
67 Longest Common Subsequence
417
68 Formal Language Theory
420
69 Online CFL Recognition
427
610 Turing Machine Time Complexity
432
611 Parallel Computation
445
612 Switching Lemma
449
613 History and References
452
ResourceBounded Complexity
459
71 Mathematical Theory
460
72 Language Compression
476
73 Computational Complexity
488
74 Instance Complexity
495
75 Kt Complexity and Universal Optimal Search
502
76 TimeLimited Universal Distributions
506
77 Logical Depth
510
78 History and References
516
Physics Information and Computation
521
81 Algorithmic Complexity and Shannons Entropy
522
82 Reversible Computation
528
83 Information Distance
537
84 Thermodynamics
554
85 Entropy Revisited
565
86 Compression in Nature
583
87 History and References
586
References
591
Index
618
Copyright

Common terms and phrases

References to this book

All Book Search results »

About the author (1997)

Dr. Ming Li is a recognized expert in the field of theoretical computer science and an authoritative writer on computer learning theory, mathematical systems, foundations of computer science, complexity theory and more. Ming Li and co-author Paul Vitanyi have written a well respected text in An Introduction To Kolmogorov Complexity and Its Applications (1997). This book discusses randomness and the theory that an object's complexity is determined by how briefly it can be described. Aimed at advanced students, researchers, and practitioners in the fields of computer science, mathematics, cognitive sciences, artificial intelligence, statistics, and related fields, chapters address subjects such as algorithmic complexity and probability, inductive reasoning, and physics. Problem sets are included. In addition to contributing to Algorithmic Learning Theory, the proceeds of an International Workshop in Sendai, Japan (1997), Li has written numerous technical articles for professional journals and served as editor for The Journal of Computer and System Sciences, Information and Computation, Journal of Combinatorial Optimization, and Theoretical Computer Science. Ming Li was born July 16, 1955 in Beijing, China. He earned his Ph.D. at Cornell University in 1985. Li is a professor of computer science at Waterloo University, Ontario, Canada and a frequent presenter at international conferences and symposiums.

Bibliographic information