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 -