Информационная система "Конференции"

Abstracts

Computability theory

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 [2002] and Calude, Staiger and Terwijn [2004] 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 measure function r with r(x) being the power of 2 raised to -|x|*s where s is a rational number properly between 0 and 1. In particular, the Martin-Loef r-tests are strictly weaker than Solovay r-tests which in turn are strictly weaker than strong Martin-Loef r-tests. These results also hold for a natural class of similar measure functions.

Mail to Webmaster alc9@math.nsc.ru

|Home Page| |English Part|

Go to Home