Our aim is to quantify how complex a Cantor set is as we approximate it better and better. We formalize this by asking what is the shortest program, running on a universal Turing machine, which produces this set at the precision $\epsilon$ in the sense of Hausdorff distance. This is the Kolmogorov complexity of the approximated Cantor set, which we call the "$\epsilon$-distortion complexity". How does this quantity behave as $\epsilon$ tends to 0? And, moreover, how this behaviour relates to other characteristics of the Cantor set? This is the subject of this work: we estimate this quantity for several types of Cantor sets on the line generated by iterated function systems and exhibit very different behaviours. For instance, the $\epsilon$-distortion complexity of most $C^k$ Cantor sets is proven to behave as $\epsilon^{-D/k}$, where D is its box counting dimension.
Estimates of Kolmogorov complexity in approximating Cantor sets
BONANNO, CLAUDIO;
2011-01-01
Abstract
Our aim is to quantify how complex a Cantor set is as we approximate it better and better. We formalize this by asking what is the shortest program, running on a universal Turing machine, which produces this set at the precision $\epsilon$ in the sense of Hausdorff distance. This is the Kolmogorov complexity of the approximated Cantor set, which we call the "$\epsilon$-distortion complexity". How does this quantity behave as $\epsilon$ tends to 0? And, moreover, how this behaviour relates to other characteristics of the Cantor set? This is the subject of this work: we estimate this quantity for several types of Cantor sets on the line generated by iterated function systems and exhibit very different behaviours. For instance, the $\epsilon$-distortion complexity of most $C^k$ Cantor sets is proven to behave as $\epsilon^{-D/k}$, where D is its box counting dimension.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
