Randomness and semimeasures
From MaRDI portal
Publication:2013389
DOI10.1215/00294527-3839446zbMATH Open1417.03242arXiv1310.5133OpenAlexW3103075045WikidataQ60500749 ScholiaQ60500749MaRDI QIDQ2013389
Christopher P. Porter, Paul Shafer, Laurent Bienvenu, Rupert Hölzl
Publication date: 17 August 2017
Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1310.5133
Related Items (6)
When does randomness come from randomness? ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ On Empirical Meaning of Randomness with Respect to a Real Parameter ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Regularity, uniformity, and quasirandomness ⋮ Random Measurable Selections
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)
