The Hilbert's-Tenth-Problem Operator

摘要

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,...]. For W = O, it is a famous result of Matijasevi, Davis, Putnam and Robinson that the jump O 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 = O is anomalous: for almost all W, the jump W is not diophantine in HTP(Z[W-1]). We also show that the HTP operator does not preserve Turing equivalence: even for complementary sets HTP(Z[U - 1]) and HTP(Z[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]).