Abstract
A semimeasure is a generalization of a probability measure obtained by relaxing the additivity requirement to superadditivity. We introduce and study several randomness notions for left-c.e. semimeasures, a natural class of effectively approximable semimeasures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak -randomness to left-c.e. semimeasures is the most compelling, as it best reflects Martin-Löf 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. semimeasures. Unfortunately, though, we find a negative answer, except for some special cases.
Laurent Bienvenu. Rupert Hölzl. Christopher P. Porter. Paul Shafer. "Randomness and Semimeasures." Notre Dame J. Formal Logic 58 (3) 301 - 328, 2017. https://doi.org/10.1215/00294527-3839446
Information