Incompleteness, Approximation and Relative Randomness

Article type: Research Article

Authors: Morphett, Anthony^;

Affiliations: Department of Mathematics and Statistics, The University of Melbourne, Victoria 3010, Australia. anthony@morphett.info

Note: [] Portions of this paper first appeared as part of the author’s PhD thesis [14], University of Leeds, 2009.

Abstract: We present some results about the structure of c.e. and $\Delta^0_2$ LR-degrees. First we give a technique for lower cone avoidance in the c.e. and $\Delta^0_2$ LR-degrees, and combine this with upper cone avoidance via Sacks restraints to construct a c.e. LR-degree which is incomparable with a given intermediate $\Delta^0_2$ LR-degree. Next we combine measure-guessing with an LR-incompleteness strategy to construct an incomplete c.e. LR-degree which is above a given low $\Delta^0_2$ LR-degree. This is in contrast to the Turing degrees, in which there is a low $\Delta^0_2$ Turing degree which is incomparable with all intermediate c.e. Turing degrees.

Keywords: computably enumerable degrees, relative randomness, incompleteness

DOI: 10.3233/COM-12014

Journal: Computability, vol. 1, no. 2, pp. 109-130, 2012