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

DOI10.1016/J.IC.2008.12.009MaRDI QIDQ6206710arXivFDO

Authors Mathieu Hoyrup, Cristobal Rojas

Publication date 6 September 2007

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

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).

This page was built for publication: Computability of probability measures and Martin-Lof randomness over metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6206710)