##
Asymptotic density and the coarse computability bound

Status: *Computability* 5 (2016) 13 - 27.

Availability: PDF

**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 *A*_{0},*A*_{1} such that
γ(*A*_{0}) = γ(*A*_{1}) = *r*
where *A*_{0} is coarsely computable at density *r*
while *A*_{1} 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-Σ^{0}_{3}. A surprising result is that if
*G* is a Δ^{0}_{2} 1-generic set, and *A*
is *G*-computable with γ(*A*) = 1, then *A* is
coarsely computable at density 1.

drh@math.uchicago.edu