FOM: Probabilistic proofs

[Don Fallis]

At 05:23 PM 9/21/98 -0400, Joe Shipman wrote:
>I think you're ignoring a critical distinction here.  Rabin's
>algorithm is backed by a real proof; the only reason not to believe
>that a number is prime after it has passed Rabin's test for 500
>randomly chosen witnesses (with the random input taken from a
>published table of random numbers generated by a physical process) is
>that you have somehow made a mistake in running the algorithm ....

I think that for the most part we are in agreement.  We both think that at
least some probabilistic methods (including Rabin's test) should count as
proofs.  Also, we both think that some probabilistic methods should not
count as proofs.  For instance, I would certainly not dispute your claim
that the evidence that we currently have for the Riemann hypothesis does
not rise to the level of proof.

Even so, I think that we may have a disagreement over what criteria must be
satisfied in order for something to count as a proof.  First, while I agree
that Rabin's conventional mathematical proof gives us a very high degree of
confidence that a number is prime when Rabin's test says that it is, I am
not convinced that a conventional mathematical proof is the ONLY way that
we could achieve such confidence in a probabilistic method.  Second, I am
not sure that a high degree of certainty is all that it takes for something
to count as a proof.  In any case, it is pretty clear that mathematicians
do not think that a high degree of certainty is all that it takes.

Rabin's test pretty clearly provides a very high degree of certainty that a
number is prime.  (However, since we don't know how to compute the
probability that our source of "random" numbers is sufficiently random, I
don't think that we can really compute a numerical bound on the probability
that a number is prime when Rabin's test says that it is.)  In fact, it
arguably provides a higher degree of certainty than many conventional
mathematical proofs.  Nevertheless, most mathematicians do not think that
Rabin's test should count as a proof even when they accept that Rabin's
test provides an arbitrarily high degree of certainty.

As a result, in order to establish that (at least some) probabilistic
methods should count as proofs, one has to do more than argue that they
provide a very high degree of certainty.  In addition, one has to argue
that there is no other epistemic benefit of conventional mathematical
proofs that these probabilistic methods cannot also provide.  This is what
I try to do in my article on probabilistic proofs.  

take care,
don

Don Fallis
Assistant Professor
School of Information Resources & Library Science
University of Arizona