News
26 Nov 2025: page created
23 Nov 2025: Accepted
20 July 2025: First submission
Title
Randomness with respect to c.e. semimeasures
Type
Research article
Publication
Information and Computation
Special Issue in Memory of Vladimir V’yugin
https://doi.org/10.1016/j.ic.2025.105384
Abstract
We study algorithmic randomness with respect to c.e. semimeasures, which naturally arise as pushforward measures of partial computable mappings and therefore play a crucial role in algorithmic randomness.
We consider four distinct randomness notions: three based on complexity and one based on tests.
We systematically clarify their inclusion relationships.
Our main contribution is to construct concrete examples that separate these notions.
Furthermore, we investigate how they interact with the classical randomness preservation and no-randomness-from-nothing theorems, identifying precise conditions under which they continue to hold.
download
semimeasure-elsarticle-20251126