Long after Alan Turing and Alonzo Church had proved that there can be no general decision procedure for first-order logic, the very first decision problem was still unresolved. This was the famous Tenth Problem listed by David Hilbert in his address to the International Congress of Mathematicians in 1900 as one of the challenges facing mathematicians of the twentieth century:

10. Determination of the Solvability of a Diophantine Equation

Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: *To devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.*^{1}

The algebra problems created by third-century Alexandrian mathematician Diophantus in his *Arithmetica* can always be expressed as polynomials with integer coefficients and multiple variables. Hilbert's Tenth Problem asked for a general process to show if a particular Diophantine equation has a solution in whole numbers.

Of course, after Gödel's Incompleteness Theorem and the undecidability results of Church and Turing, few mathematicians expected anyone to fulfill Hilbert's wish and actually “devise a process” to determine the solvability of Diophantine equations. Pretty much everyone expected a negative result — a proof that such a general process was impossible.

Many mathematicians were fascinated by the Tenth Problem, and at least one devoted almost ...

Start Free Trial

No credit card required