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

zbMATH Keywords

recursively enumerable setsn-r.e. setsordinals in recursion theoryreducibilities between numberingstheory of numberings in the difference hierarchy

Mathematics Subject Classification ID

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)

Numberings in the analytical hierarchy ⋮ Rogers semilattices of punctual numberings ⋮ Rogers semilattices with least and greatest elements in the Ershov hierarchy ⋮ Rogers semilattices of limitwise monotonic numberings ⋮ On universal pairs in the Ershov hierarchy ⋮ Elementary theories and hereditary undecidability for semilattices of numberings ⋮ Theories of Rogers semilattices of analytical numberings ⋮ One-element Rogers semilattices in the Ershov hierarchy

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