Algorithmic randomness and complexity / Rodney G. Downey, Denis R. Hirschfeldt.

Format:

Book

Author/Creator:

Downey, R. G. (Rod G.)

Contributor:

Hirschfeldt, Denis Roman.

Beth & Matthew Mezvinsky Collection Fund for Modern Philosophy.

Series:

Theory and applications of computability

Theory and applications of computability, 2190-619X

Language:

English

Subjects (All):

Computational complexity.

Computable functions.

számítási bonyolultság--elmélet.

kiszámításelmélet (matematikai logika).

Local Subjects:

számítási bonyolultság--elmélet.

kiszámításelmélet (matematikai logika).

Physical Description:

xxviii, 855 pages : illustrations ; 24 cm.

Place of Publication:

New York : Springer, [2010]

Summary:

"Intuitively, a sequence such as 101010101010101010 ... does not seem random, whereas 101101011101010100 ..., obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say that an individual mathematical object such as a real number is random, or to say that one real is more random than another? And what is the relationship between randomness and computational power. 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. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science."--Publisher's website.

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

1.1. Notation and conventions

1.2. Basics from measure theory

2.1. Computable functions, coding, and the halting problem

2.2. Computable enumerability and Rice's Theorem

2.3. The Recursion Theorem

2.4. Reductions

2.4.1. Oracle machines and Turing reducibility

2.4.2. The jump operator and jump classes

2.4.3. Strong reducibilities

2.4.4. Myhill's Theorem

2.5. The arithmetic hierarchy

2.6. The Limit Lemma and Post's Theorem

2.7. The difference hierarchy

2.8. Primitive recursive functions

2.9. Anote on reductions

2.10. The finite extensionmethod

2.11. Post's Problem and the finite injury priority method

2.12. Finite injury arguments of unbounded type

2.12.1. The Sacks Splitting Theorem

2.12.2. The Pseudo-Jump Theorem

2.13. Coding and permitting

2.14. The infinite injury priority method

2.14.1. Priority trees and guessing

2.14.2. The minimal pairmethod

2.14.3. High computably enumerable degrees

2.14.4. The Thickness Lemma

2.15. The Density Theorem

2.16. Jump theorems

2.17. Hyperimmune-free degrees

2.18. Minimal degrees

2.19. 01 and Σ01 classes

2.19.1. Basics

2.19.2. 0 n and Σ 0 n classes

2.19.3. Basis theorems

2.19.4. Generalizing the low basis theorem

2.20. Strong reducibilities and Post's Program

2.21. PA degrees

2.22. Fixed-point free and diagonally noncomputable functions

2.23. Array noncomputability and traceability

2.24. Genericity and weak genericity

3.1. Plain Kolmogorov complexity

3.2. Conditional complexity

3.3. Symmetry of information

3.4. Information-theoretic characterizations of computability

3.5. Prefix-free machines and complexity

3.6. The KC Theorem

3.7. Basic properties of prefix-free complexity

3.8. Prefix-free randomness of strings

3.9. The Coding Theorem and discrete semimeasures

3.10. Prefix-free symmetry of information

3.11. Initial segment complexity of sets

3.12. Computable bounds for prefix-free complexity

3.13. Universal machines and halting probabilities

3.14. The conditional complexity of σ\* given σ

3.15. Monotone and process complexity

3.16. Continuous semimeasures and KM-complexity

4.1. Levin's Theorem relating Cand K

4.2. Solovay's Theorems relating Cand K

4.3. Strong K-randomness and C-randomness

4.3.1. Positive results

4.3.2. Counterexamples

4.4. Muchnik's Theorem on Cand K

4.5. Monotone complexity and KM-complexity

5.1. Computable and left-c.e. reals

5.2. Real-valued functions

5.3. Representing left-c.e. reals

5.3.1. Degrees of representations

5.3.2. Presentations of left-c.e. reals

5.3.3. Presentations and ideals

5.3.4. Promptly simple sets and presentations

5.4. Left-d.c.e. reals

5.4.1. Basics

5.4.2. The field of left-d.c.e. reals

6.1. The computational paradigm

6.2. Themeasure-theoretic paradigm

6.3. The unpredictability paradigm

6.3.1. Martingales and supermartingales

6.3.2. Supermartingales and continuous semimeasures

6.3.3. Martingales and optimality

