Geodesic
Asymptotic density and computability
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 10 (2021), pp. 3-14

Voir la notice de l'article provenant de la source Math-Net.Ru

We show that a set is bi-immune if and only if there are no computable permutations that arrange the set into a generically computable set or an effectively densely computable set. An example of a coarsely computable bi-immune set is constructed. It is also proved that for any set there is a permutation from the same Turing degree that arranges the set into an effectively densely computable set. The upper densities of some sets are studied.
Keywords: asymptotic density, generic complexity, Turing degree.
Mots-clés : bi-immune set 
@article{IVM_2021_10_a0,
     author = {I. I. Batyrshin},
     title = {Asymptotic density and computability},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {3--14},
     publisher = {mathdoc},
     number = {10},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2021_10_a0/}
}
TY  - JOUR
AU  - I. I. Batyrshin
TI  - Asymptotic density and computability
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2021
SP  - 3
EP  - 14
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2021_10_a0/
LA  - ru
ID  - IVM_2021_10_a0
ER  - 
%0 Journal Article
%A I. I. Batyrshin
%T Asymptotic density and computability
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2021
%P 3-14
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2021_10_a0/
%G ru
%F IVM_2021_10_a0
I. I. Batyrshin. Asymptotic density and computability. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 10 (2021), pp. 3-14. http://geodesic.mathdoc.fr/item/IVM_2021_10_a0/