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 Randomized Algorithms''
   The Constructive in Logic and Applications
   CUNY Graduate Center, New York
   May 24, 2012

  Download slides: PDF.

Back to Sam Buss's publications page.