Logic Seminar
For a ring R, Hilbert’s Tenth Problem is the set HTP(R) of polynomials f∈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.