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 complexity; computability theory; definability; Turing reducibility; Turing degrees; critical triple
03D15: Complexity of computation (including implicit computational complexity)
03D25: Recursively (computably) enumerable sets and degrees
Related Items
A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES, Indifferent sets for genericity, Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees, A semilattice generated by superlow computably enumerable degrees, Lowness for bounded randomness, Bounded Randomness, Strengthening prompt simplicity, Promptness does not imply superlow cuppability
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
