Asymptotic density and the coarse computability bound

Abstract

For $r\in [0,1]$ we say that a set $A\subseteq \omega$ 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 $\gamma (A)=\sup \{r:Ais\; coarsely\; computable\; at\; densityr\}$. 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 $\gamma (A_0)=\gamma (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 $\gamma (A)$ for some c.e.\ set $A$ if and only if $r$ is left-${\Sigma }_3^0$. A surprising result is that if $G$ is a ${\Delta }_2^0$ $1$-generic set, and $A\le \subset TG$ with $\gamma (A)=1$, then $A$ is coarsely computable at density $1$.

Cited by in corpus (1)

• Lowness, randomness, and computable analysis