Algorithmic Randomness: A General Framework

Title: Algorithmic Randomness: A General Framework

Research Question: How can we develop a framework for studying algorithmic randomness in a general space, allowing for non-compact spaces and arbitrary distributions?

Methodology: The study uses the concept of constructive topological spaces and measures over these spaces. It defines a uniform test, a lower semicomputable function that measures the deficiency of randomness. The paper also introduces neutral measures, which are measures that do not decrease randomness.

Results: The research shows that there is a universal test that is lower semicomputable and has strong properties of randomness conservation. It also demonstrates that there is a lower semicomputable semimeasure that is neutral. Furthermore, the paper provides an expression for mutual information in terms of the deficiency of independence.

Implications: This study extends the algorithmic theory of randomness to arbitrary Bernoulli distributions and arbitrary distributions, removing previous restrictions. It provides a general framework for studying these questions and related ones, such as statistics for a family of distributions. The results have implications for the understanding of randomness in general spaces, particularly in continuous spaces like the space of continuous functions.

Link to Article: https://arxiv.org/abs/0312039v3 Authors: arXiv ID: 0312039v3