Asymptotic Density and the Coarse Computability Bound

by Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Timothy H. McNicholl, and Paul E. Schupp



Status: published in Computability 5 (2016) 13 - 27.

Availability: journal version and preprint

Abstract. For r in [0,1] we say that a set A is coarsely computable at density r if there is a computable set C such that the set of n such that C(n) = A(n) has lower density at least r. Let γ(A) be the supremum of the set of r such that A is coarsely computable at density r. We study the interactions of these concepts with Turing reducibility. For example, we show that if r is in (0,1] there are sets A0,A1 such that γ(A0) = γ(A1) = r where A0 is coarsely computable at density r while A1 is not coarsely computable at density r. We show that a real r in [0,1] is equal to γ(A) for some c.e. set A if and only if r is left-Σ03. A surprising result is that if G is a Δ02 1-generic set, and A is G-computable with γ(A) = 1, then A is coarsely computable at density 1.



drh@math.uchicago.edu