Title :
The Quasi-equivalence between the Definitions of Partial Randomness
Author :
Liu, ChenGuang ; Tanaka, Kazuyuki ; Yamazaki, Takeshi
Author_Institution :
Grad. Sch. of Manage. Sci., Xi´´an Univ. of Technol., Xi´´an
Abstract :
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.
Keywords :
random processes; set theory; DH-Chaitin randomness; Kolmogorov randomness; Martin randomness; Solovay randomness; partial randomness definition; Binary sequences; Books; Conference management; Technology management; Algorithmic randomness; Partial randomness; Quasi-equivalence;
Conference_Titel :
Natural Computation, 2008. ICNC '08. Fourth International Conference on
Conference_Location :
Jinan
Print_ISBN :
978-0-7695-3304-9
DOI :
10.1109/ICNC.2008.916