The Hilbert's-Tenth-Problem Operator

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(\mathbb{Z}[W^{-1}])$, which is naturally viewed as a set of polynomials in $\mathbb{Z}[X_1,X_2,\dots ]$. For $W=\varnothing$, it is a famous result of Matiyasevich, Davis, Putnam, and Robinson that the jump $\varnothing {}^{\prime }$ is Turing-equivalent to $HTP(\mathbb{Z})$. More generally, $HTP(\mathbb{Z}[W^{-1}])$ is always Turing-reducible to $W^{\prime }$, but not necessarily equivalent. We show here that the situation with $W=\varnothing$ is anomalous: for almost all $W$, the jump $W^{\prime }$ is not diophantine in $\mathbb{Z}[W^{-1}]$. We also show that the $HTP$ operator does not preserve Turing equivalence: even for complementary sets $U$ and $\overline{U}$, $HTP(\mathbb{Z}[U^{-1}])$ and $HTP(\mathbb{Z}[{\overline{U}}^{-1}])$ can differ by a full jump. Strikingly, reversals are also possible, with $V{<}_{T}W$ but $HTP(\mathbb{Z}[W^{-1}]){<}_{T}HTP(\mathbb{Z}[V^{-1}])$.