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 satisÞes this quasi-maximality property. As a corollary we may conclude that there exists no complete real in the structure of Delta2 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.