Infinity in Computable Probability
Introduction: Since at least the time of Aristotle [1], the concept of combining a finite number of objects infinitely many times has been taken to imply certainty of construction of a particular object. In a frequently-encountered modern example of this argument, at least one of infinitely many monkeys, producing a character string equal in length to the collected works of Shakespeare by striking typewriter keys in a uniformly random manner, will with probability one reproduce the collected works. In the following, the term “monkey” can (naturally) refer to some (abstract) device capable of producing sequences of letters of arbitrary (fixed) length at a reasonable speed. Recursive function theory is one possible model for computation; Russian recursive mathematics is a reasonable formalization of this theory [4].1 Here we show that, surprisingly, within recursive mathematics it is possible to assign to an infinite number of monkeys probabilities of reproducing Shakespeare’s collected works in such a way that while it is impossible that no monkey reproduces the collected works, the probability of any finite number of monkeys reproducing the works of Shakespeare is arbitrarily small. The method of assigning probabilities depends only on the desired probability of success and not on the size of any finite subset of monkeys. Moreover, the result extends to reproducing all possible texts of any finite given length. However, in the context of implementing an experiment or simulation computationally (such as the small-scale example in [10]; see also [7]), the fraction among all possible probability distributions of such pathological distributions is vanishingly small provided sufficiently large samples are taken.
