  The 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-Loef), 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.
  - We allow non-compact spaces (like the space of continuous functions,
underlying the Brownian motion).
  - The uniform test (deficiency of randomness) d_P(x) (depending both on the
outcome x and the measure P should be defined in a general and natural way.
  - We 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).

Computational Complexity