Asymptotic density, computable traceability, and 1-randomness
Volume 234 / 2016
Fundamenta Mathematicae 234 (2016), 41-53
MSC: 03D28, 03D32.
DOI: 10.4064/fm118-10-2015
Published online: 15 February 2016
Abstract
Let $r\in [0,1]$. A set $A \subseteq \omega $ is said to be coarsely computable at density $r$ if there is a computable function $f$ such that $\{n \mid f(n) = A(n)\}$ has lower density at least $r$. Our main results are that $A$ is coarsely computable at density $1/2$ if $A$ is computably traceable or truth-table reducible to a $1$-random set. In the other direction, we show that if a degree $\mathbf {a}$ is hyperimmune or PA, then there is an $\mathbf {a}$-computable set which is not coarsely computable at any positive density.
