“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



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.

< Prev   CONTENTS   Source   Next >