Geodesic
Generic amplification of recursively enumerable sets
Algebra i logika, Tome 57 (2018) no. 4, pp. 448-455

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

Generic amplification is a method that allows algebraically undecidable problems to generate problems undecidable for almost all inputs. It is proved that every simple negligible set is undecidable for almost all inputs, but it cannot be obtained via amplification from any undecidable set. On the other hand, it is shown that every recursively enumerable set with nonzero asymptotic density can be obtained via amplification from a set of natural numbers.
Keywords: algorithmically undecidable problem, generic amplification, undecidable set, simple negligible set, recursively enumerable set. 
@article{AL_2018_57_4_a2,
     author = {A. N. Rybalov},
     title = {Generic amplification of recursively enumerable sets},
     journal = {Algebra i logika},
     pages = {448--455},
     publisher = {mathdoc},
     volume = {57},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2018_57_4_a2/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic amplification of recursively enumerable sets
JO  - Algebra i logika
PY  - 2018
SP  - 448
EP  - 455
VL  - 57
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2018_57_4_a2/
LA  - ru
ID  - AL_2018_57_4_a2
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic amplification of recursively enumerable sets
%J Algebra i logika
%D 2018
%P 448-455
%V 57
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2018_57_4_a2/
%G ru
%F AL_2018_57_4_a2
A. N. Rybalov. Generic amplification of recursively enumerable sets. Algebra i logika, Tome 57 (2018) no. 4, pp. 448-455. http://geodesic.mathdoc.fr/item/AL_2018_57_4_a2/