Degrees in Which the Recursive Sets are Uniformly Recursive
Author:
- Carl G. JockuschCJCarl G. Jockusch
- 1 December 1972
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 24 (6) , 1092-1099
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.Keywords
This publication has 1 reference indexed in Scilit:
- Minimal degrees and the jump operatorThe Journal of Symbolic Logic, 1973