Geodesic
Asymptotic density, computable traceability, and 1-randomness
Uri Andrews 1   ; Mingzhong Cai 2   ; David Diamondstone 3   ; Carl Jockusch 4   ; Steffen Lempp 1
1 Department of Mathematics University of Wisconsin 480 Lincoln Dr. Madison, WI 53706-1388, U.S.A.
2 Department of Mathematics Dartmouth College Hanover, NH 03755, U.S.A.
3 Google 1600 Amphitheatre Parkway Mountain View, CA 94043, U.S.A.
4 Department of Mathematics University of Illinois at Urbana-Champaign 1409 W. Green St. Urbana, IL 61801 U.S.A.
Fundamenta Mathematicae, Tome 234 (2016) no. 1, pp. 41-53 Cet article a éte moissonné depuis la source Institute of Mathematics Polish Academy of Sciences

Voir la notice de l'article

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.
DOI : 10.4064/fm118-10-2015
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

Uri Andrews  1   ; Mingzhong Cai  2   ; David Diamondstone  3   ; Carl Jockusch  4   ; Steffen Lempp  1

1 Department of Mathematics University of Wisconsin 480 Lincoln Dr. Madison, WI 53706-1388, U.S.A.
2 Department of Mathematics Dartmouth College Hanover, NH 03755, U.S.A.
3 Google 1600 Amphitheatre Parkway Mountain View, CA 94043, U.S.A.
4 Department of Mathematics University of Illinois at Urbana-Champaign 1409 W. Green St. Urbana, IL 61801 U.S.A. 
@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},
     year = {2016},
     volume = {234},
     number = {1},
     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
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
%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 :