Recursion Theory

14 The theory of higher randomness

Higher randomness theory studies algorithmic complexity problems of randomness using techniques and ideas from hyperarithmetic theory and set theory. Since second order arithmetic provides a broader, though sometimes coarser, view of the reals, the picture one gets of randomness is quite different from that for first order theory.

14.1 Higher Kurtz randomness

14.1.1 and -Kurtz randomness

Definition 14.1.1. Let x ∈ 2ω. Given a class Γ of sets of reals, x is Γ-Kurtz random if it is not a member of any closed nullset ...