O'Reilly logo

Recursion Theory by Liang Yu, Chi Tat Chong

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required