Algorithmic Randomness: A General Framework

Title: Algorithmic Randomness: A General Framework

Research Question: How can we extend the algorithmic theory of randomness to arbitrary distributions and non-compact spaces while maintaining its key properties?

Methodology: The study uses the framework of constructive topology and lower semicomputable functions to define a uniform test of randomness. This test is used to measure the deficiency of randomness, which is the difference between the original measure and the test. The paper also introduces the concept of neutral measures, which are measures that do not decrease randomness.

Results: The main results include the existence of a universal test that is lower semicomputable and has strong properties of randomness conservation. The paper also shows that there is a lower semicomputable semi-measure that is neutral. Additionally, the study provides an expression for mutual information in terms of the deficiency of independence.

Implications: The research has implications for the field of algorithmic information theory and randomness. By extending the theory to arbitrary distributions and non-compact spaces, it opens up new possibilities for studying randomness in a more general context. The paper also provides a new interpretation of mutual information as a kind of deficiency of independence.

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