Algorithmic Randomness on Computable Metric Spaces

28 concepts13 papers1 proposal

Classical algorithmic randomness—pioneered by Per Martin-Löf—traditionally operates on the Cantor space, the set of all infinite binary sequences. In this discrete setting, a sequence is deemed "random" if it avoids all effectively implementable constructive null sets (tests of typicality). However, the physical and mathematical worlds are rarely just sequences of bits; they consist of continuous surfaces, high-dimensional spaces, and complex dynamical trajectories.

To understand randomness in these realistic settings, researchers have extended algorithmic information theory to arbitrary metric spaces. The core challenge is foundational: how can a discrete, finite computer rigorously reason about randomness in an uncountable, continuous space?

From Bits to Open Balls

The bridge between discrete computation and continuous spaces is the concept of a computable metric space. We cannot store an arbitrary point of a continuous space in a computer's memory with absolute precision. Instead, we select a countable, dense subset of "ideal" points (analogous to how the rational numbers are dense within the real numbers) and require that the distances between these ideal points can be computed to arbitrary precision.

This structure allows us to specify any point in the space by a sequence of increasingly small open balls centered around these ideal points. As demonstrated by Mathieu Hoyrup et al. in Computability of probability measures and Martin-Löf randomness over metric spaces, any computable metric space equipped with a computable probability measure is fundamentally isomorphic to the Cantor space.

Think of this as a generalized binary expansion. Just as a real number in the interval $[0,1]$ can be pinned down by a sequence of left-or-right choices (bits), a point in a metric space can be isolated by a sequence of nested open sets. This "binary representation" serves as a direct mechanism to transfer randomness concepts from binary strings to abstract topological spaces. Building on this framework, Péter Gács et al. showed in Randomness on Computable Probability Spaces - A Dynamical Point of View that these mappings act as computable transformations that preserve randomness, allowing researchers to study chaotic dynamical systems by analyzing whether their trajectories behave typically.

Redefining Randomness Tests

In the Cantor space, different definitions of randomness emerge depending on how we formalize a "fair test." Generalizing these tests to metric spaces requires redefining the mathematical objects used to measure a strategy's success.

Generalizing Betting Strategies

Computable randomness is classically defined via martingales—betting strategies where a computer program gambles on the successive bits of a sequence. If no computable strategy can achieve infinite wealth, the sequence is random. To port this intuition to non-binary spaces, Jason Rute introduced a "cell decomposition" method in Computable randomness and betting for computable probability spaces. Instead of betting on binary branches, the algorithm bets on sequences of almost-everywhere decidable sets that partition the metric space into finer and finer cells. This ensures that the gambling intuition remains robust and base-invariant across diverse mathematical structures.

Conservation of Randomness

A critical sanity check for any theory of randomness is the "no-randomness-from-nothing" principle: a computable process should not be able to turn a non-random input into a random output. In When does randomness come from randomness?, Jason Rute abstracted this analysis to arbitrary computable metric spaces, proving that Martin-Löf randomness is the weakest standard notion that successfully conserves randomness under computable maps.

The Challenge of Uncomputable Measures

Standard algorithmic randomness assumes that the underlying probability distribution is itself computable. This assumption fails when modeling real-world processes governed by uncomputable parameters—such as a physical coin whose exact bias is an uncomputable real number.

To bypass this limitation, Laurent Bienvenu et al. introduced "uniform tests" in Algorithmic tests and randomness with respect to a class of measures. Instead of evaluating a sequence against a fixed, known measure, a uniform test evaluates the sequence and the measure simultaneously. By treating the measure as an input to the test, the computational bound scales dynamically with the complexity of the distribution itself.

Standard Test:       Sequence ───► [ Test (Fixed Measure) ] ───► Random / Non-Random

Uniform Test:        Sequence ───┐
                                 ├──► [ Uniform Test ] ────────► Random / Non-Random
                     Measure  ───┘

Using a similar philosophy of uniformization, Jason Rute demonstrated in Schnorr randomness for noncomputable measures that by using uniform integral tests, Schnorr randomness preserves its core structural properties—such as Van Lambalgen’s theorem—even when the underlying probability measures are entirely noncomputable.

The Computational Limits of Measure Theory

When classical theorems of probability and measure theory are re-examined through the lens of computable metric spaces, unexpected computational barriers and boundaries are revealed.

  • De Finetti's Theorem: In Computable de Finetti measures, Cameron E. Freer et al. provided a constructive proof showing that exchangeable stochastic processes can be computably inverted into their underlying mixing measures, justifying the automation of state-free procedures in probabilistic programming.
  • The Radon-Nikodym Derivative: In Computability of the Radon-Nikodym Derivative, Mathieu Hoyrup et al. analyzed the density change between two measures. They proved that computing this derivative is not fully computable, but its complexity is precisely bounded by a single application of a known non-computable operator.
  • Conditional Probability: Most strikingly, Nathanael L. Ackerman et al. proved a fundamental negative result in On the Computability of Conditional Probability. They showed that conditioning is fundamentally non-computable: a perfectly computable joint probability distribution on a metric space can yield a conditional distribution that encodes the halting problem, exposing an absolute mathematical barrier to universal inference algorithms.
  • Convergence Complexity: As Jeremy Avigad et al. established in Algorithmic randomness, reverse mathematics, and the dominated convergence theorem, lifting measure-theoretic proofs from the Cantor space to compact separable metric spaces fundamentally alters their logical strength, requiring more complex formalizations to guarantee convergence.

By shifting the domain of algorithmic randomness from binary strings to computable metric spaces, this research direction establishes exactly when continuous probabilistic phenomena can be simulated, predicted, or certified as truly random by digital machines.

Key Foundational Work

Computability of probability measures and Martin-Löf randomness over metric spaces (2009) — contributed 6 concept elements to this direction.
Computable de Finetti measures (2009) — contributed 4 concept elements to this direction.
06051 Abstracts Collection -- Kolmogorov Complexity and Applications (2006) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computable_metric_space_generalization_e5a41383,
  title = {computable metric space generalization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computable-metric-space-generalization/rdr_e5a4138319ce49ad822f41b94db0af63},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_computable_metric_space_generalization_e5a41383_v1,
  title = {computable metric space generalization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computable-metric-space-generalization/rdr_e5a4138319ce49ad822f41b94db0af63/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake