An Introduction To Kolmogorov Complexity and its Applications

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Reference

Li, M., Vitányi, P.: An Introduction To Kolmogorov Complexity and its Applications. 3nd edn. Springer, New York (2008).

DOI

http://www.springer.com/mathematics/applications/book/978-0-387-33998-6

Abstract

Develops Kolmogorov theory in detail and outlines the wide range of illustrative applications

Presents recent, major results in the field: topics include Omega numbers, Kolmogorov-Loveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, and Shannon information

Introduces results from prominent researchers in the field, such as those found by Slaman-Kucera, Downey, Hirschfeldt, Nies, Solovay, Miller and many more

Includes applications to hierarchical clustering, phylogeny in genomics, classification of music, Google, and the World Wide Web

Additional exercises on new results

Improved sections on high-probability properties and Kolmogorov’s structure function, information distance

This ongoing bestseller, now in its third edition, is considered the standard reference on Kolmogorov complexity, a modern theory of information that is concerned with information in individual objects.

New key features and topics in the 3rd edition:

  • New results on randomness
  • Kolmogorov's structure function, model selection, and MDL
  • Incompressibility method: counting unlabeled graphs, Shellsort, communication complexity
  • Derandomization
  • Kolmogorov complexity versus Shannon information, rate distortion, lossy compression, denoising
  • Theoretical results on information distance
  • The similarity metric with applications to genomics, phylogeny, clustering, classification, semantic meaning, question-answer systems
  • Quantum Kolmogorov complexity

Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in all fields of science. It is self-contained: it contains the basic requirements from mathematics, probability theory, statistics, information theory, and computer science. Included are history, theory, new developments, a wide range of applications, numerous (new) problem sets, comments, source references, and hints to solutions of problems. This is the only comprehensive treatment of the central ideas of Kolmogorov complexity and their applications.

Extended Abstract

Reviews

Bibtex

Table of contents

