Using Random Sets as Oracles
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.
drh@math.uchicago.edu