MathLabs

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

Step 1 of 9: Hilbert's tenth problem: an algorithm for Diophantine equations?
Previous stepNext step
In plain words

A Diophantine equation is a polynomial puzzle where only whole-number answers count, like x2+y2=z2x^2+y^2=z^2 (which has solutions — the Pythagorean triples) or, famously, xn+yn=znx^n+y^n=z^n for n≥3n \ge 3 (which Fermat's Last Theorem says has none). In 1900, David Hilbert asked, as the tenth of his 23 famous problems, for a single universal recipe that, fed any such equation, always correctly answers "yes, it has an integer solution" or "no, it doesn't".

At the time, "algorithm" was an informal notion; only in the 1930s did Alan Turing and Alonzo Church pin the concept down precisely enough for anyone to prove a definitive "no such algorithm exists" answer to a question like this one.

P(x1,…,xn)=0,P∈Z[x1,…,xn]P(x_1, \ldots, x_n) = 0, \quad P \in \mathbb{Z}[x_1, \ldots, x_n]
Detailed analysis

Hilbert's tenth problem, posed in his 1900 address to the International Congress of Mathematicians, asks for an algorithm that decides, for any polynomial P(x1,…,xn)P(x_1, \ldots, x_n) with integer coefficients, whether the equation P(x1,…,xn)=0P(x_1, \ldots, x_n) = 0 has a solution in integers. Some classes were already known to be fully decidable: linear Diophantine equations (via the Euclidean algorithm and gcd⁡\gcd), and, by the 1920s, general degree-two equations in two variables via continued fractions and the theory of Pell equations.

General higher-degree, many-variable equations resisted every classical technique, and the problem sat unsolved for over half a century, awaiting a precise mathematical definition of "algorithm" itself. That definition arrived in the 1930s through Turing machines and the equivalent formalisms of Church and Gödel, finally making it possible to prove a rigorous impossibility result rather than merely fail to find a method.

The key to attacking the problem, developed from the 1950s onward, was to compare the algebraic notion of a Diophantine equation directly against the computability-theoretic notion of a "listable" set — the subject of the next step.

Terms in this step
Diophantine equation
A polynomial equation P(x1,…,xn)=0P(x_1, \ldots, x_n) = 0 with integer coefficients, for which only integer (or sometimes nonnegative integer) solutions are of interest, named after the ancient mathematician Diophantus.
Algorithm (decision procedure)
A finite, mechanical, step-by-step procedure that is guaranteed to halt and give the correct yes/no answer for every possible input; made mathematically precise in the 1930s via Turing machines and equivalent formalisms.
Knowledge used in this step
Recursive functions and Turing machinesLinear Diophantine equations