Bounded Turing reductions and data processing inequalities for sequences (Q1787951): Difference between revisions

Define \(\operatorname{mdim}(Z:Y)=\underline{\lim}_n\frac{I(Z\upharpoonright n:Y\upharpoonright n)}{n\log|\Sigma|}\) and \(\operatorname{Mdim}(Z:Y)=\overline{\lim}_n\frac{I(Z\upharpoonright n:Y\upharpoonright n)}{n\log|\Sigma|}\), where \(\Sigma\) is a finite list, both \(Z,Y\in \Sigma^{\infty}\) and \(I\) is the algorithmic mutual information. The major result in the paper is that if \(Z\) is computable Lipschitz reductible to \(X\) then, for any \(Y\), \(\operatorname{mdim}(Z:Y)\leq \operatorname{mdim}(X:Y)\) and \(\operatorname{Mdim}(Z:Y)\leq \operatorname{Mdim}(X:Y)\).