Samuel R. Buss and Mia Minnes
"Probabilistic Algorithmic Randomness"
Journal of Symbolic Logic 78, 2 (2013) 579-601.
Download manuscript: PDF.
Abstract: We introduce probabilistic martingales, in which randomness is used to decide whether to bet. We show that different versions of computable probabilistic martingales can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.
Slides from related talk:
``Algorithmic Complexity via
The Constructive in Logic and Applications
CUNY Graduate Center, New York
May 24, 2012
Download slides: PDF.
Back to Sam Buss's publications page.