Paper detail

Asymptotic density and the coarse computability bound

For $r \in [0,1]$ we say that a set $A \subseteq ω$ is \emph{coarsely computable at density} $r$ if there is a computable set $C$ such that $\{n : C(n) = A(n)\}$ has lower density at least $r$. Let $γ(A) = \sup \{r : A \hbox{ is coarsely computable at density } r\}$. We study the interactions of these concepts with Turing reducibility. For example, we show that if $r \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 \leq\sub{T} G$ with $γ(A) = 1$, then $A$ is coarsely computable at density $1$.