TY - JOUR
T1 - Propagation of partial randomness
AU - Higuchi, Kojiro
AU - Hudelson, W. M.Phillip
AU - Simpson, Stephen G.
AU - Yokoyama, Keita
PY - 2014/2
Y1 - 2014/2
N2 - Let f be a computable function from finite sequences of 0's and 1's to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.
AB - Let f be a computable function from finite sequences of 0's and 1's to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.
KW - Effective Hausdorff dimension
KW - Kolmogorov complexity
KW - Martin-Löf randomness
KW - Models of arithmetic
KW - Partial randomness
UR - http://www.scopus.com/inward/record.url?scp=84887997422&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84887997422&partnerID=8YFLogxK
U2 - 10.1016/j.apal.2013.10.006
DO - 10.1016/j.apal.2013.10.006
M3 - Article
AN - SCOPUS:84887997422
SN - 0168-0072
VL - 165
SP - 742
EP - 758
JO - Annals of Pure and Applied Logic
JF - Annals of Pure and Applied Logic
IS - 2
ER -