Worked solution: The MRDP theorem: Diophantine sets are exactly the recursively enumerable sets (1970)

Frequently asked questions

Isn't every listable set obviously decidable, since you can eventually list all its members?

No — listing only ever confirms membership, by eventually seeing a number appear. For a number that is genuinely not a member, the listing process runs forever without ever giving a definitive "no"; this asymmetry between confirming "yes" and confirming "no" is the heart of undecidability.

Source

Yuri Matiyasevich, completing work of Martin Davis, Hilary Putnam, and Julia Robinson, 1970

Matiyasevich theorem

Condensed summary

Step 2 of 9: Diophantine sets versus recursively enumerable sets

Previous step Next step

In plain words

A set of numbers is "listable" (recursively enumerable) if some computer program, left running forever, will eventually print out every member of the set and nothing else — even if the program never finishes, and can never definitively say "no" for a number that is not a member. A set is "Diophantine" if membership in it can be expressed as some fixed polynomial equation, with the target number as a parameter, having an integer solution.

Every Diophantine set is automatically listable — just have the program try every possible tuple of nonnegative integers in order and print the parameter whenever it finds a solution. The deep, far less obvious question is the reverse: is every listable set secretly Diophantine too?

S \text{ Diophantine} \iff \exists P,\ a \in S \iff \exists x_1, \ldots, x_n \in \mathbb{Z}_{\ge0},\ P(a, x_1, \ldots, x_n) = 0

Detailed analysis

A set $S \subseteq \mathbb{Z}_{\ge 0}$ is recursively enumerable (r.e.), or listable, if there is an algorithm that, given enough time, outputs exactly the elements of $S$ in some order (with no guarantee of ever halting, and no requirement to say anything about non-members). A set $S$ is Diophantine if there is a polynomial $P$ with integer coefficients such that $a \in S \iff \exists x_1, \ldots, x_n \in \mathbb{Z}_{\ge0}$ with $P(a, x_1, \ldots, x_n) = 0$ .

The implication "Diophantine $\implies$ r.e." is immediate: dovetail through all tuples $(x_1, \ldots, x_n)$ and all candidate values of $a$ , outputting $a$ whenever a solution is found. The implication in the other direction — every r.e. set is Diophantine — is far from obvious, since polynomial equations look like a much more rigid, purely algebraic tool than the flexible step-by-step logic of an arbitrary algorithm.

Martin Davis conjectured in 1953 that the two notions do in fact coincide exactly; the next step states this conjecture and its significance precisely.

Terms in this step

Recursively enumerable (listable) set: A set for which some algorithm, run forever, eventually outputs every member (and only members); such a set need not be decidable, since the algorithm may never confirm that a given non-member will never appear.

Knowledge used in this step

Recursive functions and Turing machines