Hilbert's Tenth Problem - Formulation

Formulation

The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an algorithm. The term "rational integer" simply refers to the integers, positive, negative or zero: 0, ±1, ±2, ... . So Hilbert was asking for a general algorithm to decide whether a given polynomial Diophantine equation with integer coefficients has a solution in integers. The answer to the problem is now known to be in the negative: no such general algorithm can exist. Although it is unlikely that Hilbert had conceived of such a possibility, before going on to list the problems, he did presciently remark:

"Occasionally it happens that we seek the solution under insufficient hypotheses or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses or in the sense contemplated."

The work on the problem has been in terms of solutions in natural numbers rather than arbitrary integers. But it is easy to see that an algorithm in either case could be used to obtain one for the other. If one possessed an algorithm to determine solvability in natural numbers, it could be used to determine whether an equation in unknowns,

has an integer solution by applying the supposed algorithm to the 2n equations

Conversely, an algorithm to test for solvability in arbitrary integers could be used to test a given equation for solvability in natural numbers by applying that supposed algorithm to the equation obtained from the given equation by replacing each unknown by the sum of the squares of four new unknowns. This works because of Lagrange's four-square theorem, to the effect that every natural number can be written as the sum of four squares.