Computability and Randomness
1st Edition
Published on 29. January 2009
450 pages
978-0-19-155227-4 (ISBN)
Description
The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts and methods originating from randomness enrich computability theory. The book covers topics such as lowness and highness properties, Kolmogorov complexity, betting strategies and higher computability. Both the basics and recent research results are desribed, providing a very readable introduction to the exciting interface of computability and randomness for graduates and researchers in computability theory, theoretical computer science, and measure theory.
More details
Other editions
Additional editions
Andre Nies
Computability and Randomness
Book
01/2009
Oxford University Press
€176.42
Shipment within 15-20 days
Content
- Intro
- Contents
- 1 The complexity of sets
- 1.1 The basic concepts
- Partial computable functions
- Computably enumerable sets
- Indices and approximations
- 1.2 Relative computational complexity of sets
- Many-one reducibility
- Turing reducibility
- Relativization and the jump operator
- Strings over {0, 1}
- Approximating the functionals F[sub(e)], and the use principle
- Weak truth-table reducibility and truth-table reducibility
- Degree structures
- 1.3 Sets of natural numbers
- 1.4 Descriptive complexity of sets
- ?[sup(0)][sub(2)]sets and the Shoenfield Limit Lemma
- Sets and functions that are n-c.e. or ?-c.e.
- Degree structures on particular classes *
- The arithmetical hierarchy
- 1.5 Absolute computational complexity of sets
- Sets that are low[sub(n)]
- Computably dominated sets
- Sets that are high[sub(n)]
- 1.6 Post's problem
- Turing incomparable ?[sup(0)][sub(2)]-sets
- Simple sets
- A c.e. set that is neither computable nor Turing complete
- Is there a natural solution to Post's problem?
- Turing incomparable c.e. sets
- 1.7 Properties of c.e. sets
- Each incomputable c.e. wtt-degree contains a simple set
- Hypersimple sets
- Promptly simple sets
- Minimal pairs and promptly simple sets
- Creative sets *
- 1.8 Cantor space
- Open sets
- Binary trees and closed sets
- Representing open sets
- Compactness and clopen sets
- The correspondence between subsets of N and real numbers
- Effectivity notions for real numbers
- Effectivity notions for classes of sets
- Examples of II[sup(0)][sub(1)] classes
- Isolated points and perfect sets
- The Low Basis Theorem
- The basis theorem for computably dominated sets
- Weakly 1-generic sets
- 1-generic sets
- The arithmetical hierarchy of classes
- Comparing Cantor space with Baire space
- 1.9 Measure and probability
- Outer measures
- Measures
- Uniform measure and null classes
- Uniform measure of arithmetical classes
- Probability theory
- 2 The descriptive complexity of strings
- Comparing the growth rate of functions
- 2.1 The plain descriptive complexity C
- Machines and descriptions
- The counting condition, and incompressible strings
- Invariance, continuity, and growth of C
- Algorithmic properties of C
- 2.2 The prefix-free complexity K
- Drawbacks of C
- Prefix-free machines
- The Machine Existence Theorem and a characterization of K
- The Coding Theorem
- 2.3 Conditional descriptive complexity
- Basics
- An expression for K (x,y) *
- 2.4 Relating C and K
- Basic interactions
- Solovay's equations *
- 2.5 Incompressibility and randomness for strings
- Comparing incompressibility notions
- Randomness properties of strings
- 3 Martin-Löf randomness and its variants
- 3.1 A mathematical definition of randomness for sets
- Martin-Löf tests and their variants
- Schnorr's Theorem and universal Martin-Löf tests
- The initial segment approach
- 3.2 Martin-Löf randomness
- The test concept
- A universal Martin-Löf test
- Characterization of MLR via the initial segment complexity
- Examples of Martin-Löf random sets
- Facts about ML-random sets
- Left-c.e. ML-random reals and Solovay reducibility
- Randomness on reals, and randomness for bases other than 2
- A nonempty II[sup(0)][sub(1)] subclass of MLR has ML-random measure *
- 3.3 Martin-Löf randomness and reduction procedures
- Each set is weak truth-table reducible to a ML-random set
- Autoreducibility and indifferent sets *
- 3.4 Martin-Löf randomness relative to an oracle
- Relativizing C and K
- Basics of relative ML-randomness
- Symmetry of relative Martin-Löf randomness
- Computational complexity, and relative randomness
- The halting probability O relative to an oracle *
- 3.5 Notions weaker than ML-randomness
- Weak randomness
- Schnorr randomness
- Computable measure machines
- 3.6 Notions stronger than ML-randomness
- Weak 2-randomness
- 2-randomness and initial segment complexity
- 2-randomness and being low for O
- Demuth randomness *
- 4 Diagonally noncomputable functions
- 4.1 D.n.c. functions and sets of d.n.c. degree
- Basics on d.n.c. functions and fixed point freeness
- The initial segment complexity of sets of d.n.c. degree
- A completeness criterion for c.e. sets
- 4.2 Injury-free constructions of c.e. sets
- Each ?[sup(0)][sub(2)] set of d.n.c. degree bounds a promptly simple set
- Variants of Kucera's Theorem
- An injury-free proof of the Friedberg-Muchnik Theorem *
- 4.3 Strengthening the notion of a d.n.c. function
- Sets of PA degree
- Martin-Löf random sets of PA degree
- Turing degrees of Martin-Löf random sets *
- Relating n-randomness and higher fixed point freeness
- 5 Lowness properties and K-triviality
- 5.1 Equivalent lowness properties
- Being low for K
- Lowness for ML-randomness
- When many oracles compute a set
- Bases for ML-randomness
- Lowness for weak 2-randomness
- 5.2 K-trivial sets
- Basics on K-trivial sets
- K-trivial sets are ?[sup(0)][sub(2)]
- The number of sets that are K-trivial for a constant b *
- Closure properties of K
- C-trivial sets
- Replacing the constant by a slowly growing function *
- 5.3 The cost function method
- The basics of cost functions
- A cost function criterion for K-triviality
- Cost functions and injury-free solutions to Post's problem
- Construction of a promptly simple Turing lower bound
- K-trivial sets and S[sub(1)]-induction *
- Avoiding to be Turing reducible to a given low c.e. set
- Necessity of the cost function method for c.e. K-trivial sets
- Listing the (?-c.e.) K-trivial sets with constants
- Adaptive cost functions
- 5.4 Each K-trivial set is low for K
- Introduction to the proof
- The formal proof of Theorem 5.4.1
- 5.5 Properties of the class of K-trivial sets
- A Main Lemma derived from the golden run method
- The standard cost function characterizes the K-trivial sets
- The number of changes *
- O[sup(A)] for K-trivial A
- Each K-trivial set is low for weak 2-randomness
- 5.6 The weak reducibility associated with Low(MLR)
- Preorderings coinciding with LR-reducibility
- A stronger result under the extra hypothesis that A =[sub(T)] B'
- The size of lower and upper cones for =[sub(LR)] *
- Operators obtained by relativizing classes
- Studying =[sub(LR)] by applying the operator K
- Comparing the operators S[sub(LR)] and K *
- Uniformly almost everywhere dominating sets
- Ø' =[sub(LR)] C if and only if C is uniformly a.e. dominating
- 6 Some advanced computability theory
- 6.1 Enumerating Turing functionals
- Basics and a first example
- C.e. oracles, markers, and a further example
- 6.2 Promptly simple degrees and low cuppability
- C.e. sets of promptly simple degree
- A c.e. degree is promptly simple iff it is low cuppable
- 6.3 C.e. operators and highness properties
- The basics of c.e. operators
- Pseudojump inversion
- Applications of pseudojump inversion
- Inversion of a c.e. operator via a ML-random set
- Separation of highness properties
- Minimal pairs and highness properties *
- 7 Randomness and betting strategies
- 7.1 Martingales
- Formalizing the concept of a betting strategy
- Supermartingales
- Some basics on supermartingales
- Sets on which a supermartingale fails
- Characterizing null classes by martingales
- 7.2 C.e. supermartingales and ML-randomness
- Computably enumerable supermartingales
- Characterizing ML-randomness via c.e. supermartingales
- Universal c.e. supermartingales
- The degree of nonrandomness in ML-random sets *
- 7.3 Computable supermartingales
- Schnorr randomness and martingales
- Preliminaries on computable martingales
- 7.4 How to build a computably random set
- Three preliminary Theorems: outline
- Partial computable martingales
- A template for building a computably random set
- Computably random sets and initial segment complexity
- The case of a partial computably random set
- 7.5 Each high degree contains a computably random set
- Martingales that dominate
- Each high c.e. degree contains a computably random
- A computably random set that is not partial computably random
- A strictly computably random set in each high degree
- A strictly Schnorr random set in each high degree
- 7.6 Varying the concept of a betting strategy
- Basics of selection rules
- Stochasticity
- Stochasticity and initial segment complexity
- Nonmonotonic betting strategies
- Muchnik's splitting technique
- Kolmogorov-Loveland randomness
- 8 Classes of computational complexity
- 8.1 The class Low(O)
- The Low(O) basis theorem
- Being weakly low for K
- 2-randomness and strong incompressibility K
- Each computably dominated set in Low(O) is computable
- A related result on computably dominated sets in GL[sub(1)]
- 8.2 Traceability
- C.e. traceable sets and array computable sets
- Computably traceable sets
- Lowness for computable measure machines
- Facile sets as an analog of the K-trivial sets *
- 8.3 Lowness for randomness notions
- Lowness for C-null classes
- The class Low(MLR, SR)
- Classes that coincide with Low(SR)
- Low(MLR, CR) coincides with being low for K
- 8.4 Jump traceability
- Basics of jump traceability, and existence theorems
- Jump traceability and descriptive string complexity
- The weak reducibility associated with jump traceability
- Jump traceability and superlowness are equivalent for c.e. sets
- More on weak reducibilities
- Strong jump traceability
- Strong superlowness*
- 8.5 Subclasses of the K-trivial sets
- Some K-trivial c.e. set is not strongly jump traceable
- Strongly jump traceable c.e. sets and benign cost functions
- The diamond operator
- 8.6 Summary and discussion
- A diagram of downward closed properties
- Computational complexity versus randomness
- Some updates
- 9 Higher computability and randomness
- 9.1 Preliminaries on higher computability theory
- II[sup(1)[sub(1)] and other relations
- Well-orders and computable ordinals
- Representing II[sup(1)][sub(1)] relations by well-orders
- II[sup(1)][sub(1)] classes and the uniform measure
- Reducibilities
- A set theoretical view
- 9.2 Analogs of Martin-Löf randomness and K-triviality
- II[sup(1)][sub(1)] Machines and prefix-free complexity
- A version of Martin-Löf randomness based on II[sup(1)][sub(1)] sets
- An analog of K-triviality
- Lowness for II[sup(1)][sub(1)]-ML-randomness
- 9.3 ?[sup(1)][sub(1)]-randomness and II[sup(1)][sub(1)]-randomness
- Notions that coincide with ?[sup(1)][sub(1)]-randomness
- More on II[sup(1)][sub(1)]-randomness
- 9.4 Lowness properties in higher computability theory
- Hyp-dominated sets
- Traceability
- Solutions to the exercises
- Solutions to Chapter 1
- Solutions to Chapter 2
- Solutions to Chapter 3
- Solutions to Chapter 4
- Solutions to Chapter 5
- Solutions to Chapter 6
- Solutions to Chapter 7
- Solutions to Chapter 8
- Solutions to Chapter 9
- References
- Notation Index
- Index
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- R
- S
- T
- U
- V
- W
- Y
- Z
