Computability of probability measures and Martin-Lof randomness over metric spaces

2007/09/06 by Hoyrup, Mathieu, Rojas, Cristobal · 3 citations
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.0709.0907

Abstract

In this paper we investigate algorithmic randomness on more general spaces than the Cantor space, namely computable metric spaces. To do this, we first develop a unified framework allowing computations with probability measures. We show that any computable metric space with a computable probability measure is isomorphic to the Cantor space in a computable and measure-theoretic sense. We show that any computable metric space admits a universal uniform randomness test (without further assumption).

Cited by

• Irreversibility and randomness
• Computable thermodynamic formalism
• Computability for Axiom A Polynomial Skew Products of ℂ²

Related

• Algorithmic tests and randomness with respect to a class of measures
• Computable randomness and betting for computable probability spaces
• On the close interaction between algorithmic randomness and constructive/computable measure theory
• Computable randomness is about more than probabilities
• Measures and their random reals