Probabilistic algorithm

The terms probabilistic method and probabalistic algorithm are used for methods of approximate calculation based on probability theory, e.g., monte-carlo algorithms, simulated annealing etc.

For example, there exist probabilistic algorithms for proving primality, where the probability of error can be reduced to an arbitary degree by performing enough independent tests.

If, using such a method, the probability of error is 2^-1000, the philosophical question arises: is this a proof? After all the probability of error is distinctly smaller than the probability of an error in the reader's computer, or the reader themselves making an error in reading a proof - what does it mean in real terms to consider this small a probability?

If that does not seem extreme enough to be perplexing, consider a proof with an error probability of 2^-1000000: the user only has to leave the computer running the probabilistic algorithm running a little longer. At this level, the odds against error are not only astronomically, but also cosmologically vast.