TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES
From MaRDI portal
Publication:3521597
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)
computational complexitycomputability theorydefinabilityTuring reducibilityTuring degreescritical triple
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 low2 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
