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, Nonlowness is independent from fickleness, Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees, Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees, Maximality and collapse in the hierarchy of α-c.a. degrees, Towards characterizing the \(> \omega^2\)-fickle recursively enumerable Turing degrees, A classification of low c.e. sets and the Ershov hierarchy, A semilattice generated by superlow computably enumerable degrees, Lowness for bounded randomness, Effective domination and the bounded jump, Bounded Randomness, Strengthening prompt simplicity, Hierarchy of Computably Enumerable Degrees II, 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