Randomness and semimeasures

DOI10.1215/00294527-3839446zbMATH Open1417.03242arXiv1310.5133OpenAlexW3103075045WikidataQ60500749 ScholiaQ60500749MaRDI QIDQ2013389FDOQ2013389

Rupert Hölzl, Christopher P. Porter, Paul Shafer, Laurent Bienvenu

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

Recommendations

• Randomness and initial segment complexity for measures
• On semimeasures predicting Martin-Löf random sequences
• scientific article
• Randomness -- beyond Lebesgue measure
• Algorithmic Learning Theory

zbMATH Keywords

measuresalgorithmic randomnessrandomnesssemimeasures

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

Cited In (6)

• Regularity, uniformity, and quasirandomness
• DEGREES OF RANDOMIZED COMPUTABILITY
• When does randomness come from randomness?
• The Kučera-Gács theorem revisited by Levin
• Random Measurable Selections
• 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)