Abstract: A semi-measure is a generalization of a probability measure obtained by relaxing the additivity requirement to super-additivity. We introduce and study several randomness notions for left-c.e. semi-measures, a natural class of effectively approximable semi-measures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak 2-randomness to left-c.e. semi-measures is the most compelling, as it best reflects Martin-L"of randomness with respect to a computable measure. Additionally, we analyze a question of Shen, a positive answer to which would also have yielded a reasonable randomness notion for left-c.e. semi-measures. Unfortunately though, we find a negative answer, except for some special cases.
Recommendations
Cited in
(8)- Regularity, uniformity, and quasirandomness
- When does randomness come from randomness?
- The Kučera-Gács theorem revisited by Levin
- Random Measurable Selections
- Bridging computational notions of depth
- Degrees of randomized computability
- Randomness with respect to c.e. semimeasures
- On Empirical Meaning of Randomness with Respect to a Real Parameter
This page was built for publication: Randomness and semimeasures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2013389)
