Editing Hilbert's tenth problem (section)

===Diophantine sets===
{{main article|Diophantine set}}

In a Diophantine equation, there are two kinds of variables: the parameters and the unknowns. The [[Diophantine set]] consists of the parameter assignments for which the Diophantine equation is solvable. A typical example is the linear Diophantine equation in two unknowns,

:<math>a_1x + a_2y = a_3,</math>

where the equation is solvable if and only if the [[greatest common divisor]] <math>\gcd(a_1, a_2)</math> evenly divides <math>a_3</math>. The set of all ordered triples <math>(a_1, a_2, a_3)</math> satisfying this restriction is called the ''Diophantine set'' defined by <math>a_1x + a_2y = a_3</math>.
In these terms, Hilbert's tenth problem asks whether there is an algorithm to determine if the Diophantine set corresponding to an arbitrary polynomial is non-empty.

The problem is generally understood in terms of the [[natural number]]s (that is, the non-negative integers) rather than arbitrary integers. However, the two problems are equivalent: any general algorithm that can decide whether a given Diophantine equation has an integer solution could be modified into an algorithm that decides whether a given Diophantine equation has a natural-number solution, and vice versa. By [[Lagrange's four-square theorem]], every natural number is the sum of the squares of four integers, so we could rewrite every natural-valued parameter in terms of the sum of the squares of four new integer-valued parameters. Similarly, since every integer is the difference of two natural numbers, we could rewrite every integer parameter as the difference of two natural parameters.{{sfn|Matiyasevich|1993}} Furthermore, we can always rewrite a system of simultaneous equations <math>p_1=0,\ldots,p_k=0</math> (where each <math>p_i</math> is a polynomial) as a single equation <math>p_1^{\,2}+\cdots+p_k^{\,2}=0</math>.