Asymptotic density, computable traceability, and 1-randomness

Uri Andrews, et al. "Asymptotic density, computable traceability, and 1-randomness." Fundamenta Mathematicae 234.1 (2016): 41-53. <http://eudml.org/doc/286624>.

@article{UriAndrews2016,
abstract = {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.},
author = {Uri Andrews, Mingzhong Cai, David Diamondstone, Carl Jockusch, Steffen Lempp},
journal = {Fundamenta Mathematicae},
keywords = {computability theory; asymptotic density; computably traceable; 1-random; hyperimmune degrees; PA degrees},
language = {eng},
number = {1},
pages = {41-53},
title = {Asymptotic density, computable traceability, and 1-randomness},
url = {http://eudml.org/doc/286624},
volume = {234},
year = {2016},
}

TY - JOUR
AU - Uri Andrews
AU - Mingzhong Cai
AU - David Diamondstone
AU - Carl Jockusch
AU - Steffen Lempp
TI - Asymptotic density, computable traceability, and 1-randomness
JO - Fundamenta Mathematicae
PY - 2016
VL - 234
IS - 1
SP - 41
EP - 53
AB - 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.
LA - eng
KW - computability theory; asymptotic density; computably traceable; 1-random; hyperimmune degrees; PA degrees
UR - http://eudml.org/doc/286624
ER -