##
Using Random Sets as Oracles

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
Delta^{0}_{2} 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.

drh@math.uchicago.edu