Asymptotic density and the coarse computability bound

DOI10.3233/COM-150035MaRDI QIDQ2799747

Paul E. Schupp, Denis R. Hirschfeldt, Carl G. jun. Jockusch, Timothy H. McNicholl

Publication date: 13 April 2016

Published in: Computability (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic densityTuring degreescoarse computability

Mathematics Subject Classification ID

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

Related Items (11)

Asymptotic density, computable traceability, and 1-randomness ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ On unstable and unoptimal prediction ⋮ DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ Lowness, Randomness, and Computable Analysis ⋮ Some Questions in Computable Mathematics ⋮ Computing sets from all infinite subsets ⋮ MUCHNIK DEGREES AND CARDINAL CHARACTERISTICS ⋮ The gamma question for many-one degrees ⋮ Asymptotic density and computability

Cites Work

• Generic-case complexity, decision problems in group theory, and random walks.
• Generic computability, Turing degrees, and asymptotic density
• Notions of weak genericity
• Asymptotic density and the Ershov hierarchy
• Nonexistence of minimal pairs for generic computability
• From Bi-Immunity to Absolute Undecidability
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• The degrees of bi‐immune sets
• Degrees in Which the Recursive Sets are Uniformly Recursive

This page was built for publication: Asymptotic density and the coarse computability bound