📄 Infinity in computable probability

Summary

The paper revisits the infinite monkey theorem. Classically, infinitely many random typists will almost surely produce a given text, such as Shakespeare's collected works. The authors ask whether that certainty helps anyone actually locate the successful typist when everything must be computable.

Working in Russian recursive mathematics, they use the singular covering theorem. This result says the unit interval can be covered by a computable sequence of rational open intervals whose partial length sums all stay below any chosen ε. From such a cover they build a non-uniform, computable assignment of success probabilities to an enumerable "monkeyverse". Under it, classically it is impossible that no monkey succeeds. Yet every finite initial group of monkeys succeeds with probability below ε. The construction depends only on ε, not on how many monkeys are searched. The result extends to listing all strings of a fixed length.

A counterweight theorem shows that such pathological distributions become rare as the searched group grows. This gives an a priori argument for large samples and repeated runs in computer simulations.

Key points

• Classical baseline. Take a 64-character alphabet with punctuation and capitals. A uniformly random 6-string equals "banana" with probability 1/64⁶ ≈ 1.5 × 10⁻¹¹. Real experiments are therefore hopeless even for short targets.
• A first non-uniform example (§3). A classical distribution built with Dirac-delta weights keeps success below ε within m monkeys but guarantees it at monkey m+1. Its drawback is that the distribution depends on m.
• Main result (Theorem 3). The key tool is the singular covering theorem (Tseitin & Zaslavsky 1956; Kreisel & Lacombe 1957).
  • Set ε′ = −log(1−ε) and build the cover (I_k) for ε′.
  • Assign p_k = exp(−|I_k|) as the failure probability of monkey k.
  • The product of the p_k classically tends to 0, yet every partial product stays above 1−ε.
• Corollary 4. Even target-free enumeration of all possible w-strings without repetition finishes in finite time only with arbitrarily small probability.
• Theorem 5. Over a group of m monkeys, the share of pathological distributions is at most ε^m, which vanishes as m grows. The authors conjecture that Theorem 3 has no classical analogue, because the covering theorem fails classically.

Interesting ideas

• I1. The paper separates two claims: that a solution exists somewhere in an infinite space, and that any finite search will find it with useful probability. The second is what matters for any system that searches.
• I2. Small per-step amounts (here −log of failure probabilities) can always sum below a bound while the infinite product still vanishes. This is a compact way to reason about cumulative risk across many independent trials.
• I3. The ε^m argument shows that a pathological generating process becomes exponentially unlikely to fool you as the number of independent samples grows. This justifies repeated runs before anything is computed.
• I4. Checking a finite output against a target is decidable. The hard part is the search order and the distribution over candidates, not the check itself.
• I5. The authors note that the candidate list can be cut by grammar checks before exhaustive enumeration, though worst-case completion remains unlikely. Filtering for well-formedness shrinks the space but does not remove the need for guided search.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

• I1 (learn): self-induced repair-rule search and self-play should report the probability of a hit within a fixed budget, not just whether a fix exists in principle.
• I2 (learn): summing log-failure rates of witness parsers over silver batches gives an explicit bound on how likely an agreed error is to slip through.
• I3 (learn): evaluation with negative controls should rerun on several independent samples, so that one unlucky split cannot look like a real gain.
• I4 (answer): when a solver enumerates candidate readings of a word problem, effort should go into ordering candidates well, since verifying each one is cheap.
• I5 (back): generation from the meaning graph should build only UD-valid realizations guided by the graph, rather than enumerating strings and filtering them afterwards.