Logic Seminar

Russell Miller, Queens College - City University of New York

"Hilbert's Tenth Problem for Subrings of the Rationals"

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.