TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES

DOI10.1142/S0219061307000640zbMath1149.03032MaRDI QIDQ3521597

Noam Greenberg, Rebecca Weber, Rodney G. Downey

Publication date: 26 August 2008

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

zbMATH Keywords

computational complexitycomputability theorydefinabilityTuring reducibilityTuring degreescritical triple

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (15)

Nonlowness is independent from fickleness ⋮ Bounded Randomness ⋮ Strengthening prompt simplicity ⋮ Towards characterizing the \(> \omega^2\)-fickle recursively enumerable Turing degrees ⋮ A classification of low c.e. sets and the Ershov hierarchy ⋮ Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees ⋮ A semilattice generated by superlow computably enumerable degrees ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Indifferent sets for genericity ⋮ Lowness for bounded randomness ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Promptness does not imply superlow cuppability ⋮ Effective domination and the bounded jump ⋮ Maximality and collapse in the hierarchy of α-c.a. degrees

Cites Work

• Lattice nonembeddings and initial segments of the recursively enumerable degrees
• Structural interactions of the recursively enumerable T- and W-degrees
• Not every finite lattice is embeddable in the recursively enumerable degrees
• Dynamic notions of genericity and array noncomputability
• A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
• Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree
• Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees
• Interpretability and Definability in the Recursively Enumerable Degrees
• Contiguity and distributivity in the enumerable Turing degrees
• Degree theoretic definitions of the low₂ recursively enumerable sets
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Embeddings of \(N_5\) and the contiguous degrees

This page was built for publication: TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES