The Quasi-equivalence between the Definitions of Partial Randomness
Chenguang Liu, Kazuyuki Tanaka, Takeshi Yamazaki · 2008
In the recent literature, many definitions of partial randomness of reals have been proposed and studied rather discretely. For instance, it is known that for a computable real epsi isin (0,1), strong Martin-Lof epsi-randomness is strictly stronger than Solovay epsi-randomness which is strictly stronger than weak Martin-Lof epsi-randomness. In the present work, we firstly give several new definitions of partial randomness - strong Kolmogorov epsi-randomness and weak/strong DH-Chaitin epsi-randomness. Then, we investigate the relation between epsi-randomness by one definition and epsi'-randomness by another. Finally, we show that all of the known definitions of epsi-randomness are quasi-equivalent.