Degrees in Which the Recursive Sets are Uniformly Recursive

Abstract

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.