Asymptotic density, computable traceability, and 1-randomness
Fundamenta Mathematicae, Tome 234 (2016) no. 1, pp. 41-53
Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences
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.
Keywords:
set subseteq omega said coarsely computable density there computable function mid has lower density least main results coarsely computable density computably traceable truth table reducible random set other direction degree mathbf hyperimmune there mathbf computable set which coarsely computable positive density
Affiliations des auteurs :
Uri Andrews 1 ; Mingzhong Cai 2 ; David Diamondstone 3 ; Carl Jockusch 4 ; Steffen Lempp 1
@article{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},
pages = {41--53},
publisher = {mathdoc},
volume = {234},
number = {1},
year = {2016},
doi = {10.4064/fm118-10-2015},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.4064/fm118-10-2015/}
}
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 SP - 41 EP - 53 VL - 234 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.4064/fm118-10-2015/ DO - 10.4064/fm118-10-2015 LA - en ID - 10_4064_fm118_10_2015 ER -
%0 Journal Article %A Uri Andrews %A Mingzhong Cai %A David Diamondstone %A Carl Jockusch %A Steffen Lempp %T Asymptotic density, computable traceability, and 1-randomness %J Fundamenta Mathematicae %D 2016 %P 41-53 %V 234 %N 1 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.4064/fm118-10-2015/ %R 10.4064/fm118-10-2015 %G en %F 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 234 (2016) no. 1, pp. 41-53. doi: 10.4064/fm118-10-2015
Cité par Sources :