Hilbert's tenth problem

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.