Toward the definability of the array noncomputable degrees
Stephen M. Walk, Peter A. Cholak · 1999
We focus on a particular class of computably enumerable (c.e.) degrees, the array noncomputable degrees defined by Downey, Jockusch, and Stob, to answer questions related to array noncomputable degrees and definability in the partial ordering ( R , ≤ ) of c.e. degrees. First we demonstrate that the lattice M5 cannot be embedded into the c.e. degrees below every array noncomputable degree, or even below every nonlow array noncomputable degree. As Downey and Shore have proved that M5 can be embedded below every nonlow2 degree, our result is the best possible in terms of array noncomputable degrees and jump classes. Further, it shows that the array noncomputable degrees are definably different from the nonlow2 degrees. We demonstrate also that there are embeddings of M5 in which all five degrees are array noncomputable, and in which the bottom degree is the computable degree 0 but the other four are array noncomputable. Next we turn to the relativization of some important concepts in computability theory. These include array noncomputability, which we have conjectured to be definable in ( R , ≤ ), and other properties, such as promptness and contiguity, that are known to be definable in ( R , ≤ ). We find that if d is a c.e. degree that is not prompt, then there is a c.e. degree a below d such that d is nonetheless prompt over a, and we can choose this a to be in any interval below d. However, for each other property P under consideration, there is a c.e. degree d that fails to have property P and also fails to have the relativized property Pa for any a below d. Finally we discuss our conjecture on the definability of the array noncomputable degrees and report results that arose from the pursuit of it. Two of these would be consequences of the conjecture itself, and another demonstrates a relationship between Schaeffer's composition hierarchy and Sui's recursively-controlled Turing reducibilities.