Geodesic
Generic undecidability of universal theories
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1289-1294.

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

Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper we study generic complexity of undecidable universal theories. We prove that any undecidable universal theory remains generically undecidable (i.e. for almost all inputs).
Keywords: universal theory, generic complexity. 
@article{SEMR_2019_16_a21,
     author = {A. N. Rybalov},
     title = {Generic undecidability of universal theories},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1289--1294},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic undecidability of universal theories
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 1289
EP  - 1294
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/
LA  - ru
ID  - SEMR_2019_16_a21
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic undecidability of universal theories
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 1289-1294
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/
%G ru
%F SEMR_2019_16_a21
A. N. Rybalov. Generic undecidability of universal theories. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1289-1294. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a21/

[1] E.Y. Daniyarova, A.G. Myasnikov, V.N. Remeslennikov, Algebraic geometry over algebraic structures, SB RAS, Novosibirsk, 2016 (in Russian) | MR

[2] 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

[3] 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

[4] 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

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

[6] D.E. Knuth, The Art of Computer Programming, Addison-Wesley, Reading, Massachusetts, 1997 | MR | Zbl