An Introduction to Kolmogorov Complexity and Its Applications
Springer (Publisher)
2nd Edition
Published on 27. February 1997
Book
Hardback
XX, 637 pages
978-0-387-94868-3 (ISBN)
Article exhausted; check for reprint
Description
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).
More details
Series
Edition
2nd ed.
Language
English
Place of publication
NY
United States
Target group
College/higher education
Professional and scholarly
Edition type
Revised edition
Illustrations
8
4 s/w Tabellen, 8 s/w Abbildungen
41 illus.
Dimensions
Height: 23.5 cm
Width: 17.8 cm
Weight
1240 gr
ISBN-13
978-0-387-94868-3 (9780387948683)
DOI
10.1007/978-1-4757-2606-0
Schweitzer Classification
Other editions
New editions

Ming Li | Paul Vitányi
An Introduction to Kolmogorov Complexity and Its Applications
Book
06/2019
4th Edition
Springer
€106.99
Shipment within 7-9 days

Ming Li | Paul M.B. Vitányi
An Introduction to Kolmogorov Complexity and Its Applications
Book
11/2008
3rd Edition
Springer
€90.94
Article exhausted; check for reprint
Additional editions

Ming Li | Paul Vitanyi
An Introduction to Kolmogorov Complexity and Its Applications
E-Book
03/2013
2nd Edition
Springer
€85.59
Available for download
Previous edition
Ming Li | Paul Vitanyi
An Introduction to Kolmogorov Complexity and Its Applications
Book
05/1994
Springer
€59.75
Article exhausted; check for reprint
Content
1 Preliminaries.- 2 Algorithmic Complexity.- 3 Algorithmic Prefix Complexity.- 4 Algorithmic Probability.- 5 Inductive Reasoning.- 6 The Incompressibility Method.- 7 Resource-Bounded Complexity.- 8 Physics, Information, and Computation.- References.