6.3.4. Martingale processes

6.4. Relativizing randomness

6.5. Ville's Theorem

6.6. The Ample Excess Lemma

6.7. Plain complexity and randomness

6.8. n-randomness

6.9. Van Lambalgen's Theorem

6.10. Effective0-1 laws

6.11. Infinitely often maximally complex sets

6.12. Randomness for other measures and degree-invariance

6.12.1. Generalizing randomness to other measures

6.12.2. Computable measures and representing reals

7.1. Computable randomness and Schnorr randomness

7.1.1. Basics

7.1.2. Limitations

7.1.3. Computable measure machines

7.1.4. Computable randomness and tests

7.1.5. Bounded machines and computable randomness

7.1.6. Process complexity and computable randomness

7.2. Weak n-randomness

7.2.1. Basics

7.2.2. Characterizations of weak 1-randomness

7.2.3. Schnorr randomness via Kurtz null tests

7.2.4. Weakly 1-random left-c.e. reals

7.2.5. Solovay genericity and randomness

7.3. Decidable machines

7.4. Selection revisited

7.4.1. Stochasticity

7.4.2. Partial computable martingales and stochasticity

7.4.3. Amartingale characterization of stochasticity

7.5. Nonmonotonic randomness

7.5.1. Nonmonotonic betting strategies

7.5.2. Van Lambalgen's Theorem revisited

7.6. Demuth randomness

7.7. Difference randomness

7.8. Finite randomness

7.9. Injective and permutation randomness

8.1. 01 classes of 1-randomsets

8.2. Computably enumerable degrees

8.3. The Kucera-Gacs Theorem

8.4. A "no gap" theorem for 1-randomness

8.5. Kucera coding

8.6. Demuth's Theorem

8.7. Randomness relative to other measures

8.8. Randomness and PA degrees

8.9. Mass problems

8.10. DNC degrees and subsets of random sets

8.11. High degrees and separating notions of randomness

8.11.1. High degrees and computable randomness

8.11.2. Separating notions of randomness

8.11.3. When van Lambalgen's Theorem fails

8.12. Measure theory and Turing reducibility

8.13. n-randomness and weak n-randomness

8.14. Every 2-random set is GL 1

8.15. Stillwell's Theorem

8.16. DNC degrees and autocomplexity

8.17. Randomness and n-fixed-point freeness

8.18. Jump inversion

8.19. Pseudo-jump inversion

8.20. Randomness and genericity

8.20.1. Similarities between randomness and genericity

8.20.2. n-genericity versus n-randomness

8.21. Properties of almost all degrees

8.21.1. Hyperimmunity

8.21.2. Bounding 1-generics

8.21.3. Every 2-random set is CEA

8.21.4. Where 1-generic degrees are downward dense

Part III. Relative Randomness :

9.1. Solovay reducibility

9.2. The Kucera-Slaman Theorem

9.3. Presentations of left-c.e. reals and complexity

9.4. Solovay functions and 1-randomness

9.5. Solovay degrees of left-c.e. reals

9.6. cl-reducibility and r K-reducibility

9.7. K-reducibility and C-reducibility

9.8. Density and splittings

9.9. Monotone degrees and density

9.10. Further relationships between reducibilities

9.11. Aminimal r K-degree

9.12. Complexity and completeness for left-c.e. reals

9.13. cl-reducibility and the Kucera-Gacs Theorem

9.14. Further properties of cl-reducibility

9.14.1. cl-reducibility and joins

9.14.2. Array noncomputability and joins

9.14.3. Left-c.e. reals cl-reducible to versions of Ω

9.14.4. cl-degrees of versions of Ω

9.15. K-degrees, C-degrees, and Turing degrees

9.16. The structure of the monotone degrees

9.17. Schnorr reducibility

10.1. Uncountable lower cones in Kand C

10.2. The K-complexity of Ω and other 1-random sets

10.2.1. K(A n) versus K(n) for 1-random sets A

10.2.2. The rate of convergence of Ω and the α function

10. Complexity and Relative Randomness for 1-Randoms Sets

10.2.3. Comparing complexities of 1-random sets

10.2.4. Limit complexities and relativized complexities

10.3. Van Lambalgen reducibility

10.3.1. Basic properties of the van Lambalgen degrees

10.3.2. Relativized randomness and Turing reducibility