Preface to the First Edition . . . . . . . . . . . . . . . . . . . . vii Preface to the Second Edition . . . . . . . . . . . . . . . . . . xi Preface to the Third Edition . . . . . . . . . . . . . . . . . . . xii How to Use This Book . . . . . . . . . . . . . . . . . . . . . . xii Outlines of One-Semester Courses . . . . . . . . . . . . . . . . xv Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi 1 Preliminaries 1 1.1 A Brief Introduction . . . . . . . . . . . . . . . . . . . . . 1 1.2 Prerequisites and Notation . . . . . . . . . . . . . . . . . 7 1.3 Numbers and Combinatorics . . . . . . . . . . . . . . . . 8 1.4 Binary Strings . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . 15 1.6 Basics of Probability Theory . . . . . . . . . . . . . . . . 18 1.7 Basics of Computability Theory . . . . . . . . . . . . . . 24 1.8 The Roots of Kolmogorov Complexity . . . . . . . . . . . 47 1.9 Randomness . . . . . . . . . . . . . . . . . . . . . . . . . 49 1.10 Prediction and Probability . . . . . . . . . . . . . . . . . 59 xviii Contents 1.11 Information Theory and Coding . . . . . . . . . . . . . . 65 1.12 State × Symbol Complexity . . . . . . . . . . . . . . . . 90 1.13 History and References . . . . . . . . . . . . . . . . . . . 2 Algorithmic Complexity 92 101 2.1 The Invariance Theorem . . . . . . . . . . . . . . . . . . 104 2.2 Incompressibility . . . . . . . . . . . . . . . . . . . . . . . 116 2.3 C as an Integer Function . . . . . . . . . . . . . . . . . . 126 2.4 Random Finite Sequences . . . . . . . . . . . . . . . . . . 133 2.5 *Random Infinite Sequences . . . . . . . . . . . . . . . . 143 2.6 Statistical Properties of Finite Sequences . . . . . . . . . 165 2.7 Algorithmic Properties of C 2.8 Algorithmic Information Theory . . . . . . . . . . . . . . 186 2.9 History and References . . . . . . . . . . . . . . . . . . . 192 . . . . . . . . . . . . . . . . 174 3 Algorithmic Prefix Complexity 197 3.1 The Invariance Theorem . . . . . . . . . . . . . . . . . . 200 3.2 *Sizes of the Constants . . . . . . . . . . . . . . . . . . . 206 3.3 Incompressibility . . . . . . . . . . . . . . . . . . . . . . . 211 3.4 K as an Integer Function . . . . . . . . . . . . . . . . . . 216 3.5 Random Finite Sequences . . . . . . . . . . . . . . . . . . 218 3.6 *Random Infinite Sequences . . . . . . . . . . . . . . . . 220 3.7 Algorithmic Properties of K . . . . . . . . . . . . . . . . 239 3.8 *Complexity of Complexity . . . . . . . . . . . . . . . . . 241 3.9 *Symmetry of Algorithmic Information . . . . . . . . . . 244 3.10 History and References . . . . . . . . . . . . . . . . . . . 255 4 Algorithmic Probability 259 4.1 Semicomputable Functions Revisited . . . . . . . . . . . . 260 4.2 Measure Theory . . . . . . . . . . . . . . . . . . . . . . . 262 4.3 Discrete Sample Space . . . . . . . . . . . . . . . . . . . . 265 4.4 Universal Average-Case Complexity . . . . . . . . . . . . 290 4.5 Continuous Sample Space . . . . . . . . . . . . . . . . . . 294 4.6 Universal Average-Case Complexity, Continued . . . . . . 330 4.7 History and References . . . . . . . . . . . . . . . . . . . 331 Contents 5 Inductive Reasoning xix 339 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 339 5.2 Solomonoff’s Theory of Prediction . . . . . . . . . . . . . 348 5.3 Simple Pac-Learning . . . . . . . . . . . . . . . . . . . . . 370 5.4 Hypothesis Identification by MDL . . . . . . . . . . . . . 382 5.5 Nonprobabilistic Statistics . . . . . . . . . . . . . . . . . 401 5.6 History and References . . . . . . . . . . . . . . . . . . . 431 6 The Incompressibility Method 441 6.1 Three Examples . . . . . . . . . . . . . . . . . . . . . . . 442 6.2 High-Probability Properties . . . . . . . . . . . . . . . . . 448 6.3 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . 451 6.4 Kolmogorov Random Graphs . . . . . . . . . . . . . . . . 461 6.5 Compact Routing . . . . . . . . . . . . . . . . . . . . . . 469 6.6 Average-Case Analysis of Sorting . . . . . . . . . . . . . . 476 6.7 Longest Common Subsequence . . . . . . . . . . . . . . . 486 6.8 Formal Language Theory . . . . . . . . . . . . . . . . . . 490 6.9 Online CFL Recognition . . . . . . . . . . . . . . . . . . 497 6.10 Turing Machine Time Complexity . . . . . . . . . . . . . 502 6.11 Communication Complexity . . . . . . . . . . . . . . . . 516 6.12 Circuit Complexity . . . . . . . . . . . . . . . . . . . . . 521 6.13 History and References . . . . . . . . . . . . . . . . . . . 524 7 Resource-Bounded Complexity 531 7.1 Mathematical Theory . . . . . . . . . . . . . . . . . . . . 532 7.2 Language Compression . . . . . . . . . . . . . . . . . . . 550 7.3 Computational Complexity . . . . . . . . . . . . . . . . . 562 7.4 Instance Complexity . . . . . . . . . . . . . . . . . . . . . 571 7.5 Kt and Universal Search . . . . . . . . . . . . . . . . . . . 577 7.6 Time-Limited Universal Distributions . . . . . . . . . . . 582 7.7 Logical Depth . . . . . . . . . . . . . . . . . . . . . . . . 589 7.8 History and References . . . . . . . . . . . . . . . . . . . 596 xx Contents 8 Physics, Information, and Computation 601 8.1 Information Theory . . . . . . . . . . . . . . . . . . . . . 602 8.2 Reversible Computation . . . . . . . . . . . . . . . . . . . 629 8.3 Information Distance . . . . . . . . . . . . . . . . . . . . 641 8.4 Normalized Information Distance . . . . . . . . . . . . . . 660 8.5 Thermodynamics . . . . . . . . . . . . . . . . . . . . . . . 674 8.6 Entropy Revisited . . . . . . . . . . . . . . . . . . . . . . 686 8.7 Quantum Kolmogorov Complexity . . . . . . . . . . . . . 696 8.8 Compression in Nature . . . . . . . . . . . . . . . . . . . 711 8.9 History and References . . . . . . . . . . . . . . . . . . . 714 References 723 Index 765


Links

Full Text

[extern file]

intern file

Sonstige Links

Abgerufen von „http://de.evo-art.org/index.php?title=An_Introduction_To_Kolmogorov_Complexity_and_its_Applications&oldid=1409“