ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS

DOI10.1142/S0219061313500050zbMath1326.03048arXiv1307.0040MaRDI QIDQ5401598

Paul E. Schupp, Carl G. jun. Jockusch, Rodney G. Downey

Publication date: 10 March 2014

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

Full work available at URL: https://arxiv.org/abs/1307.0040

zbMATH Keywords

asymptotic densitycomputably enumerable setsTuring degreeslow degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28)

Related Items

Notions of robust information coding ⋮ What Percentage of Programs Halt? ⋮ Effectively categorical abelian groups ⋮ Asymptotic density, computable traceability, and 1-randomness ⋮ Nonexistence of minimal pairs for generic computability ⋮ Generically and coarsely computable isomorphisms ⋮ Computability theory. Abstracts from the workshop held February 5--11, 2012. ⋮ Følner functions and the generic word problem for finitely generated amenable groups ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ The degrees of bi-hyperhyperimmune sets ⋮ A MINIMAL PAIR IN THE GENERIC DEGREES ⋮ Computably enumerable sets that are automorphic to low sets ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ Some Questions in Computable Mathematics ⋮ COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS ⋮ INTRINSIC SMALLNESS ⋮ Generic case completeness ⋮ Asymptotic density and computability ⋮ Asymptotic density and the Ershov hierarchy

Cites Work

• Algorithmically finite groups.
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Average case completeness
• Generic-case complexity, decision problems in group theory, and random walks.
• Effectively categorical abelian groups
• Turing Computability
• Generic computability, Turing degrees, and asymptotic density
• Backdoors to Satisfaction
• Generic complexity of undecidable problems
• Average Case Complete Problems
• Computational complexity, speedable and levelable sets
• Automorphisms of the lattice of recursively enumerable sets
• Matrix Transformation Is Complete for the Average Case
• Jump equivalence of the Δ₂⁰ hyperimmune sets
• The nonlow computably enumerable degrees are not invariant in $\mathcal {E}$
• Nonexistence of minimal pairs for generic computability
• The degrees of bi‐immune sets
• A theorem on hyperhypersimple sets
• The Degrees of Hyperimmune Sets