Algorithmic tests and randomness with respect to a class of measures

Details Algorithmic tests and randomness with respect to a class of measures Algorithmic tests and randomness with respect to a class of measures

2011-03-08

arxiv.org/abs/1103.1529v2

Mathematics

Logic

Scientific paper

The paper considers quantitative versions of different randomness notions: algorithmic test measures the amount of non-randomness (and is infinite for non-random sequences). We start with computable measures on Cantor space (and Martin-Lof randomness), then consider uniform randomness (test is a function of a sequence and a measure, not necessarily computable) and arbitrary constructive metric spaces. We also consider tests for classes of measures, in particular Bernoulli measures on Cantor space, and show how they are related to uniform tests and original Martin-Lof definition. We show that Hyppocratic (blind, oracle-free) randomness is equivalent to uniform randomness for measures in an effectively orthogonal effectively compact class. We also consider the notions of sparse set and on-line randomness and show how they can be expressed in our framework.

Affiliated with

Also associated with

No associations

Rating

Algorithmic tests and randomness with respect to a class of measures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithmic tests and randomness with respect to a class of measures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic tests and randomness with respect to a class of measures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-82651