Geodesic
Generic undecidability of existential theory of integer numbers ring
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 882-887 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Famous theorem of Matiyasevich about undecidability of Hilbert’s thenth problem implies that existential theory of ring of integer numbers is undecidable. In this paper we prove that this theory remains undecidable if we restrict the set of all existential arithmetic statements by any recursive subsets of almost all statements (so called generic sets).
Keywords: existential theory of ring of integer numbers, generic complexity. 
@article{SEMR_2016_13_a24,
     author = {A. N. Rybalov},
     title = {Generic undecidability of existential theory of integer numbers ring},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {882--887},
     year = {2016},
     volume = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a24/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic undecidability of existential theory of integer numbers ring
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 882
EP  - 887
VL  - 13
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a24/
LA  - ru
ID  - SEMR_2016_13_a24
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic undecidability of existential theory of integer numbers ring
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 882-887
%V 13
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a24/
%G ru
%F SEMR_2016_13_a24
A. N. Rybalov. Generic undecidability of existential theory of integer numbers ring. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 882-887. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a24/

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

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

[3] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Average-case complexity for the word and membership problems in group theory”, Advances in Mathematics, 190 (2005), 343–359 | DOI | MR | Zbl

[4] A. Myasnikov, A. Rybalov, “Generic complexity of undecidable problems”, Journal of Symbolic Logic, 73:2 (2008), 656–673 | DOI | MR | Zbl

[5] D. Knuth, The Art of Computer Programming, Addison-Wesley, 2008 | MR

[6] Y. Matiyasevich, “The diophantiness of recursively enumerable sets”, Soviet Math. Dokl., 191:2 (1970), 2790–282 (in Russian) | Zbl