Reductions between types of numberings
DOI10.1016/j.apal.2019.102716zbMath1439.03077OpenAlexW2949656797WikidataQ127553248 ScholiaQ127553248MaRDI QIDQ2326424
Sanjay Jain, Frank Stephan, Ian Herbert, Steffen Lempp, Manat Mustafa
Publication date: 7 October 2019
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2019.102716
recursively enumerable setsn-r.e. setsordinals in recursion theoryreducibilities between numberingstheory of numberings in the difference hierarchy
Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items (8)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Demuth randomness and computational complexity
- Positive undecidable numberings in the Ershov hierarchy
- \(\Pi_1^0 \) classes, LR degrees and Turing degrees
- Computable single-valued numerations
- Classical recursion theory. The theory of functions and sets of natural numbers
- On some examples of upper semilattices of computable enumerations
- Positive enumerations
- Computable structures and the hyperarithmetical hierarchy
- Infinite family of \(\Sigma_a^{-1}\)-sets with a unique computable numbering
- Things that can be made into themselves
- Families without minimal numberings
- Rogers semilattices of families of two embedded sets in the Ershov hierarchy
- Arithmetic complexity via effective names for random sequences
- Benign cost functions and lowness properties
- Algorithmic Randomness and Complexity
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
- Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy
- Numberings and Randomness
- A decomposition of the Rogers semilattice of a family of d.c.e. sets
- A Splitting Theorem for the N-R.E. Degrees
- Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees
- Anti-Complex Sets and Reducibilities with Tiny Use
- On the existence of universal numberings for finite families of d.c.e. sets
- Post's Programme for the Ershov Hierarchy
- Recursive Pseudo-Well-Orderings
This page was built for publication: Reductions between types of numberings