Document Type

Article

Publication Date

5-7-2025

Published In

ACM Transactions On Computation Theory

Abstract

We investigate the relationship between algorithmic fractal dimensions and the classical local fractal dimensions of outer measures in Euclidean spaces. We introduce global and local optimality conditions for lower semicomputable outer measures. We prove that globally optimal outer measures exist. Our main theorem states that the classical local fractal dimensions of any locally optimal outer measure coincide exactly with the algorithmic fractal dimensions. Our proof uses an especially convenient locally optimal outer measure κ defined in terms of Kolmogorov complexity. We discuss implications for point-to-set principles.

Keywords

algorithmic dimension, outer measures, Kolmogorov complexity

Comments

This work is freely available under a Creative Commons license.

Download

Share

COinS