Suppose a problem has been modeled as a Diophantine equation

D(x_1,…,x_n)=0

in any number n of unknowns, to be solved over the integers: here D can be a polynomial of any degree, with integer coefficients. It is not difficult to design a program which, given D, internally generates the n-tuples x_1,…,x_n of integers and prints the ones which solve the equation. The process can go on for ever—after all, there could be infinitely many solutions—, but what if we simply wanted to know whether the equation has a solution or not?

Finding an algorithm which, given D, says whether or not there is a solution, appeared tenth in a list of open problems proposed by David Hilbert at the beginning of the XX century. This challenge promoted theoretical investigations which contributed to the early developments of computer science.

Much like the more demanding Entscheidungsproblem, also Hilbert’s Tenth received a negative answer: “no such algorithm exists”.

This talk offers a historical recollection of the main achievements which led to this renowned negative result, often referred to as DPRM (Davis-Putnam-Robinson-Matiyasevich); those achievements have set up a formidable—but by no means abstruse—combinatorial machinery, teaching us how to model whatsoever computation by way of Diophantine polynomial equations.

Famous problems, such as the Goldbach conjecture, can be cast as assertions that some single Diophantine equation has no solution: they could have been settled, in principle, by a positive solution to Hilbert’s Tenth. A joint paper by Davis, Matijasevi\v{c} and Robinson points the opposite direction: “all mathematical methods can be tools in the theory of Diophantine equations and perhaps we should consciously attempt to exploit them”.