O'Reilly logo

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine by Charles Petzold

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

18  The Long Sleep of Diophantus

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required