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: PostScript, DVI, and PDF

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