An Introduction to Kolmogorov complexity and its applications (Google eBook)

Li, Ming

Springer, 1997 - Computers - 637 pages

"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

User Review -

This is a great book. See reviews on Amazon.

Review: An Introduction to Kolmogorov Complexity and Its Applications

User Review  - Nick Black - Goodreads

I'm more excited about this than any textbook I've read all year. It's absolutely awesome thus far. Kolmogorov complexity is so deep in computer science -- in a way, I feel that it *is* computer ...

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
• 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
• 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
• 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

About the author

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

• Title: An Introduction to Kolmogorov complexity and its applications; Graduate texts in computer science
• Author: Li, Ming
• Contributor: Paul M. B. Vitanyi
• Edition: 2, illustrated
• Publisher: Springer, 1997
• ISBN: 0387948686, 9780387948683
• Length: 637 pages
• Subjects: Computers / Computer Science