Amazon cover image
Image from Amazon.com
Image from Google Jackets

Algorithmic randomness and complexity

By: Contributor(s): Material type: TextTextLanguage: English Series: Theory and appications of computabilityPublication details: New york Springer 2010Description: xxviii, 855pISBN:
  • 9780387955674 (HB)
Subject(s):
Contents:
pt. I. Background. Preliminaries Computability theory Kolmogorov complexity of finite strings Relating complexities Effective reals pt. II. Notions of randomness. Martin-Löf randomness Other notions of algorithmic randomness Algorithmic randomness and Turing reducibility pt. III. Relative randomness. Measures of relative randomness Complexity and relative randomness for 1-randoms sets Randomness-theoretic weakness Lowness and triviality for other randomness notions Algorithmic dimension pt. IV. Further topics. Strong jump traceability [Omega] as an operator Complexity of computably enumerable sets. Part I. Background : 1. Preliminaries 2. Computability Theory 3. Kolmogorov Complexity of Finite Strings 4. Relating Complexities 5. Effective Reals Part II. Notions of Randomness : 6. Martin-Lof Randomness 7. Other Notions of Algorithmic Randomness 8. Algorithmic Randomness and Turing Reducibility Part III. Relative Randomness : 9. Measures of Relative Randomness 10. Complexity and Relative Randomness for 11. Randomness-Theoretic Weakness 12. Lowness and Triviality for Other Randomness Notions 13. Algorithmic Dimension Part IV. Further Topics : 14. Strong Jump Traceability 15. Ω as an Operator 16. Complexity of Computably Enumerable Sets
Summary: The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory.
Item type: BOOKS
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Home library Call number Materials specified Status Date due Barcode
IMSc Library 510.52 DOW (Browse shelf(Opens below)) Available 69918

Includes index

Includes bibliography (p. 767-796) and references

pt. I. Background. Preliminaries
Computability theory
Kolmogorov complexity of finite strings
Relating complexities
Effective reals
pt. II. Notions of randomness. Martin-Löf randomness
Other notions of algorithmic randomness
Algorithmic randomness and Turing reducibility
pt. III. Relative randomness. Measures of relative randomness
Complexity and relative randomness for 1-randoms sets
Randomness-theoretic weakness
Lowness and triviality for other randomness notions
Algorithmic dimension
pt. IV. Further topics. Strong jump traceability
[Omega] as an operator
Complexity of computably enumerable sets. Part I. Background :
1. Preliminaries
2. Computability Theory
3. Kolmogorov Complexity of Finite Strings
4. Relating Complexities
5. Effective Reals
Part II. Notions of Randomness :
6. Martin-Lof Randomness
7. Other Notions of Algorithmic Randomness
8. Algorithmic Randomness and Turing Reducibility
Part III. Relative Randomness :
9. Measures of Relative Randomness
10. Complexity and Relative Randomness for
11. Randomness-Theoretic Weakness
12. Lowness and Triviality for Other Randomness Notions
13. Algorithmic Dimension
Part IV. Further Topics :
14. Strong Jump Traceability
15. Ω as an Operator
16. Complexity of Computably Enumerable Sets

The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory.

There are no comments on this title.

to post a comment.
The Institute of Mathematical Sciences, Chennai, India