DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES

DOI10.1017/jsl.2016.50zbMath1406.03056arXiv1512.09057OpenAlexW2962978350MaRDI QIDQ5359570

Gregory Igusa, Peter A. Cholak

Publication date: 26 September 2017

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

coarse computabilityquasiminimalgeneric computabilitycoarse reducibilitygeneric reducibilitydensity 1 bounding

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items

Asymptotic Density and the Theory of Computability: A Partial Survey, Some Questions in Computable Mathematics, Asymptotic density and computability

Cites Work

• Lowness for genericity
• Generic-case complexity, decision problems in group theory, and random walks.
• THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS
• Asymptotic density and the coarse computability bound
• Generic computability, Turing degrees, and asymptotic density
• COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS
• Lowness and nullsets
• The axiomatization of randomness
• Notions of robust information coding
• Nonexistence of minimal pairs for generic computability
• Using random sets as oracles