Asymptotic Density and the Coarse Computability Bound
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