Editing Hilbert's tenth problem (section)

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