Recursion Theory

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 ∉ ...