Using Random Sets as Oracles

Denis R. Hirschfeldt, André Nies, and Frank Stephan

Status: published in the Journal of the London Mathematical Society 75 (2007) 610 - 622.

Availability: journal version and preprint

Abstract. Let C be a notion of effective randomness for individual sets of natural numbers. We say B is a basis for C randomness if there is a Z computing B such that Z is C random relative to B. We show that the bases for 1-randomness are exactly the K-trivial sets and discuss several consequences of this result. We also show that the bases for computable randomness include every Δ02 set that is not diagonally noncomputable, but no set of PA-degree. As a consequence, we conclude that an n-c.e. set is a basis for computable randomness iff it is Turing incomplete.