MODNET

Research Training Network in Model Theory

Publications > Preprint server > Preprint Number 1354
Preprint Number 1354
1354. Ken Kramer and Russell Miller The Hilbert's-Tenth-Problem Operator E-mail: Submission date: 23 December 2017 Abstract: For a ring R, Hilbert's Tenth Problem HTP(R) is the set of polynomial equations over R, in several variables, with solutions in R. We view HTP as an operator, mapping each set W of prime numbers to HTP(Z[W^{-1}]), which is naturally viewed as a set of polynomials in Z[X_1,X_2,\ldots]. For W=∅, it is a famous result of Matiyasevich, Davis, Putnam, and Robinson that the jump ∅' is Turing-equivalent to HTP(Z). More generally, HTP(Z[W^{-1}]) is always Turing-reducible to W', but not necessarily equivalent. We show here that the situation with W=∅ is anomalous: for almost all W, the jump W' is not diophantine in Z[W^{-1}]. We also show that the HTP operator does not preserve Turing equivalence: even for complementary sets U and \overline{U}, HTP(Z[U^{-1}]) and HTP(Z[\overline{U}^{-1}]) can differ by a full jump. Strikingly, reversals are also possible, with V<_T W but HTP(Z[W^{-1}]) <_T HTP(Z[V^{-1}]). Mathematics Subject Classification: 03D45 (Primary), 03D25, 12L05, 11U05, 11D09 (Secondary) Keywords and phrases: |

Last updated: December 29 2017 16:41 | Please send your corrections to: |