Computability of probability measures and Martin-Löf randomness over metric spaces
Computability of probability measures and Martin-Löf randomness over metric spaces
复制标题
概率测度的可计算性和度量空间上的 Martin-Löf 随机性
DOI：
10.1016/j.ic.2008.12.009
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Cristobal Rojas
中科院分区：
文献类型：
--
作者：
M. Hoyrup;Cristobal Rojas
在本文中，我们研究算法的随机性更一般的空间比康托空间，即可计算度量空间。要做到这一点，我们首先开发一个统一的框架，允许计算的概率措施。我们表明，任何可计算的度量空间与可计算的概率测度同构的康托空间在可计算和测量理论的意义。我们表明，任何可计算的度量空间承认一个普遍的一致随机性测试（没有进一步的假设）。
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).