A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES

DOI10.1017/bsl.2017.41OpenAlexW2800448812MaRDI QIDQ4637942

Noam Greenberg, Rodney G. Downey

Publication date: 3 May 2018

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e3fbc85050cb86f663bf207886dbbe39ada38160

zbMATH Keywords

lattice embeddingcomputably enumerablemultiple permittingtotally \(\alpha\)-computably approximable

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Related Items (6)

Bounded Randomness ⋮ Splitting into degrees with low computational strength ⋮ Lowness for bounded randomness ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Effective domination and the bounded jump ⋮ Maximality and collapse in the hierarchy of α-c.a. degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kobayashi compressibility
• Lattice nonembeddings and initial segments of the recursively enumerable degrees
• The density of infima in the recursively enumerable degrees
• Turing degrees of reals of positive effective packing dimension
• Structural interactions of the recursively enumerable T- and W-degrees
• Not every finite lattice is embeddable in the recursively enumerable degrees
• A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
• Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree
• Integer valued betting strategies and Turing degrees
• A bounded jump for the bounded Turing degrees
• Many-one degrees of the predicates \(H_ a(x)\)
• Lowness properties and randomness
• Hypersimplicity and semicomputability in the weak truth table degrees
• Splitting into degrees with low computational strength
• Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees
• Natural Large Degree Spectra
• Bounded Randomness
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• Recursive well-orderings
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES
• Indifferent Sets
• T-Degrees, Jump Classes, and Strong Reducibilities
• Interpretability and Definability in the Recursively Enumerable Degrees
• Bounding minimal pairs
• Post's program and incomplete recursively enumerable sets.
• Minimal pairs and high recursively enumerable degrees
• The recursively enumerable α-degrees are dense
• Double jumps of minimal degrees
• Contiguity and distributivity in the enumerable Turing degrees
• Maximal contiguous degrees
• AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES
• ON THE DEFINABILITY OF THE DOUBLE JUMP IN THE COMPUTABLY ENUMERABLE SETS
• Degree theoretic definitions of the low₂ recursively enumerable sets
• Indifferent sets for genericity
• Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees
• The importance of Π₁⁰ classes in effective randomness
• Anti-Complex Sets and Reducibilities with Tiny Use
• Π₁⁰ classes and strong degree spectra of relations
• Post's Programme for the Ershov Hierarchy
• The role of true finiteness in the admissible recursively enumerable degrees
• Recursion Theory and Dedekind Cuts
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• New Computational Paradigms
• Recursively enumerable sets of positive integers and their decision problems
• Theory and Applications of Models of Computation
• Embeddings of \(N_5\) and the contiguous degrees

This page was built for publication: A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES