Hilbert's tenth problem

Solved, 1970Foundations of mathematicsArithmetic and number theoryHilbert #10

Statement

Devise a general algorithm that, given any Diophantine equation (a polynomial equation with integer coefficients in one or more unknowns), decides in finitely many steps whether it has a solution in integers.

The negative solution, now called the MRDP theorem (Matiyasevich–Robinson–Davis–Putnam), was built in stages. In 1953 Martin Davis conjectured that every recursively enumerable set of integers is exactly the solution set of some family of Diophantine equations — the key idea needed to transfer undecidability (from Turing's halting problem) to number theory. Julia Robinson identified an essential technical ingredient: a Diophantine relation that grows exponentially (the 'JR hypothesis'). In 1961 Davis, Hilary Putnam and Robinson proved a version of Davis's conjecture for exponential Diophantine equations, reducing the whole problem to finding one specific exponential-growth relation that is genuinely Diophantine (polynomial). Yuri Matiyasevich supplied that missing piece in 1970, showing the Fibonacci numbers satisfy a Diophantine condition, which completes the proof and shows no algorithm can exist.

Posed by, 1900David Hilbert Solved by, 1970Yuri Matiyasevich

The MRDP theorem shows Diophantine sets are exactly the recursively enumerable sets, with striking consequences: there is a single polynomial in several variables whose positive values, as the variables range over nonnegative integers, are exactly the prime numbers, and many other classically studied problems (existence of integer points on a variety, Fermat-type equations) inherit no general algorithmic test. The restricted version of the problem for equations in a fixed small number of variables, or over other rings such as the rational numbers $\mathbb{Q}$ (Hilbert's tenth problem over $\mathbb{Q}$ remains open as of 2026), is an active research area.

References

Yuri Matiyasevich (1970). Enumerable sets are Diophantine · DOI:10.1007/bf01693980
Yuri Matiyasevich (1993). Hilbert's Tenth Problem
Martin Davis (1973). Hilbert's Tenth Problem is Unsolvable · DOI:10.1080/00029890.1973.11993265

History of the problem

1900David Hilbert poses the problem as the tenth of his 23 problems at the International Congress of Mathematicians in Paris: find an algorithm that decides the solvability of any Diophantine equation.David Hilbert
1936Alan Turing and Alonzo Church give precise mathematical definitions of computation (Turing machines, the lambda calculus) and exhibit an undecidable problem — the halting problem — providing the tools needed to eventually prove that no algorithm for Hilbert's tenth problem can exist.Alan Turing
1953Martin Davis conjectures that every recursively enumerable set of integers coincides with the solution set of a family of Diophantine equations — the strategy that would eventually connect Turing's undecidability to number theory.
1961Martin Davis, Hilary Putnam and Julia Robinson prove the corresponding statement for exponential Diophantine equations, reducing Hilbert's tenth problem to a single, purely number-theoretic question about exponential growth.
1970Yuri Matiyasevich, building on Julia Robinson's earlier work isolating the missing ingredient, proves that the Fibonacci sequence is Diophantine, completing the Davis–Putnam–Robinson–Matiyasevich (MRDP) theorem and giving Hilbert's tenth problem a negative answer.Yuri Matiyasevich