An Introduction to Kolmogorov Complexity and Its Applications

Front Cover
Springer Science & Business Media, Feb 27, 1997 - Mathematics - 637 pages
4 Reviews
Briefly, we review the basic elements of computability theory and prob ability theory that are required. Finally, in order to place the subject in the appropriate historical and conceptual context we trace the main roots of Kolmogorov complexity. This way the stage is set for Chapters 2 and 3, where we introduce the notion of optimal effective descriptions of objects. The length of such a description (or the number of bits of information in it) is its Kolmogorov complexity. We treat all aspects of the elementary mathematical theory of Kolmogorov complexity. This body of knowledge may be called algo rithmic complexity theory. The theory of Martin-Lof tests for random ness of finite objects and infinite sequences is inextricably intertwined with the theory of Kolmogorov complexity and is completely treated. We also investigate the statistical properties of finite strings with high Kolmogorov complexity. Both of these topics are eminently useful in the applications part of the book. We also investigate the recursion theoretic properties of Kolmogorov complexity (relations with Godel's incompleteness result), and the Kolmogorov complexity version of infor mation theory, which we may call "algorithmic information theory" or "absolute information theory. " The treatment of algorithmic probability theory in Chapter 4 presup poses Sections 1. 6, 1. 11. 2, and Chapter 3 (at least Sections 3. 1 through 3. 4).
 

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