Hierarchies of Randomness Tests
No Thumbnail Available
Date
2006-02-10T06:54:28Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
It is well known that Martin-Loef randomness can be characterized by a number of equivalent test concepts, based either on effective nullsets (Martin-Loef and Solovay tests) or on prefix-free Kolmogorov complexity (lower and upper entropy). These equivalences are not preserved as regards the partial randomness notions induced by effective Hausdorff measures or partial incompressibility. Tadaki as well as Calude, Staiger and Terwijn studied several concepts of partial randomness, but for some of them the exact relations remained unclear. In this paper we will show that they form a proper
hierarchy of randomness notions, namely for any rho where rho(x) is 2 to the power of -|x|s and s is a rational number satisfying 0<s<1, the Martin-Loef rho-tests are strictly weaker than Solovay rho-tests which in turn are strictly weaker than strong Martin-Loef rho-tests.
These results also hold for a more general class of rho introduced as unbounded premeasures.