Propagation of partial randomness (Q386647)

Several groups of researchers have independently found two results about algorithmic randomness which have since been widely known and used: NEWLINE{\parindent=6mm NEWLINE\begin{itemize} \item[(1)] If \(X\) is ML-random, \(Y\) is \(Z\)-ML-random and \(Y\) computes \(X\), then \(X\) is \(Z\)-ML-random; NEWLINE\item [(2)] If \(X\) is ML-random then \(X\) is random relative to some PA degree.NEWLINENEWLINE\end{itemize}} NEWLINEIn 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: NEWLINE{\parindent=6mm NEWLINE\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\); NEWLINE\item [(b)] If \(Y\) is \(Z\)-ML-random, \(Y\) computes \(X\) and \(X\) is DNR, then \(X\) is DNR\({}^Z\).NEWLINENEWLINE\end{itemize}}