Random Reals and Lipschitz Continuity
G. Barmpalias and A. Lewis
Summary
Lipschitz continuity is used as a tool for analyzing the relationship between incomputability and randomness. Having presented
a simpler proof of one of the major results in this area---the theorem
of Yu and Ding that there exists no cl-complete c.e. real---we go on to
consider the global theory. The existential theory of the cl degrees is
decidable but this does not follow immediately by the standard proof for
classical structures such as the Turing degrees since the cl degrees is a
structure without join. We go on to show that strictly below every random cl degree there is another random cl degree. Results regarding the
phenomenon of quasi-maximality in the cl degrees are also presented.