Gacs, Peter2018-06-192018-06-192005-09-05P Gacs. 2005. "Uniform test of algorithmic randomness over a general space." Theoretical Computer Science, Volume 341, Issue 1-3, pp. 91 - 137 (47). https://doi.org/10.1016/j.tcs.2005.03.0540304-3975https://hdl.handle.net/2144/29417The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. These restrictions seem artificial. Some progress has been made to extend the theory to arbitrary Bernoulli distributions (by Martin-Löf) and to arbitrary distributions (by Levin). We recall the main ideas and problems of Levin's theory, and report further progress in the same framework. The issues are the following: Allow non-compact spaces (like the space of continuous functions, underlying the Brownian motion). The uniform test (deficiency of randomness) (depending both on the outcome x and the measure P) should be defined in a general and natural way. See which of the old results survive: existence of universal tests, conservation of randomness, expression of tests in terms of description complexity, existence of a universal measure, expression of mutual information as “deficiency of independence”. The negative of the new randomness test is shown to be a generalization of complexity in continuous spaces; we show that the addition theorem survives. The paper's main contribution is introducing an appropriate framework for studying these questions and related ones (like statistics for a general family of distributions).p. 91 - 137Science & technologyTechnologyComputer science, theory & methodsComputer scienceAlgorithmic information theoryAlgorithmic entropyRandomness testKolmogorov complexityDescription complexityInformation and computing sciencesMathematical sciencesComputation theory & mathematicsArticle10.1016/j.tcs.2005.03.054