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

Frequently asked questions

Why couldn't Davis, Putnam, and Robinson finish the job in 1961?

Their 1961 result already reduced everything to Robinson's precisely-stated JR-hypothesis, but actually exhibiting a purely polynomial relation with genuine exponential growth — as opposed to using exponents directly, which is comparatively easy — required a genuinely new number-theoretic idea, which did not arrive until Matiyasevich's work in 1970.

Source

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

Matiyasevich theorem

Condensed summary

Step 5 of 9: Davis–Putnam–Robinson 1961: every r.e. set is exponential-Diophantine

Previous step Next step

In plain words

An "exponential Diophantine equation" is a more generous kind of equation than a plain polynomial one: it allows variables to appear in exponents too, like $x^y = z$ , not just multiplied and added together. In 1961, Martin Davis, Hilary Putnam, and Julia Robinson proved that with this extra generosity, every listable set can already be captured exactly — no exceptions.

This meant the entire remaining difficulty of Davis's original 1953 conjecture had been squeezed down to one precisely-stated technical obstacle: finding a way to push the exponents back down into ordinary polynomial form, which is exactly Robinson's JR-hypothesis from the previous step.

\text{r.e. set} \iff \exists \text{ exponential Diophantine eq. } Q(a, x_1, \ldots, x_k, y_1, \ldots, y_l) = 0,\ y_i \text{ appear as exponents}

Detailed analysis

An exponential Diophantine equation allows variables to occur as exponents, e.g. $Q(a, x_1, \ldots, x_k, y_1, \ldots, y_l) = 0$ where some of the $y_i$ appear as exponents somewhere in $Q$ ; a set $S$ is exponential-Diophantine if membership is expressible via such an equation the same way as for ordinary Diophantine sets.

In 1961, Davis, Putnam, and Robinson proved that every recursively enumerable set is exponential-Diophantine, by combining Davis's normal form (a single bounded universal quantifier) with Robinson's earlier existential-definability techniques for eliminating bounded quantifiers when exponential-sized building blocks (Pell-equation solutions, again) are available. This fully proved Davis's conjecture for the broader class of exponential equations, even though the original conjecture was about ordinary polynomial equations only.

The entire remaining gap between this 1961 result and Davis's full 1953 conjecture was now exactly Robinson's JR-hypothesis: find one purely polynomial (non-exponential) Diophantine relation with exponential growth, and every exponential Diophantine definition could be rewritten as an ordinary one. Closing this single remaining gap took until 1970, and is the subject of the next step.

Terms in this step

Exponential Diophantine equation: An equation built from addition, multiplication, and exponentiation with integer variables, such as $x^y + z = w$ , where variables (not just constants) are allowed as exponents — a strictly more expressive class of equations than ordinary polynomial equations.

Knowledge used in this step

Linear Diophantine equations