[2] The MRDP theorem (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is computably enumerable.
This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or computability-theoretic terms.
Hilbert's tenth problem[4] was to find a general algorithm that can decide whether a given Diophantine equation has a solution among the integers.
The equation has a solution in y1 and y2 precisely when x can be expressed as a product of two integers greater than 1, in other words x is a composite number.
Earlier work by Julia Robinson, Martin Davis and Hilary Putnam – hence, MRDP – had shown that this suffices to show that every computably enumerable set is Diophantine.
Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations.
The conjunction of Matiyasevich's result with the fact that most recursively enumerable languages are not decidable implies that a solution to Hilbert's tenth problem is impossible.