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/

[1] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Generic-case complexity, decision problems in group theory, and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[2] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Average-case complexity and decision problems in group theory”, Adv. Math., 190:2 (2005), 343–359 | DOI | MR | Zbl

[3] J. D. Hamkins, A. Miasnikov, “The halting problem is decidable on a set of asymptotic probability one”, Notre Dame J. Formal Logic, 47:4 (2006), 515–524 | DOI | MR | Zbl

[4] A. G. Myasnikov, A. N. Rybalov, “Generic complexity of undecidable problems”, J. Symb. Log., 73:2 (2008), 656–673 | DOI | MR | Zbl

[5] A. Rybalov, “On the strongly generic undecidability of the halting problem”, Theor. Comput. Sci., 377:1–3 (2007), 268–270 | DOI | MR | Zbl

[6] A. N. Rybalov, “O genericheskoi nerazreshimosti problemy ostanovki dlya normalizovannykh mashin Tyuringa”, Vestn. Om. un-ta, 2014, no. 3, 15–17

[7] A. N. Rybalov, “Generic complexity of Presburger arithmetic”, Theor. Comput. Syst., 46:1 (2010), 2–8 | DOI | MR | Zbl

[8] A. Rybalov, “Generic complexity of the Diophantine problem”, Groups Complex. Cryptol., 5:1 (2013), 25–30 | DOI | MR | Zbl

[9] A. N. Rybalov, “Genericheskaya nerazreshimost ekzistentsialnoi teorii koltsa tselykh chisel”, Sib. elektron. matem. izv., 13 (2016), 882–887 http://semr.math.nsc.ru/v13/p882-887.pdf | DOI | Zbl

[10] A. N. Rybalov, “O genericheskoi slozhnosti problemy vypolnimosti bulevykh formul”, Vestn. Om. un-ta, 2013, no. 4, 52–56

[11] A. N. Rybalov, “O genericheskoi slozhnosti problemy raspoznavaniya kvadratichnykh vychetov”, PDM, 2015, no. 2(28), 54–58 | DOI

[12] A. N. Rybalov, “O genericheskoi slozhnosti problemy diskretnogo logarifma”, PDM, 2016, no. 3(33), 93–97 | DOI

[13] A. Rybalov, “On the generic complexity of the searching graph isomorphism problem”, Groups Complex. Cryptol., 7:2 (2015), 191–193 | DOI | MR | Zbl

[14] C. G. Jockusch (Jr.), P. E. Schupp, “Generic computability, Turing degrees, and asymptotic density”, J. London Math. Soc. II Ser., 85:2 (2012), 472–490 | DOI | MR | Zbl