A minimal pair joining to a plus cupping Turing degree

A computably enumerable (c.e.) degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC , and show that there exists a minimal pair which join to a plus cupping degree, so that PC ? NB . This gives a first known difference between NB and PC . (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Kolmogorov complexity and computably enumerable sets

We study the computably enumerable sets in terms of the:     

Cupping the Recursively Enumerable Degrees by D.R.E. Degrees

We prove that there are two incomplete d.r.e. degrees (the Turingdegrees of differences of two recursively enumerable sets) suchthat every non-zero recursively enumerable degree cups at leastone of them to 0', the greatest recursively enumerable (Turing)degree. 1991 Mathematics Subject Classification: primary 03D25,03D30; secondary 03D35.     

Bounding cappable degrees

It will be shown that there exist computably enumerable degrees a and b such that a b, and for any computably enumerable degree u, if u a and u is cappable, then u b. Received: 22 April 1997     

On the distribution of Lachlan nonsplitting bases

 We say that a computably enumerable (c.e.) degree b is a Lachlan nonsplitting base (LNB), if there is a computably enumerable degree a such that a > b, and for any c.e. degrees w,v ≤ a, if a ≤ w or; v or; b then either a ≤ w or; b or a ≤ v or; b. In this paper we investigate the relationship between bounding and nonbounding of Lachlan nonsplitting bases and the high /low hierarchy. We prove that there is a non-Low₂ c.e. degree which bounds no Lachlan nonsplitting base. Received: 11 October 1999 / Published online: 7 May 2002     

On Lachlan’s major sub-degree problem

The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, if and only if . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively. Both authors were funded by EPSRC Research Grant no. GR/M 91419, “Turing Definability”, by INTAS-RFBR Research Grant no. 97-0139, “Computability and Models”, and by an NSFC Grand International Joint Project Grant no. 60310213, “New Directions in Theory and Applications of Models of Computation”. Both authors are grateful to Andrew Lewis for helpful suggestions regarding presentation, technical aspects of the proof, and verification. A. Li is partially supported by National Distinguished Young Investigator Award no. 60325206 (People’s Republic of China).     

There is No Low Maximal D.C.E. Degree

We show that for any computably enumerable (c.e.) set A and any set L, if L is low and , then there is a c.e. splitting such that . In Particular, if L is low and n‐c.e., then is n‐c.e. and hence there is no low maximal n‐c.e. degree.     

A join theorem for the computably enumerable degrees

It is shown that for any computably enumerable (c.e.) degree , if , then there is a c.e. degree such that (so is lowand is high). It follows from this and previous work of P. Cholak, M. Groszek and T. Slaman that the low and low c.e. degrees are not elementarily equivalent as partial orderings.

     

There exists a maximal 3-C.E. enumeration degree

We construct an incomplete 3-c.e. enumeration degree which is maximal among then-c.e. enumeration degrees for everyn with 3≤n≤ω. Consequently then-c.e. enumeration degrees are not dense for any suchn. We show also that no lown-c.e. e-degree can be maximal among then-c.e. e-degrees, for 2≤n≤ω. The first two authors were partially supported by EPSRC Research Grant “Turing Definability” No. GR/M 91419 (UK), and the second author by NSF grant No. 69973048 and by NSF major grant No. 19931020 (P. R. China), and by an INDAM visiting professorship at the University of Siena. The fourth author was partially supported as a visiting scholar by the University of Siena. The first three authors were funded by the INTAS-RFBR joint projectComputability and Models, no. 972-139. The fourth authors would like to thank Marat Arslanov for useful discussions.     

Splitting and cone avoidance in the D.C.E. degrees

It is shown that the Cooper splitting theorem for the n-c.e. degrees is not compatible with cone avoidance: For any n > 1, there exist n-c.e. degree a, c.e. degree b such that 0 < b < a and such that for any n-c.e. degrees x,y, if x ∨ y = a, then either b ≤ x or b ≤ y. This provides a new type of elementary difference between the classes of c.e. and d.c.e. degrees, implementable at lower levels of the high/low hierarchy.