We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES.
- Authors
DOWNEY, ROD; GREENBERG, NOAM
- Abstract
We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of Δ20 functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.
- Subjects
COMPUTABILITY logic; COMPUTABLE functions; APPROXIMATION theory; COMBINATORICS; ITERATIVE methods (Mathematics)
- Publication
Bulletin of Symbolic Logic, 2018, Vol 24, Issue 1, p53
- ISSN
1079-8986
- Publication type
Article
- DOI
10.1017/bsl.2017.41