TY - GEN
T1 - Relative randomness for Martin-Löf random sets
AU - Peng, Ning Ning
AU - Higuchi, Kojiro
AU - Yamazaki, Takeshi
AU - Tanaka, Kazuyuki
PY - 2012
Y1 - 2012
N2 - Let Γ be a set of functions on the natural numbers. We introduce a new randomness notion called semi Γ-randomness, which is associated with a Γ-indexed test. Fix a computable sequence {G n} nεω of all c.e. open sets. For any f ε Γ, {G f(n)} nεω is called a Γ-indexed test if μ(G f(n)) ≤ 2 -n for all n. We prove that weak n-randomness is strictly stronger than semi Δ n 0-randomness, for n > 2. Moreover, we investigate the relationships between various definitions of randomness.
AB - Let Γ be a set of functions on the natural numbers. We introduce a new randomness notion called semi Γ-randomness, which is associated with a Γ-indexed test. Fix a computable sequence {G n} nεω of all c.e. open sets. For any f ε Γ, {G f(n)} nεω is called a Γ-indexed test if μ(G f(n)) ≤ 2 -n for all n. We prove that weak n-randomness is strictly stronger than semi Δ n 0-randomness, for n > 2. Moreover, we investigate the relationships between various definitions of randomness.
UR - http://www.scopus.com/inward/record.url?scp=84862157760&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862157760&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-30870-3_58
DO - 10.1007/978-3-642-30870-3_58
M3 - Conference contribution
AN - SCOPUS:84862157760
SN - 9783642308697
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 581
EP - 588
BT - How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings
T2 - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012
Y2 - 18 June 2012 through 23 June 2012
ER -