Logic Seminar

Russell MillerQueens College and CUNY Graduate Center
Hilbert's tenth problem for subrings of the rationals

Tuesday, August 22, 2017 - 2:55pm
Malott 206

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$.