10.3.3. v L-reducibility, K-reducibility, and joins

10.3.4. v L-reducibility and C-reducibility

10.3.5. Contrasting v L-reducibility and K-reducibility

10.4. Upward oscillations and K-comparable1-random sets

10.5. LR-reducibility

10.6. Almost everywhere domination

11.1. K-triviality

11.1.1. The basic K-triviality construction

11.1.2. The requirement-free version

11.1.3. Solovay functions and K-triviality

11.1.4. Counting the K-trivial sets

11.2. Lowness

11.3. Degrees of K-trivial sets

11.3.1. Afirst approximation: wtt-incompleteness

11.3.2. Asecond approximation: impossible constants

11.3.3. The less impossible case

11.4. K-triviality and lowness

11.5. Cost functions

11.6. The ideal of K-trivial degrees

11.7. Bases for 1-randomness

11.8. ML-covering, ML-cupping, and related notions

11.9. Lowness for weak 2-randomness

11.10. Listing the K-trivial sets

11.11. Upper bounds for the K-trivial sets

11.12. Agap phenomenon for K-triviality

12.1. Schnorr lowness

12.1.1. Lowness for Schnorr tests

12.1.2. Lowness for Schnorr randomness

12.1.3. Lowness for computable measure machines

12.2. Schnorr triviality

12.2.1. Degrees of Schnorr trivial sets

12.2.2. Schnorr triviality and strong reducibilities

12.2.3. Characterizing Schnorr triviality

12.3. Tracing weak truth table degrees

12.3.1. Basics

12.3.2. Reducibilities with tiny uses

12.3.3. Anti-complex sets and tiny uses

12.3.4. Anti-complex sets and Schnorr triviality

12.4. Lowness for weak genericity and randomness

12.5. Lowness for computable randomness

12.6. Lowness for pairs of randomness notions

13.1. Classical Hausdorffdimension

13.2. Hausdorffdimension via gales

13.3. Effective Hausdorffdimension

13.4. Shiftcomplex sets

13.5. Partial randomness

13.6. Acorrespondence principle for effective dimension

13.7. Hausdorffdimension and complexity extraction

13.8. A Turing degree of nonintegral Hausdorffdimension

13.9. DNC functions and effective Hausdorffdimension

13.9.1. Dimension in h-spaces

13.9.2. Slow-growing DNC functions and dimension

13.10. C-independence and Zimand's Theorem

13.11. Other notions of dimension

13.11.1. Box counting dimension

13.11.2. Effective box counting dimension

13.11.3. Packing dimension

13.11.4. Effective packing dimension

13.12. Packing dimension and complexity extraction

13.13. Clumpy trees and minimal degrees

13.14. Building sets of high packing dimension

13.15. Computable dimension and Schnorr dimension

13.15.1. Basics

13.15.2. Examples of Schnorr dimension

13.15.3. Amachine characterization of Schnorr dimension

13.15.4. Schnorr dimension and computable enumerability

13.16. The dimensions of individual strings

14.1. Basics

14.2. The ideal of strongly jump traceable c.e. sets

14.3. Strong jump traceability and K-triviality: the c.e. case

14.4. Strong jump traceability and diamond classes

14.5. Strong jump traceability and K-triviality: the general case

15.1. Introduction

15.2. Omega operators

15.3. A-1-random A-left-c.e. reals

15.4. Reals in the range of some Omega operator

15.5. Lowness for Ω

15.6. Weak lowness for K

15.6.1. Weak lowness for Kand lowness for Ω

15.6.2. Infinitely often strongly K-randomsets

15.7. When ΩA is a left-c.e. real

15.8. ΩA for K-trivial A

15.9. K-triviality and left-d.c.e. reals

15.10. Analytic behavior of Omega operators

16.1. Barzdins' Lemma and Kummer complex sets

16.2. The entropy of computably enumerable sets

16.3. The collection of nonrandom strings

16.3.1. The plain and conditional cases

16.3.2. The prefix-free case

16.3.3. The overgraphs of universal monotone machines

16.3.4. The strict process complexity case.

Notes:

Includes bibliographical references (pages 767-795) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Beth & Matthew Mezvinsky Collection Fund for Modern Philosophy.

ISBN:

9780387955674

0387955674

OCLC:

692704397

Online:

Publisher description