Mutual dimension

DOI10.1145/2786566MaRDI QIDQ2832303zbMATH OpenOpenAlexFDO

Authors Adam Case, Jack H. Lutz

Publication date 10 November 2016

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4135

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the data processing inequality for mutual dimension, says that, if $f:mathbb{R}^{m}ightarrowmathbb{R}^n$ is computable and Lipschitz, then the inequalities $mdim(f(x):y)leqmdim(x:y)$ and $Mdim(f(x):y)leqMdim(x:y)$ hold for all $xinmathbb{R}^m$ and $yinmathbb{R}^t$. We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.

Recommendations

• scientific article; zbMATH DE number 6678913
• Bounded Turing reductions and data processing inequalities for sequences
• Conditional dimension in metric spaces: a natural metric-space counterpart of Kolmogorov-complexity-based mutual dimension

Cites work

• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 1994007 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• An introduction to Kolmogorov complexity and its applications
• Computing over the reals: foundations for scientific computing.
• Computing space-filling curves
• Connectedness properties of dimension level sets
• Connectivity properties of dimension level sets
• Correspondence principles for effective dimensions
• Curves that must be retraced
• Curves that must be retraced
• Dimensions of Points in Self-Similar Fractals
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Effective dimension of points visited by Brownian motion
• Elements of Information Theory
• Inequalities for Shannon entropy and Kolmogorov complexity
• Logical operations and Kolmogorov complexity
• Mutual Information and Maximal Correlation as Measures of Dependence
• On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
• Points on Computable Curves of Computable Lengths
• The dimensions of individual strings and sequences
• Translating the Cantor set by a random real

Cited in

(10)

• Bounds on the dimension of lineal extensions
• Results on the dimension spectra of planar lines
• Bounded Turing reductions and data processing inequalities for sequences
• Dimension spectra of lines
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• On the packing dimension of unions and extensions of k-planes
• Fractal Intersections and Products via Algorithmic Dimension
• Algorithmically optimal outer measures
• scientific article; zbMATH DE number 6678913 (Why is no real title available?)
• Projection theorems using effective dimension

This page was built for publication: Mutual dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2832303)