|
This article is cited in 2 scientific papers (total in 2 papers)
Mathematical logic, algebra and number theory
Generic undecidability of existential theory of integer numbers ring
A. N. Rybalov Sobolev Institute of Mathematics, Pevtsova str. 13, Omsk 644043, Russia
Abstract:
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.
Received March 24, 2016, published October 20, 2016
Citation:
A. N. Rybalov, “Generic undecidability of existential theory of integer numbers ring”, Sib. Èlektron. Mat. Izv., 13 (2016), 882–887
Linking options:
https://www.mathnet.ru/eng/semr720 https://www.mathnet.ru/eng/semr/v13/p882
|
Statistics & downloads: |
Abstract page: | 142 | Full-text PDF : | 38 | References: | 36 |
|