12 Review of classical algorithmic randomness

We assume familiarity with the classical theory of algorithmic randomness and give a review of the subject in this chapter. For details see [111] and [24].

12.1 Randomness via measure theory

Intuitively, a random real should pass every feasible statistical test. This is the motivation for using measure theory to define randomness. In the language of measure theory, a test is associated with a null set. The following is a summary of the key notions of measure-theoretic randomness.

12.1.1 Kurtz and Schnorr randomness

The notion of (now called) Kurtz randomness was introduced in Kurtz [79].

Definition 12.1.1.

(i)A set A ⊆ 2ω is a Kurtz test if it is and μ(A) = 0;

(ii)a real x is Kurtz random if x ∉ A for every Kurtz test A.

Definition 12.1.2 (Schnorr [125] and [127]).

(i)A sequence of open sets {Un}n<ω is a Schnorr test if {(n, σ)| σ ∈ Un} is r.e. and μ(Un) = 2−n for every n < ω;

(ii)a real x is Schnorr random if for every Schnorr test {Un}n<ω.

Proposition 12.1.3 (Terwijn and Zambella [163]). A real x is Schnorr random if and only if for every sequence of open sets {Vn}n<ω such that {(n, σ)| σ ∈ Vn} is r.e. and μ(Vn) = 2−f(n) for some recursive function f.

12.1.2 Martin-Löf randomness

The notions of Kurtz and Schnorr randomness both turn out to be somewhat restrictive and unsatisfactory. The next notion, due to Martin-Löf, is perhaps the most widely studied to-date.

Definition 12.1.4 (Martin-Löf [96]).

(i)A sequence of open sets {Un}n<ω is a Martin-Löf test if {(n, σ)| σ ∈ Un} is r.e. and μ(Un) < 2−n for every n < ω;

(ii)a real x is Martin-Löf random if for every Martin-Löf test {Un}n<ω.

The next result says that Martin-Löf randomness is decided by a single test.

Proposition 12.1.5 (Martin-Löf [96]). There exists a universal Martin-Löf test. Namely, there is a Martin-Löf test {Un}n<ω such that for every Martin-Löf test {Vn}n<ω.

12.1.3 Strong Martin-Löf randomness

Definition 12.1.6 (Kurtz [79]).

(ii)A sequence of open sets {Un}n<ω is a generalized Martin-Löf test if {(n, σ)| σ ∈ Un} is r.e. and limn→∞ μ(Un) = 0;

(ii)a real x is strongly Martin-Löf random if for any generalized Martin-Löf test {Un}n<ω.

Strong Martin-Löf randomness has a number of regularity properties not shared by Martin-Löf randomness.

12.1.4 Relativized randomness

Each of the notions above may be relativized to an arbitrary real x. For example, an x-Martin-Löf test is a sequence of open sets {Un}n<ω such that {(n, σ)| σ ∈ Un} is xr.e. and μ(Un) < 2−n for every n ∈ ω. Then z is x-Martin-Löf random if for any x-Martin-Löf test {Un}n<ω. In particular, z is n-random if z is ø(n−1)-Martin-Löf random.

The following is known as van Lambalgen’s Theorem.

Theorem 12.1.7 (van Lambalgen [165]). x ⊕ y is Martin-Löf random if and only if x is Martin-Löf random and y is x-Martin-Löf random, and also if and only if y is Martin-Löf random and x is y-Martin-Löf random.

Martin-Löf randomness seems to be the only randomness notion for which van Lambalgen’s Theorem holds.

12.1.5 Relative strengths of randomness notions

The relative strengths of the notions of randomness introduced above may be summarized as follows. Note that the implications do not reverse:

A real x is recursively dominated if every function f ≤T x is dominated by a recursive function. The following result gives a characterization of strong Martin-Löf randomness for recursively dominated reals.

Proposition 12.1.8 (Yu). If x is recursively dominated, then x is strongly Martin-Löf random if and only if it is Kurtz random.

Next is a characterization of Martin-Löf randomness in terms of Schnorr randomness.

Theorem 12.1.9 (Nies, Terwijn and Stephan [112]). For any real x,

(i)if x is Schnorr random and , then x is Martin-Löf random;

(ii)if , then there is a Schnorr random real y ≡T x such that y is not Martin-Löf random.

12.1.6 The computational power of random reals

The following theorem says that random reals may have very strong computational power:

Theorem 12.1.10 (Kučera [76]). For any real x ≥T ø′, there is a Martin-Löf random real z ≡T x.

