Hierarchy of Computably Enumerable Degrees II

DOI10.53733/133OpenAlexW3198990160MaRDI QIDQ3380356

Ellen Hammatt, Noam Greenberg, Rodney G. Downey

Publication date: 28 September 2021

Published in: New Zealand Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.53733/133

zbMATH Keywords

hierarchiesdegrees of unsolvabilityreducibilities

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Associative rings and algebras (16-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lattice nonembeddings and initial segments of the recursively enumerable degrees
• Not every finite lattice is embeddable in the recursively enumerable degrees
• Two theorems on many-one degrees of recursively enumerable sets
• A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
• Lowness and logical depth
• Cuppability of simple and hypersimple sets
• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• Lowness properties and randomness
• Hypersimplicity and semicomputability in the weak truth table degrees
• Splitting into degrees with low computational strength
• Bounded Randomness
• Algorithmic Randomness and Complexity
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• Notions of weak genericity
• TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES
• T-Degrees, Jump Classes, and Strong Reducibilities
• Interpretability and Definability in the Recursively Enumerable Degrees
• Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets
• Post's program and incomplete recursively enumerable sets.
• The infinite injury priority method
• Recursively enumerable sets and degrees
• Contiguity and distributivity in the enumerable Turing degrees
• Maximal contiguous degrees
• STRONG JUMP-TRACEABILITY
• A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES
• Degree theoretic definitions of the low₂ recursively enumerable sets
• Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees
• A Hierarchy of Turing Degrees
• Π₁⁰ classes and strong degree spectra of relations
• Post's Programme for the Ershov Hierarchy
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Randomness, relativization and Turing degrees
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Recursively enumerable sets of positive integers and their decision problems
• Theory and Applications of Models of Computation

This page was built for publication: Hierarchy of Computably Enumerable Degrees II