Propagation of partial randomness (Q386647): Difference between revisions

Several groups of researchers have independently found two results about algorithmic randomness which have since been widely known and used: {\parindent=6mm \begin{itemize} \item[(1)] If \(X\) is ML-random, \(Y\) is \(Z\)-ML-random and \(Y\) computes \(X\), then \(X\) is \(Z\)-ML-random; \item [(2)] If \(X\) is ML-random then \(X\) is random relative to some PA degree. \end{itemize}} In this paper, the authors show that similar results hold for the notion of strong \(f\)-randomness, where \(f\) is a computable function which associates weights to finite binary strings. An important example is the weight \(f(\sigma) = 2^{-s|\sigma|}\) for some \(s\in (0,1)\), which is used in the definition of effective Hausdorff dimension. The authors also relate strong \(f\)-randomness to autocomplexity, and prove some propagation results for non-\(K\)-triviality and for DNR: {\parindent=6mm \begin{itemize} \item[(a)] if \(Y\) is \(Z\)-ML-random, \(Y\) computes \(X\) and \(X\) is not \(K\)-trivial, then \(X\) is not ML-below \(Z\); \item [(b)] If \(Y\) is \(Z\)-ML-random, \(Y\) computes \(X\) and \(X\) is DNR, then \(X\) is DNR\({}^Z\). \end{itemize}}