Rather unexpectedly, strong Martin-Löf randomness does not yield the same conclusion:

Theorem 12.1.11 (Downey, Nies, Weber, Yu [23] and Hirschfeldt, Miller). A real x is strongly Martin-Löf random if and only if x is Martin-Löf random and Turing computes no nonrecursive -real.

In algorithmic randomness theory, there is a thesis which states that more randomness means less computational power. Although a random real x contains much information, the information may be computationally useless in the sense that it cannot be used to predicate any set except the set x itself. There is much evidence in the literature to support this thesis. We give some examples.

Definition 12.1.12. Let h be a function. A real x is h-diagonally nonrecursive, abbreviated h-DNR, if there is a function f ≤T x such that f(e) ≠ Φe(e) and f(e) < h(e) for every e < ω. We say that x is DNR if there is a function f ≤T x such that f(e) ≠ Φe(e) for e < ω.

The next theorem implies that no incomplete Martin-Löf random real is 2-DNR.

Theorem 12.1.13 (Stephan). Suppose that x ∈ 2ω is Martin-Löf random. Then x is 2-DNR if and only if x ≥T ′.

Theorem 12.1.13 has an interesting consequence. By the Low Basis Theorem (Exercise 1.5.3), there is a real x which is 2-DNR and x′ ≡T ′. By Proposition 12.1.5, there is a nonempty set which contains only Martin-Löf random reals. Then there is a Martin-Löf random real z ≤T x since every 2-DNR real Turing computes a member of any given nonempty -set. By Theorem 12.1.13, there is no random real Turing equivalent to x. Thus we have the following:

Theorem 12.1.14 (Kučera [76]). The collection of Turing degrees of Martin-Löf random reals is not upward closed.

On the other hand, the Turing degrees of Martin-Löf random reals may be downward closed, as implied by the following.

Theorem 12.1.15 (Demuth [20]). Any y >T that is truth-table reducible to a Martin-Löf random real is Turing equivalent to a Martin-Löf random real.

Clearly every real Turing reducible to any recursively dominated x is tt-reducible to x. Hence the collection of Turing degrees of Martin-Löf random reals is downward closed for random reals that are recursively dominated. The following result gives another piece of evidence for the randomness thesis.

Theorem 12.1.16 (Miller and Yu [103]). For any z, if x ≤T y are Martin-Löf random and y is z-Martin-Löf random, then so is x.

12.1.7 Exercises

Exercise 12.1.1. Prove that there is no universal Kurtz test.

Exercise 12.1.2 (Schnorr [127]). Prove that there is no universal Schnorr test.

Exercise 12.1.3 (Downey, Nies, Weber and Yu [23]). Prove that there is no universal generalized Martin-Löf test.

Exercise 12.1.4 (Merkle et al. [99], Yu [170], and Kjos-Hanssen). Prove that van Lambalgen’s Theorem fails for Schnorr randomness.

12.2 Randomness via complexity theory

Intuitively, a random real is not predicated by any partial information about itself, and no information about its content is compressible. This is the basis for defining randomness in terms of complexity.

12.2.1 Plain Kolmogorov complexity

Definition 12.2.1 (Solomonoff [146] and Kolmogorov [73]). Given a Turing machine M and a finite string σ ∈ 2<ω, the M-Kolmogorov complexity of σ, CM(σ), is min{|τ| | M(τ) = σ}.

If U is a universal Turing machine, then for any Turing machine M, there is a constant cM such that

(∀σ)(CU(σ) ≤ CM(σ)+ cM).

In other words, CU is optimal up to a constant. We drop the subscript U and use C to denote the plain Kolmogorov complexity function CU. Then one may define a real x to be random if there is a constant cx such that (∀n)(C(x ↾ n) ≥ n − cx). However, for any x and n, x ↾Code(x ↾ n) (where Code(σ) is the natural number that codes a string σ) may be obtained from a final segment (say σ) of x ↾ Code(x ↾ n) of length Code(x ↾ n) − n via U. This is because once σ is known, one may find a unique string τ such that |τ⌢σ| codes τ, i.e. |τ⌢σ|= Code(τ). Then |τ|= n and τ⌢σ = x ↾Code(x ↾ n). Thus we have the following.

Proposition 12.2.2 (Martin-Löf). For any real

Proposition 12.2.2 says that there is no random real in the sense of plain Kolmogorov complexity leading to the next definition introduced by Levin and Chaitin.

Definition 12.2.3.

(i)A set A ⊆ 2<ω is prefix-free if for any σ ≺ τ ∈ 2<ω,either σ ∉ A or τ ∉ A.

(ii)A Turing machine M is prefix-free if its domain is a prefix-free set.

Definition 12.2.4 (Levin[83] and Chaitin [9]). Given a prefix-free Turing machine M and a string σ ∈ 2<ω, the M-Kolmogorov complexity of σ, KM(σ), ismin{|τ|| M(τ) = σ}.

It is not difficult to see that there is a universal prefix-free Turing machine U and we use K(σ) to denote KU(σ). The following technical theorem points a way to constructing a prefix-free machine.

Theorem 12.2.5 (Levin[83] and Chaitin [9] and Schnorr [126]). Let {(di, τi)}i<ω ⊆ ω × 2<ω be a recursive sequence such that ∑i<ω 2−d i ≤ 1. There exist a prefix-free machine M and strings σi of length di such that M(σi) = τi for all i and Dom(M) ={σi | i < ω}. Furthermore, an index for M may be obtained effectively from an index for the sequence.

The following result summarizes some basic properties of K.

Theorem 12.2.6 (Chaitin).

(i)∑σ∈2<ω 2−K(σ) ≤ 1;

(ii)(∃c)(∀σ)(K(σ) ≤|σ|+ K(|σ|) + c);

(iii)(∃c)(∀n)(∀k)(|{σ ∈ 2n | K(σ) ≤ n + K(n) − k}| ≤ 2n−k+c).

12.2.2 Characterizing randomness via complexity

The equivalence between Martin-Löf randomness and Kolmogorov complexity is given by the following:

Theorem 12.2.7 (Schnorr). A real x is Martin-Löf random if and only if

Chaitin [9] gave a “concrete” example of a Martin-Löf random real:

and several randomness notions have been characterized in terms of Kolmogorov complexity. The next two theorems characterize Martin-Löf randomness and 2-randomness respectively in terms of plain Kolmogorov complexity.

Theorem 12.2.8 (Miller and Yu [103]). A real x is Martin-Löf random if and only if for every recursive function g with ,

Theorem 12.2.9 (Miller [101] and Nies, Stephan, Terwijn [112]). A real x is 2-random if and only if

2-randomness may also be characterized via prefix-free Kolmogorov complexity as follows:

Theorem 12.2.10 (Ding, Downey, and Yu [173] and Miller [102]). A real x is 2-random if and only if

A connection between Martin-Löf randomness and the two notions of complexity is given by the following theorem:

Theorem 12.2.11 (Miller and Yu [103]). x ⊕ y is Martin-Löf random if and only if

There is a natural way of comparing two reals in terms of plain and prefix-free complexities:

Definition 12.2.12. Write x ≤K y (resp. x ≤C y) if and only if

(resp. (∃c)(∀n)(C(x ↾ n)≤ C(y ↾ n)+ c)).

By combining van Lambalgen’s Theorem 12.1.7 and Theorem 12.2.11, we have the following conclusion.

Corollary 12.2.13 (Miller and Yu [103]). Suppose that x, y, z are Martin-Löf random. If x ≤K y or x ≤C y and x is z-Martin-Löf random, then so is y.

It is not known whether strong Martin-Löf randomness is ≤K-upward closed. By Theorem 12.1.10, Corollary 12.2.13 says that higher complexity entails stronger randomness in a set. However, the following two results hint at a more subtle picture.

Theorem 12.2.14 (Miller [102]). If x is 2-random, then |{y | x ≤K y}| = ℵ0 and |{y | x ≤C y}| = ℵ0.

Theorem 12.2.15 (Miller and Yu [104]). There are two Martin-Löf random reals x and y such that .

12.2.3 K-triviality

Definition 12.2.16. A real x is K-trivial if (∃c)(∀n)(K(x ↾ n)≤ K(n)+ c).

Thus a K-trivial real is one that is far from being random. It is immediate that every recursive real is K-trivial. However, the class of K-trivial reals includes nonrecursive members all of which are recursive in a fixed real.

Theorem 12.2.17 (Solovay [151]). There is a nonrecursive K-trivial real.

Theorem 12.2.18 (Nies [110]). If x is K-trivial, then x′ ≤tt ′.

Theorem 12.2.19 (Kučera and Slaman [77]). There is an x with x′ ≡T ′ which computes every K-trivial real.

12.2.4 Exercises

Exercise 12.2.1 (Miller and Yu [103]). Prove that a real x is Martin-Löf random if and only if .

Exercise 12.2.2. Prove that neither Kurtz randomness nor Schnorr randomness are ≤K-upward closed.

