Asymptotic density, computable traceability, and 1-randomness

DOI10.4064/FM118-10-2015MaRDI QIDQ3178221zbMATH OpenOpenAlexFDO

Authors Uri Andrews, Mingzhong Cai, Carl G. jun. Jockusch, Steffen Lempp, David 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 densitycomputability theorycomputably traceablePA degrees1-randomhyperimmune degrees

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28)

Recommendations

• Asymptotic density and the coarse computability bound
• Generic computability, Turing degrees, and asymptotic density
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Coarse reducibility and algorithmic randomness
• A random set which only computes strongly jump-traceable c.e. sets

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A unifying approach to the Gamma question
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Algorithmic randomness and complexity.
• Asymptotic density and the coarse computability bound
• Computational randomness and lowness
• Covering the Recursive Sets
• From bi-immunity to absolute undecidability
• Generic complexity of undecidable problems
• Generic computability, Turing degrees, and asymptotic density
• Generic-case complexity, decision problems in group theory, and random walks.
• Notions of weak genericity
• The Degrees of Hyperimmune Sets

Cited in

(9)

• Some Questions in Computable Mathematics
• Asymptotic density and the coarse computability bound
• Lowness, Randomness, and Computable Analysis
• Asymptotic density and the theory of computability: a partial survey
• Asymptotic density and computability
• Characterizing the strongly jump-traceable sets via randomness
• Muchnik degrees and cardinal characteristics
• Coarse reducibility and algorithmic randomness
• The gamma question for many-one degrees

This page was built for publication: Asymptotic density, computable traceability, and 1-randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3178221)