Degrees in Which the Recursive Sets are Uniformly Recursive
Carl G. Jockusch · Canadian Journal of Mathematics · 1972
One of the most fundamental and characteristic features of recursion theory is the fact that the recursive sets are not uniformly recursive. In this paper we consider the degrees a such that the recursive sets are uniformly of degree ≦ a and characterize them by the condition a’ ≦ 0" . A number of related results will be proved, and one of these will be combined with a theorem of Yates to show that there is no r.e. degree a < 0’ such that the r.e. sets of degree ≦a are uniformly of degree ≦a . This result and a generalization will be used to study the relationship between Turing and many-one reducibility on the r.e. sets.