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:

Full text arXiv 1712.08686: pdf, ps.