TY - GEN
T1 - The quasi-equivalence between the definitions of partial randomness
AU - Liu, Chen Guang
AU - Tanaka, Kazuyuki
AU - Yamazaki, Takeshi
PY - 2008
Y1 - 2008
N2 - 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 ε ∈(0, 1), strong Martin-Löf ε-randomness is strictly stronger than Solovay ε-randomness which is strictly stronger than weak Martin-Löf ε-randomness. In the present work, we firstly give several new definitions of partial randomness - strong Kolmogorov ε-randomness and weak/strong DH-Chaitin ε-randomness. Then, we investigate the relation between ε-randomness by one definition and ε′-randomness by another. Finally, we show that all of the known definitions of ε-randomness are quasi-equivalent.
AB - 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 ε ∈(0, 1), strong Martin-Löf ε-randomness is strictly stronger than Solovay ε-randomness which is strictly stronger than weak Martin-Löf ε-randomness. In the present work, we firstly give several new definitions of partial randomness - strong Kolmogorov ε-randomness and weak/strong DH-Chaitin ε-randomness. Then, we investigate the relation between ε-randomness by one definition and ε′-randomness by another. Finally, we show that all of the known definitions of ε-randomness are quasi-equivalent.
UR - http://www.scopus.com/inward/record.url?scp=57649229634&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57649229634&partnerID=8YFLogxK
U2 - 10.1109/ICNC.2008.916
DO - 10.1109/ICNC.2008.916
M3 - Conference contribution
AN - SCOPUS:57649229634
SN - 9780769533049
T3 - Proceedings - 4th International Conference on Natural Computation, ICNC 2008
SP - 371
EP - 375
BT - Proceedings - 4th International Conference on Natural Computation, ICNC 2008
T2 - 4th International Conference on Natural Computation, ICNC 2008
Y2 - 18 October 2008 through 20 October 2008
ER -