文档介绍：Brit. J. Phil. Sci. 51 (2000), 255–271
The Reliability of
Randomized Algorithms
Don Fallis
ABSTRACT
Recently, certain philosophers of mathematics (Fallis [1997]; Womack and Farach
[1997]) have argued that there are no epistemic considerations that should stop
mathematicians from using probabilistic methods to establish that mathematical
propositions are true. However, mathematicians clearly should not use methods that
are unreliable. Unfortunately, due to the fact that randomized algorithms are not really
random in practice, there is reason to doubt their reliability. In this paper, I analyze the
prospects for establishing that randomized algorithms are reliable. I end by arguing
that it would be inconsistent for mathematicians to suspend judgement on the truth of
mathematical propositions on the basis of worries about the reliability of randomized
algorithms.
1 Randomized algorithms
2 Proofs of reliability
3 Empirical evidence of reliability
4 Proofs of reliability revisited
5 Physical sources of randomness
6 ‘No experimental data are cited to support this claim’
7 Concluding remarks
1 Randomized algorithms
It is very time consuming to perform putational tasks—such as
determining whether or not a very large number is prime—using deterministic
algorithms. As a result, computer scientists have developed a large number
of randomized algorithms. A randomized—or probabilistic—algorithm is
an algorithm that makes several random choices during putation. For
example, a randomized algorithm might pick numbers at random—from a
finite set of numbers—in order to determine exactly which calculations
to perform. According to puter scientists Rajeev Motwani and
Prabhakar Raghavan, ‘for many applications, a randomized algorithm is the
simplest algorithm available, or the fastest, or both’([1995], p. ix).
In order to take advantage of the speed of randomized algorithms, however,
we have to be willing to give up a little bit of certainty. Rando