Infinity in computable probability
Does combining a finite collection of objects infinitely many times guarantee the construction of a particular object? Here we use recursive function theory to examine the popular scenario of an infinite collection of typing monkeys reproducing the works of Shakespeare. Our main result is to show that it is possible to assign typing probabilities in such a way that while it is impossible that no monkey reproduces Shakespeare's works, the probability of any finite collection of monkeys doing so is arbitrarily small. We extend our results to target-free writing, and end with a broad discussion and pointers to future work.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Algorithmic learning of probability distributions from random data in the limit
We study the problem of identifying a probability distribution for some given randomly sampled data in the limit, in the context of algorithmic learning theory as proposed recently by Vinanyi and Chater. We show that the…
Learning TheoryLoss Bounds and Time Complexity for Speed Priors
This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that a…
On the computability of conditional probability
As inductive inference and machine learning methods in computer science see continued success, researchers are aiming to describe ever more complex probabilistic models and inference algorithms. It is natural to ask whet…
Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria
Bournez, Fraigniaud, and Koegler defined a number in [0,1] as computable by their Large-Population Protocol (LPP) model, if the proportion of agents in a set of marked states converges to said number over time as the pop…
Identification of Probabilities of Languages
We consider the problem of inferring the probability distribution associated with a language, given data consisting of an infinite sequence of elements of the languge. We do this under two assumptions on the algorithms c…