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 image and image-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 ...

Get Recursion Theory now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.