Editing Hilbert's tenth problem (section)

==Background==
=== Original formulation ===
Hilbert formulated the problem as follows:{{sfn|Hilbert|1902|p=458}}

<blockquote>''Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients:'' ''To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.''</blockquote>

The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an [[algorithm]]. The term "rational integral" 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.

Hilbert's problem is not concerned with finding the solutions. It only asks whether, in general, we can decide whether one or more solutions exist. The answer to this question is negative, in the sense that no "process can be devised" for answering that question. In modern terms, Hilbert's 10th problem is an [[undecidable problem]].

===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>.

=== Recursively enumerable sets ===

A [[recursively enumerable set]] can be characterized as one for which there exists an [[algorithm]] that will ultimately halt when a member of the set is provided as input, but may continue indefinitely when the input is a non-member. It was the development of [[computability theory]] (also known as recursion theory) that provided a precise explication of the intuitive notion of algorithmic computability, thus making the notion of recursive enumerability perfectly rigorous. It is evident that Diophantine sets are recursively enumerable (also known as semi-decidable). This is because one can arrange all possible tuples of values of the unknowns in a sequence and then, for a given value of the parameter(s), test these tuples, one after another, to see whether they are solutions of the corresponding equation. The unsolvability of Hilbert's tenth problem is a consequence of the surprising fact that the converse is true:
<blockquote>''Every recursively enumerable set is Diophantine.''</blockquote>
This result is variously known as [[Matiyasevich's theorem]] (because he provided the crucial step that completed the proof) and the [[MRDP theorem]] (for [[Yuri Matiyasevich]], [[Julia Robinson]], [[Martin Davis (mathematician)|Martin Davis]], and [[Hilary Putnam]]). Because ''there exists a recursively enumerable set that is not computable,'' the unsolvability of Hilbert's tenth problem is an immediate consequence. In fact, more can be said: there is a polynomial 
:<math>p(a,x_1,\ldots,x_n)</math>
with integer coefficients such that the set of values of <math>a</math> for which the equation
:<math>p(a,x_1,\ldots,x_n)=0</math>
has solutions in natural numbers is not computable. So, not only is there no general algorithm for testing Diophantine equations for solvability, but there is none even for this family of single-parameter equations.