FOM: Mathematical and moral certainty

[urquhart@urquhart.theory.toronto.edu]

In a sense, I think Martin Davis is right when he says:

	I believe the only reason for believing that this "axiom" is true, is that 
	no one has succeeded in finding an efficient algorithm for factoring. There 
	are certainly cases where clever unsuspected algorithms have been found 
	cutting down the computational time needed for certain problems.

However, there is a sense in which I disagree with him.  There is a strong
distinction to be drawn between problems that virtually no-one has
thought about and problems like factoring towards which several centuries
of effort have been devoted, including intensive efforts in the
last few decades.  The last few years, in fact, have seen substantial
progress (for which see the very nice and attractive textbook "Modern
Computer Algebra" by Joachim von zur Gathen and Juergen Gerhard).

To take a somewhat different example, it is, I think, essentially certain
that with best play the game of checkers ends in a draw.  It would
not be an exaggeration to say that we "know" this.  Nevertheless, 
there is no mathematical proof; for a very good discussion of the 
sense in which the game of checkers can be said to be "solved" see
the paper by Jonathan  Schaeffer in "Games of No Chance."
The same is almost certainly true for chess, but with a lower degree
of confidence.

These questions have some real foundational and philosophical significance.
For example, they affect the direction of our research.  If you believe
strongly that P is true, then you should try to prove P.  But suppose
there is in fact no good reason to believe P.  Then you are wasting your
time, and should instead be looking for counter-examples.

In my opinion, the literature on foundations does not contain enough
discussion of these very interesting epistemological issues.

Alasdair Urquhart