Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T19:44:22.156Z Has data issue: false hasContentIssue false

Degrees in Which the Recursive Sets are Uniformly Recursive

Published online by Cambridge University Press:  20 November 2018

Carl G. Jockusch Jr.*
Affiliation:
University of Illinois, Urbana, Illinois
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1972