|
Mathematical logic, algebra and number theory
Generic undecidability of universal theories
A. N. Rybalovab a Omsk State Technical University,
11, Mira ave.,
Omsk, 644050, Russia
b Sobolev Institute of Mathematics, 13, Pevtsova str., Omsk, 644043, Russia
Abstract:
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.
Received January 30, 2019, published September 23, 2019
Citation:
A. N. Rybalov, “Generic undecidability of universal theories”, Sib. Èlektron. Mat. Izv., 16 (2019), 1289–1294
Linking options:
https://www.mathnet.ru/eng/semr1130 https://www.mathnet.ru/eng/semr/v16/p1289
|
Statistics & downloads: |
Abstract page: | 211 | Full-text PDF : | 119 | References: | 25 |
|