Using Random Sets as Oracles
Status: to appear in the Journal of the London Mathematical
Society
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.
drh@math.uchicago.edu