412 | 37 DECIDABIlITy AND THE ENTSCHEIDUNGSPROBLEM
Turing’s prototype undecidable problem, the Entscheidungsproblem, so showing that the tenth
problem, too, is unsolvable?
The story of this reduction is a fascinating one, and involves a seemingly extraordinary
equivalence. We have seen that enumerable sets are those whose members can be listed system-
atically by a computer program. ‘Diophantine sets’ are those for which a Diophantine equation
exists, one particular variable of which determines membership of the set. Recall Fermat’s equa-
tion xynnn+=z (not quite Diophantine but never mind). It defines a set of all values of n for
which the equation is solvable in positive integers. The set begins {1, 2, . . .}. And Fermat’s last
theorem says those two are its only members. Well, this set is certainly enumerable. But what
about any other enumerable set? What about, say, the prime numbers {2, 3, 5, 7, 11, . . .}: is this
notorious set actually Diophantine?
In 1950 Princeton and Alonzo Church re-enter our story, through the work of Church’s PhD
student Martin Davis, whose dissertation contains a bold, not-to-say brash, proposal, known
as ‘Davis’s conjecture’:
All enumerable sets are Diophantine sets.
To cut a twenty-year story short, Davis’s conjecture is true. It took the combined efforts of
Martin Davis, Hilary Putnam, Julia Robinson, and Yuri Matiyasevich, himself a PhD student
in Leningrad, to prove this. The proof appeared in 1970 and is known as the ‘DPRM theorem’
(after the initials of these mathematicians):
A set is enumerable if and only if it is a Diophantine set.
An immediate corollary of this theorem is: no algorithm can exist for solving general
Diophantine equations. Such an algorithm would automatically decide membership of any
enumerable set. And we know this to be impossible: provable statements are enumerable, as we
have seen, but Turing showed that no computer program can decide whether a given statement
belongs to the set of provable ones.
DPRM has some surprising additional consequences—surprising enough for Davis’s orig-
inal conjecture to have been treated with much scepticism. One is that there is a universal
Diophantine equation in a fixed number of variables that simulates any given Diophantine
equation, by making a suitable choice of one of the variables. Matiyasevich even put a value on
the number of variables: it can be as low as 9. This universality result relates directly to Turing’s
idea of a universal Turing machine.
A more immediate, and more amazing, consequence of the DPRM theorem is that, for any
enumerable set E, there is a polynomial whose positive values are precisely the members of E.
Think of any conjecture; it is likely that any counter-examples can be enumerated; for example,
the set of counter-examples to Goldbach’s conjecture that any even number greater than 2 is the
sum of two primes, or the set of counter-examples to the Riemann hypothesis (see Chapter 36).
Then there is a polynomial whose positive values are precisely these counter-examples!
No wonder mathematicians in the 1950s were dubious: even a polynomial taking exactly
the prime numbers as its positive values seemed a far-fetched notion! Nevertheless, the proof
of the DPRM theorem spurred mathematicians to find such a polynomial, and several are now
known. Perhaps the most elegant is the following, in twenty-six variables.^5 It may look hor-
rendous, but if you substitute any whole numbers you wish for each of the twenty-six variables
a, b, c, . . . , z, and if the resulting number you get is positive, then this number must be a prime.