Hilbert's Tenth Problem - Diophantine Sets

Sets of natural numbers, of pairs of natural numbers (or even of n-tuples of natural numbers) that have Diophantine definitions are called Diophantine sets. Diophantine definitions can be provided by simultaneous systems of equations as well as by individual equations because the system

is equivalent to the single equation

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 intutitive notion of algorithmic computability, thus making the notion of recursive enumerability perfectly rigorous. It is evident that Diophantine sets are recursively enumerable. 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:

Every recursively enumerable set is Diophantine.

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, 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

with integer coefficients such that the set of values of for which the equation

has solutions in natural numbers is not computable. So, not only is there no general algorithm for testing Diophantine equations for solvability, even for this one parameter family of equations, there is no algorithm.