Let r ∈ [0,1]. A set A ⊆ ω is said to be coarsely computable at density r if there is a computable function f such that {n | 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 a is hyperimmune or PA, then there is an a-computable set which is not coarsely computable at any positive density.
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-fm118-10-2015,
author = {Uri Andrews and Mingzhong Cai and David Diamondstone and Carl Jockusch and Steffen Lempp},
title = {Asymptotic density, computable traceability, and 1-randomness},
journal = {Fundamenta Mathematicae},
volume = {233},
year = {2016},
pages = {41-53},
zbl = {06602780},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm118-10-2015}
}
Uri Andrews; Mingzhong Cai; David Diamondstone; Carl Jockusch; Steffen Lempp. Asymptotic density, computable traceability, and 1-randomness. Fundamenta Mathematicae, Tome 233 (2016) pp. 41-53. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm118-10-2015/