On degrees of unsolvability and complexity properties

Publisher Website
Google Scholar
Abstract
In this paper we present two theorems concerning relationships between degrees of unsolvability of recursively enumerable sets and their complexity properties.The first theorem asserts that there are nonspeedable recursively enumerable sets in every recursively enumerable Turing degree. This theorem disproves the conjecture that all Turing complete sets are speedable, which arose from the fact that a rather inclusive subclass of the Turing complete sets, namely, the subcreative sets, consists solely of effectively speedable sets [2]. Furthermore, the natural construction to produce a nonspeedable set seems to lower the degree of the resulting set.The second theorem says that every speedable set has jump strictly above the jump of the recursive sets. This theorem is an expected one in view of the fact that all sets which are known to be speedable jump to the double jump of the recursive sets [4].After this paper was written, R. Soare [8] found a very useful characterization of the speedable sets which greatly facilitated the proofs of the results presented here. In addition his characterization implies that an r.e. degree a contains a speed-able set iff a′ > 0′.

This publication has 3 references indexed in Scilit: