# Blog Archives

# Topic Archive: Hilbert's Tenth Problem

# Hilbert’s Tenth Problem inside the rationals

For a ring *R*, Hilbert’s Tenth Problem is the set *HTP(R)* of polynomials *f ∈ R[X _{1},X_{2},…]* for which

*f=0*has a solution in

*R*. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that

*HTP(*is Turing-equivalent to the Halting Problem. The Turing degree of

**Z**)*HTP(*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*

**Q***HTP(*computes the Halting Problem if and only if

**Q**)*HTP(R)*computes it for a nonmeager set of subrings

*R*.

# Computability problems in number theory

We will consider several number-theoretic questions which arise from computable model theory. One of these, recently solved by Poonen, Schoutens, Shlapentokh, and the speaker, involves attempting to “embed” a graph into a field: given a graph, one wishes to construct a field with the exact same computable-model-theoretic properties as the graph. (For instance, the automorphisms of the graph should correspond to the automorphisms of the field, by a bijective functorial correspondence which preserves the Turing degree of each automorphism.) Another arises out of consideration of Hilbert’s Tenth Problem for subrings of the rationals: we ask for subrings in which Hilbert’s Tenth Problem is no harder than it is for the rationals themselves. This is known for semilocal subrings, and Eisenträger, Park, Shlapentokh and the speaker have shown that it holds for certain non-semilocal subrings as well, but it remains open whether one can invert “very few” primes and still have it hold. We will explain this problem and discuss the number-theoretic question which arises out of it.