[FOM] on Martin Davis's "bounds and Hilbert's 10th Problem"

[Gabriel Stolzenberg]

   This is in response to Martin Davis's apparent belief that I am
skeptical that classical mathematicians are interested in realistic
bounds.  (Of course, for all I know, some are not.  But that's not
the point.)  I must have written something that encouraged this (to
put it kindly, as Martin does) "strange" idea.  But I have no idea
what it was.

   I begin with the relevant quote from Martin's message, followed
by my reply and then, for reference, the body of his message.

> This is in response to Gabriel's strange (to my mind) skepticism
> about the interest of mathematicians of the classical "mindset"
> about bounds.

   Martin, I don't see that we're on different sides.  The work you
describe, which seems terrific, is about realistic bounds for certain
important problems.

   My skepticism is only about the idea that EVERY bound or algorithm
is "intrinsically interesting" to classical mathematicians (and hence,
like Skewes' number, worth getting), no matter how unrealistic it is,
no matter that we have no idea how to use it to get a realistic bound
or algorithm and no matter that we didn't learn anything of value by
constructing it.

   Gabriel

_______________________________________________________________________
   Martin's message reads:

In my dissertation I proved that every r.e. set of natural numbers could
be defined by an expression of the form:
    (Ey)(Ak < y)(E x_1, ... , x_n) [p(x,k,y,x_1, ... , x_n) = 0]
where p is a polynomial with integer coefficients. The proof was easy
using methods of G?del, and it followed from general considerations that
there was an absolute upper bound on n, easily seen to be in the
neighborhood of 50. Soon thereafter, Raphael Robinson published a very
intricate proof that n could be taken to be 4. Much later, using MRDP
Matiyaevich showed that n=2 works.

MRDP itself showed that the bounded universal quantifier could be removed
from this expression raising the question of a bound on n on this simple
polynomial equation. In a paper published in Acta Arithmetica, Julia
Robinson and Yuri Matiyasevich showed that n=13 works. Refining their
techniques, Yuri later improved the result to n=9.

I have lectured about these matters many times over the years, and have
never failed to find intense interest in the bounds.

Martin
_________________________________________________________________________