Randomness and the linear degrees of computability
by G. Barmpalias and A. Lewis
Summary
We show that there exists a real A such that, for all reals
B , if A is linear reducible to B (i.e. Turing reducible with use the identity function plus a constant)
then B is Turing reducible to A. In fact, every random real satisfies this quasi-maximality
property. As a corollary we may conclude that there exists no complete
real in the structure of $\Delta^0_2$ linear degrees. Upon realizing that quasi-maximality does not characterize the
random reals---there exist reals which are not random but which are of
quasi-maximal linear degree---it is then natural to ask whether maximality
could provide such a characterization. Such hopes, however, are in vain
since no real is of maximal linear degree.