Abstract

For a ring R, Hilbert’s Tenth Problem $HTP$ is the set of polynomial equations over R, in several variables, with solutions in R. We view $HTP$ as an enumeration operator, mapping each set W of prime numbers to $HTP$, which is naturally viewed as a set of polynomials in $\mathbb {Z}[X_1,X_2,\ldots ]$. It is known that for almost all W, the jump $W'$ does not $1$ -reduce to $HTP$. In contrast, we show that every Turing degree contains a set W for which such a $1$ -reduction does hold: these W are said to be HTP-complete. Continuing, we derive additional results regarding the impossibility that a decision procedure for $W'$ from $HTP$ can succeed uniformly on a set of measure $1$, and regarding the consequences for the boundary sets of the $HTP$ operator in case $\mathbb {Z}$ has an existential definition in $\mathbb {Q}$.