Exercise 12.2.3 (Chaitin [10]). Prove that there is no nonrecursive real x such that (∃c)(∀n)(C (x ↾ n)≤ C (n)+ c).

Exercise 12.2.4. Prove that there is a Kurtz random real which is K-trivial.

12.3 Lowness for randomness

12.3.1 General lowness notions

Given a notion Γ of randomness, we may relativize it to a real x to obtain Γx. Define Low(Γ)={x ∈ 2ω | Γ ⊆ Γx}. Then every member of Low(Γ) is said to be low for Γ.

One may consider a slightly stronger lowness notion. Since each Γ is defined in terms of Γ-tests, we may declare x to be low for Γ-tests if every Γx test is covered (as a set) by a Γ-test. More details concerning these can be found in [111] and [24].

Hence if x ∈ Low(Γ) then it does not provide any information regarding randomness for Γ. Nevertheless, the property of lowness seems somewhat mysterious since one has no clue on the complexity of members of Low(Γ). A very important and successful application of classical recursion theory is the characterization of the lowness property for various notions of randomness.

12.3.2 Lowness for Kurtz randomness

Theorem 12.3.1 (Stephan, Yu [160] and Greenberg, Miller [38]). For any real x, the following are equivalent:

(i)x is low for Kurtz randomness;

(ii)x is low for Kurtz tests;

(iii)x is recursively dominated and non-DNR.

It is known that there are -many recursively dominated and non-DNR reals. Hence Theorem 12.3.1 says that there is an abundance of reals which do not provide any information about Kurtz randomness.

12.3.3 Lowness for Schnorr randomness

Definition 12.3.2. A real x is recursively traceable if for any f ≤T x, there is a recursive function such that for any e, f(e)∈ g(e) and |g(e)| ≤ e.

It is not difficult to see that every recursively traceable real is recursively dominated and non-DNR. Moreover, the construction of a recursively traceable real is quite similar to that of a set of minimal Turing degree. They are both obtained using Sacks forcing with recursive perfect trees.

Theorem 12.3.3 (Terwijn, Zambella [163] and Kjos-Hanssen, Nies, Stephan [67]). For any real x, the following are equivalent:

(i)x is low for Schnorr randomness;

(ii)x is low for Schnorr tests;

(iii)x is recursively traceable.

Hence there are again many reals that are low for Schnorr randomness.

12.3.4 Lowness for Martin-Löf randomness

Definition 12.3.4. Let Γ be a notion of randomness. A real x is a base for Γ if there is a Γx-random y such that x ≤T y.

The following result is one of the deepest in algorithmic randomness theory.

Theorem 12.3.5 (Nies [110] and Hirschfeldt, Nies, Stephan [48]). For any x, the following are equivalent:

(i)x is K-trivial;

(ii)x is a base for Martin-Löf randomness;

(iii)(∃c)(∀n)(K(n)≤ Kx(n)+ c)

(iv)x is low for Martin-Löf tests;

(v)x is low for Martin-Löf randomness.

The concept of a randomness base is particularly important in the proof of Theorem 12.3.5. Note that one may view Martin-Löf randomness to be the weakest notion of randomness as it has only countably many bases (see [27]). Following the characterization in Theorem 12.3.5, Nies introduced a new reduction relation ≤LR:

Definition 12.3.6. x ≤LR y if every y-Martin-Löf random real is x-Martin-Löf random.

Hence by Theorem 12.3.5, x ≤LR if and only if x is K-trivial. This relation is expressed in terms of Kolmogorov complexity as follows:

Theorem 12.3.7 (Kjos-Hanssen, Miller, Solomon [66]). x ≤LR y if and only if

Combining Corollary 12.2.13 with van Lambalgen’s Theorem (12.1.7) offers additional evidence for the randomness thesis:

Proposition 12.3.8. For any two Martin-Löf random reals x and y, x ≤K y implies y ≤LR x.

12.3.5 Lowness for strong Martin-Löf randomness

Theorem 12.3.9 (Downey et al. [23], Nies [111], and Kjos-Hanssen et al. [66]). For any x, the following are equivalent:

(i)x is K-trivial;

(ii)x is low for strong Martin-Löf test;

(iii)x is low for strong Martin-Löf randomness.

12.3.6 Exercises

Exercise 12.3.1. Prove that there are -many recursively dominated and non-DNR reals.

Exercise 12.3.2. Prove that there is a recursively traceable x for which .

Exercise 12.3.3. Let be a model of ZFC and let x be Sacks generic over . Prove that if y is random in , then y is random in [x].