Computability and randomness

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 functional &cyrillic;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

δ02 sets and the Shoenfield Limit Lemma

Sets and functions that are n-c.e. or w-c.e.

Degree structures on particular classes *

The arithmetical hierarchy

1.5. Absolute computational complexity of sets

Sets that are lown

Computably dominated sets

Sets that are highn

1.6. Post's problem

Turing incomparable δ02 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 ?01 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 ?01 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 ? 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 Ω

Demuth randomness *

4. Diagonally noncomputable functions

4.1. D.n.c functions and sets of d.n.c degree

Basics on d.n.c function and fixed point freeness

Tie 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 δ02 set of d.n.c. degree bounds a promptly simple set

Variants of Ku?era' 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 δ02

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 hound

K- trivial sets and Σ1-induction *

Avoiding to he Turing reducible to a given low c.e. set

Necessity of the cost function method for c.e. K- trivial sets

Listing the (w-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 *

Ω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 &lessthanequal;T B'

The size of lower and upper corns for &lessthanequal;LR *

Operators obtained by relativizing classes

Studying &lessthanequal;LR by applying the operator K

Comparing the operators SLR and K *

Uniformly almost everywhere dominating sets

Ø? &lessthanequal;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 cuppabitity

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 left-c.e. set

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(Ω)

The Low(Ω) basis theorem

Being weakly low for K

2-randomness and strong incompreasibility k

Each computably dominated set in Low(Ω) is computable

A related result on computably dominated sets in GL1

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 (MIR, 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

&PE;11 and other relations

Well-orders and computable ordinals

Representing ?11 relations by well-orders

&PE;11 classes and the uniform measure

Reducibilities

A Mil theoretical view

9.2. Analogs of Martin-Lüf randomness and K-triviality

&PE;11 Machines and prefix-free complexity

A version of Martin-Lüf randomness based on ?11 sets

An analog of K-triviality

Lowness for &PE;11-ML-randomness

9.3. δ11- randomness and &PE;11- randomness

Notions that coincide with δ11-randomness

More on &PE;11-randomness

9.4. Lowness properties in higher computability theory

Hyp-dominated sets

Traceability

Solutions to the exercises

Solutions to Chanter 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