Asymptotic density, computable traceability, and 1-randomness

DOI10.4064/fm118-10-2015zbMath1401.03074MaRDI QIDQ3178221

Steffen Lempp, Carl G. jun. Jockusch, Uri Andrews, Mingzhong Cai, David E. Diamondstone

Publication date: 8 July 2016

Published in: Fundamenta Mathematicae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4064/fm118-10-2015

zbMATH Keywords

asymptotic density; computability theory; computably traceable; PA degrees; 1-random; hyperimmune degrees

Mathematics Subject Classification ID

03D25: Recursively (computably) enumerable sets and degrees

03D28: Other Turing degree structures

03D32: Algorithmic randomness and dimension

Related Items

The gamma question for many-one degrees, Asymptotic Density and the Theory of Computability: A Partial Survey, Lowness, Randomness, and Computable Analysis, Some Questions in Computable Mathematics

Cites Work

• Unnamed Item
• Generic-case complexity, decision problems in group theory, and random walks.
• Computational randomness and lowness
• Asymptotic density and the coarse computability bound
• Generic computability, Turing degrees, and asymptotic density
• Algorithmic Randomness and Complexity
• Covering the Recursive Sets
• Notions of weak genericity
• Generic complexity of undecidable problems
• A Unifying Approach to the Gamma Question
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• From Bi-Immunity to Absolute Undecidability
• The Degrees of Hyperimmune Sets