Hilbert's tenth problem

Remarks

The result follows from the Matiyasevich–Robinson–Davis–Putnam (MRDP) theorem. A set $S \subseteq \N$ is Diophantine if there is a polynomial $p(a, y_1, \ldots, y_m)$ with integer coefficients such that $a \in S$ exactly when $p(a, y_1, \ldots, y_m) = 0$ for some $y_1, \ldots, y_m \in \N$. The MRDP theorem says that the Diophantine sets are exactly the computably enumerable sets. Taking a Diophantine definition of a c.e. set that is not computable, such as the halting problem, shows that solvability cannot be decided. Matiyasevich completed the proof in 1970 by showing that exponentiation is Diophantine, the last step after work of Davis, Putnam and Julia Robinson.

The question in natural numbers and the question in integers are equivalent. One direction uses Lagrange's four-square theorem: every natural number is a sum of four squares. For equations in one variable the problem is decidable, since the integer roots of a nonzero polynomial lie in a finite range bounded in terms of its coefficients.

Going deeper

For a student

This is a central example of an undecidable problem from ordinary mathematics, outside of logic. The key tool is the MRDP theorem, which identifies Diophantine sets with computably enumerable sets. A consequence is that there is a single polynomial whose positive values, at natural number arguments, are exactly the prime numbers. Whether the analogous problem over $\Q$ is decidable is still open.