Logic Seminar
For a ring $R$, Hilbert’s Tenth Problem is the set $HTP(R)$ of polynomials $f\in R[X1,X2,…]$ for which $f=0$ has a solution in $R$. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that $HTP(Z)$ is Turing-equivalent to the Halting Problem. The Turing degree of $HTP(Q)$ remains unknown. Here we consider the problem for subrings of $Q$. One places a natural topology on the space of such subrings, which is homeomorphic to Cantor space. This allows consideration of measure theory and also Baire category theory. We prove, among other things, that $HTP(Q)$ computes the Halting Problem if and only if $HTP(R)$ computes it for a nonmeager set of subrings $R$. We also draw parallels and make distinctions between the jump operator and the operator $HTP$, which maps an element of Cantor space to the the $HTP$ of the corresponding subring of $Q$.