The Last Step
The DPR-theorem was a milestone on the way to proving Davis conjecture. All what remained to do was to prove a particular case of Davis conjecture, namely, to show that exponentiation is Diophantine. Indeed, suppose that we found a particular Diophantine equation
which for given values of the parameters a, b, and c has a solution in xi,.., xn if and only if a = bc. Using several copies of such an equation, one can easily transform an arbitrary exponential Diophantine equation into a genuine Diophantine equation (with additional unknowns) such that either both equations have solutions or none of them has.
In fact, Julia Robinson was tackling this problem from the beginning of the 1950s. It is instructive to note that her interest was originally stimulated by her teacher, Alfred Tarski, who asked one to prove that the set of all powers of 2 is not Diophantine. That is, the intuition of young Martin Davis was opposite to the intuition of venerable Alfred Tarski.
Julia Robinson was not able to construct the required equation (2.9) but she found [48, 50] a number of conditions sufficient for its existence. In particular she proved that in order to construct such an A, it is sufficient to have an equation
which defines a relation J(a, b) with the following two properties:
- • for any a and b, J(a, b) implies that a < bb;
- • for any k, there exist a and b such that J(a, b) and a > bk.
Julia Robinson called a relation J with these two properties a relation of exponential growth; Martin Davis named them Julia Robinson predicates.
In 1970 I [29] was able to construct the first example of a relation of exponential growth, and it was the last link in the proof of Davis conjecture. Nowadays it is often reffered to as
DPRM-theorem. Every listable set of m-tuples of natural numbers has a Dio- phantine representation.
This theorem implies, in particular, the undecidability of Hilbert’s tenth problem: There is no algorithm for deciding whether a given Diophantine equation has a solution.
