# “Positive Aspects of a Negative Solution”

The title of this section reproduces part of the title of [12], the joint paper of Martin Davis, Julia Robinson, and myself written for the Proceedings of Symposium on Hilbert’s problems [2]. The undecidability of Hilbert’s tenth problem is just one of the corollaries of the DPRM-theorem. Actually it can serve as bridge for transferring ideas and results from Computability Theory to Number Theory; a few of such applications are given below.

## Speeding Up Diophantine Equations

A simplest form of such transfer is as follows: *take any theorem about listable sets and replace them by Diophantine sets.* For example, one can explicitly write down a polynomial (2.5) with the set of its positive values being exactly the set of all prime numbers; the supposed impossibility of such a definition of primes was considered by many number-theorists as an informal argument against Martin Davis Conjecture.

It is quite typical that the map “listable” ^ “Diophantine” produces theorems not conventional for Number Theory. For example, Martin Davis published in [10] the following Diophantine counterpart of Manuel Blum’s [1] *speed-up theorem.*

Theorem *For every general recursive function a(a, w) there are Diophantine equations
*

*such that:*

- •
*for every value of a one and only one of these two equations has a solution;* - •
*if equations*

*are solvable exactly for the same values of the parameter a as Eqs.*(2.20) *and *(2.21) *respectively, then there is third pair of equations*

*such that:*

- -
*these equations are also solvable exactly for the same values of the parameter a as Eqs.*(2.20)*and*(2.21)*respectively;* - -
*for almost all a for every solution of equation*(2.22)*(Eq.*(2.23))*there is solution of equation*(2.24)*(respectively, Eq.*(2.25))*such that*

(*or
*

*respectively*)*.*

This theorem in its full generality is about an arbitrary general recursive function; replacing it by any particular (growing fast) function we obtain theorems which are purely number-theoretical but quite non-standard for Number Theory.