MathsClub Problems, proofs & good company

← All problems

Hilbert's Tenth Problem

historic

Posed by David Hilbert · 1900 · mathematical logic / number theory · resolved 1970

The problem

Hilbert asked for an effective procedure which, given a polynomial equation with integer coefficients, decides whether it has an integer solution. Resolution: no such algorithm exists — integer-solvability of polynomials is undecidable.

History & significance

The path ran through America and Russia: Davis's 1950s hypotheses, Putnam's sharpening, Julia Robinson's crucial conditions (1961 with Davis and Putnam), and the decisive young Matiyasevich (1970) proving exponentiation is Diophantine via Fibonacci-number growth. MRDP: recursively enumerable sets ARE Diophantine sets — a perfect dictionary between computability theory and number theory.