Article ID Journal Published Year Pages File Type
422174 Electronic Notes in Theoretical Computer Science 2008 15 Pages PDF
Abstract

In the context of Kolmogorov's algorithmic approach to the foundations of probability, Martin-Löf defined the concept of an individual random sequence using the concept of a constructive measure 1 set. Alternate characterizations use constructive martingales and measures of impossibility. We prove a direct conversion of a constructive martingale into a measure of impossibility and vice versa, such that their success sets, for a suitably defined class of computable probability measures, are equal. The direct conversion is then generalized to give a new characterization of constructive dimensions, in particular, the constructive Hausdorff dimension and the constructive packing dimension.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics