Traditional algorithmic information theory was built for a world of bits. It tells us what it means for an infinite sequence of 0s and 1s to be "random." But the physical and mathematical worlds are rarely just binary strings; they consist of continuous spaces, manifolds, and complex dynamical systems.
To bridge this gap, researchers have extended the theory of randomness to computable metric spaces. This allows us to rigorously define what it means for an individual point on a fractal, a real number on a line, or a state in a physical system to be "algorithmically random."
The Scaffolding of Continuous Spaces
How does a computer, which is inherently discrete, reason about a continuous space like a sphere or a Hilbert space? The solution, formalized by Mathieu Hoyrup and Cristobal Rojas in Computability of probability measures and Martin-Lof randomness over metric spaces, is the computable metric space.
A computable metric space is built on three pillars:
- A set $X$: The space itself (e.g., the unit interval $[0,1]$).
- A metric $d$: A way to calculate distances.
- A dense sequence of "ideal" points: A countable set of points that act as a "scaffolding."
Think of the rational numbers within the real numbers. While there are uncountably many reals, we can approximate any real number to arbitrary precision using rationals. In a computable metric space, an algorithm can compute the distance between any two of these "ideal" points. This structure allows us to represent any point in the space as a sequence of approximations, bringing continuous geometry into the realm of Turing machines.
Randomness as Typicality
In the binary world, a sequence is Martin-Löf random if it passes all "effective" statistical tests. A test is essentially a way to describe a set of "atypical" sequences that have a total probability of zero. If a sequence avoids all such sets, it is random.
Hoyrup and Rojas demonstrated that this logic carries over to metric spaces. They proved that universal randomness tests exist for all computable metric spaces. This means we don't need a new definition of randomness for every new space; the same algorithmic framework that identifies a random bitstring can identify a random point on a complex manifold.
The Ergodic Connection
Why does this matter? One of the most powerful applications is in dynamical systems. Stefano Galatolo, Rojas, and Hoyrup explored this in Effective Symbolic Dynamics, Random Points, Statistical Behavior, Complexity and Entropy.
In physics, we often assume that "most" points in a system will behave predictably over time (the Law of Large Numbers). However, "most" is a measure-theoretic statement that doesn't tell us how a specific point will behave. By using algorithmic randomness, Péter Gács and Mathieu Hoyrup proved a fundamental equivalence: a point is Schnorr random if and only if it satisfies the Law of Large Numbers for every "mixing" computable dynamical system (Randomness on Computable Probability Spaces - A Dynamical Point of View).
This provides a bridge between the individual (algorithmic complexity) and the ensemble (ergodic theory).
Generalizing the Measure
Early randomness theory assumed the underlying probability measure (like a fair coin flip) was itself computable. But what if the "physics" of our system is governed by an uncomputable parameter?
Laurent Bienvenu, Alexander Shen, and others addressed this by developing uniform tests in Algorithmic tests and randomness with respect to a class of measures. These tests evaluate the point and the measure simultaneously.
Jason Rute further refined this in Schnorr randomness for noncomputable measures, showing that even when measures are noncomputable, the core properties of randomness—like the fact that a random pair $(x, y)$ implies $x$ is random and $y$ is random relative to $x$ (Van Lambalgen’s Theorem)—still hold.
Conservation of Randomness
A critical question in this field is: can a computer program create randomness out of nothing? In When does randomness come from randomness?, Jason Rute investigated the "no-randomness-from-nothing" principle.
He found that if you put a random input into a computable function, the output is often random. More importantly, if the output is random, it must have come from a random input. This property is satisfied by Martin-Löf randomness but, surprisingly, fails for the weaker Schnorr randomness. This highlights why Martin-Löf randomness remains the "gold standard" for defining typicality in complex spaces.
By moving beyond binary strings, this research direction transforms algorithmic randomness from a niche subfield of logic into a robust tool for understanding the limits of computation in the physical and mathematical sciences. Whether analyzing Julia sets in Computable geometric complex analysis and complex dynamics or Brownian motion in Energy randomness, the framework of computable metric spaces provides the necessary language to talk about the complexity of the continuous world.