1.1 Introduction

These notes concern algorithmic information theory (AIT) and its application to geometric measure theory (GMT). This is motivated by the mounting evidence that mathematics under algorithmic restrictions offers insights into–and refinements to–the study of the fractal properties of sets.

The origins of algorithmic information theory began in the 1960s with the formalization of Solomonoff induction: a rule for selecting an hypothesis for the source from which some given data was produced. The rule substitutes a non-computable, universal prior distribution into Bayes’ rule, and rewards algorithmically-simpler explanations Solomonoff, 1960. R. Solomonoff’s conception of information content is most closely related to the algorithmic probability of producing a piece of data with respect to a universal Turing machine.

An independent origin came just a few years later when A. Kolmogorov defined the algorithmic (plain) complexity of individual objects, thereby refining the concept of classical Shannon information which only describes the mean information content across a distribution Kolmogorov, 1968Kolmogorov, 1968. So, Kolmogorov’s concept of information content was based on the degree of incompressibility with respect to a universal Turing machine.

And shortly after, G. Chaitin also independently introduced plain complexity and established its symmetry of information property, as well as establishing some initial notions of algorithmic randomness for infinite binary strings based on attaining maximal complexity along their prefixes Chaitin, 1969.

P. Martin-Löf characterized algorithmic randomness for an infinite binary sequence instead as the inability to cover it to arbitrary precision by effectively open statistical tests Martin-Löf, 1966. This adjusted A. Church’s original attempt: computable randomness, meant to achieve the intuitive property due to von Mises that random sequences ought to pass all standard statistical tests such as the Law of Large Numbers.

C. Schnorr showed that both Chaitin’s and Martin-Löf’s notions of algorithmic randomness for infinite binary sequences were equivalent to yet another: those sequences on which any effective betting strategy (i.e., constructive martingale) would fail to generate arbitrary gains when betting on subsequent bits Schnorr, 1971. Thus, what is now commonly known as Martin-Löf randomness is considered robust for its equivalent characterizations in terms of Chaitin’s notion of incompressibility, Martin-Löf’s notion of typicality, and Schnorr’s notion of unpredictability.

Moreover, L. Levin confirmed the equivalence between Solomonoff, Kolmogorov, and Chaitin’s approaches to quantifying algorithmic information content Levin, 1973. Levin’s Coding Theorem equated Solomonoff’s universal prior with $2^{-K(\cdot)}$, where $K(\cdot)$ denotes prefix-free or self-delimiting Kolmogorov complexity, or the minimal description-length of some data with respect to a universal, prefix-free Turing machine.

Whether viewed as the branch of theoretical computer science dedicated to the properties of computably-generated objects, or as a refinement of classical Shannon information theory by measuring the information content of individual objects, or as a project to formalize randomness: algorithmic information theory clearly offers some extra structure to otherwise “classical” mathematics, or the mathematics unconstrained by effectivity.

Just as any natural, geometric object has an assignable geometric dimension that corresponds to the right “exponential factor” by which to measure its volume, the goal of many fractal dimension notions is to assign to a set an exponent appropriate to its geometry Downey et al., 2005. For instance, the Hausdorff dimension of a set is roughly defined as the critical value of $s$ for which the volume of the set as measured using exponent $s$ switches from being infinite to null. Thus, Hausdorff dimension is naturally associated to the family of $s$-dimensional Hausdorff outer measures $\mathcal{H}^s$ (defined in Section 1.3). These outer measures refine Lebesgue measure on null sets based on their covering properties. Yet, a further refinement to $\mathcal{H}^s$-nullness is exhibited by partial randomness.

Generalizing the constructive martingales of Schnorr, J. Lutz introduced constructive $s$-supergales, where $s \geq 0$ is a dimension parameter Lutz, 2000. Whenever a constructive $s$-supergale could make arbitrary gains betting on the subsequent bits of a given sequence (i.e., succeed on the sequence), then that sequence would not be considered random with respect to $s$. Then, Lutz defined the constructive dimension of a sequence to roughly be the minimal $s$ on which some constructive $s$-supergale could succeed.

Shortly after, E. Mayordomo elucidated the relationship between Lutz’s constructive dimension and Kolmogorov complexity. In particular, the constructive dimension of a sequence matches L. Staiger’s limit inferior of the normalized Kolmogorov complexities of the sequence’s prefixes Mayordomo, 2002Staiger, 1989.

Both Lutz’s and Mayordomo’s contributions were built on decades of prior work toward understanding Kolmogorov complexity, including bounds on plain complexity by Shannon entropy Staiger, 1981, as well as work by both B. Ryabko Ryabko, 1993Ryabko, 1994 and Staiger Staiger, 1998 partially relating the limit inferior of the normalized Kolmogorov complexity of prefixes to the speed at which a computable martingale could make arbitrary gains on a given sequence.

Generalizing the work of Schnorr and Chaitin, K. Tadaki introduced notions of Martin-Löf tests and partial randomness tailored to a dimension parameter $s \geq 0$ Tadaki, 2002, which in turn provided yet another characterization of constructive dimension as roughly the minimal value of $s$ for which a set could be covered by one of these tests. Thus, this effective notion of dimension serves as a refinement to Martin-Löf randomness, and similarly may be characterized in terms of incompressibility, typicality, and unpredictability.

In effect, effective dimension quantifies just how random a sequence behaves in the limit. In particular, it is possible for singleton sets to have nonzero effective dimension (in fact, most have full effective dimension). These would correspond to points which are not covered by a Martin-Löf-test appropriate for some dimension $s > 0$; or, equivalently, those admitting highly incompressible prefixes; or, those on which any constructive $s$-supergale would not succeed at making arbitrary gains for some $s > 0$.

In the recent past, computability theorists and geometric measure theorists alike have used some notions of effective dimension to prove classical results about the fractal dimension of certain sets. The so-called Point-to-Set Principles by J. Lutz and N. Lutz have almost always served as the bridge between effective and “classical” results about Hausdorff or packing dimensions in Euclidean space Lutz & Lutz, 2018. For example, their formula in Theorem 1.12.1 characterizes the Hausdorff dimension of a set in a pointwise manner: a strange result given that all singleton sets are classically zero-dimensional. But, as we have discussed, most points are not forthright in revealing their own smallness by effective means. Essentially, sets of large fractal dimension must contain many sufficiently random points.

There are still many open questions in regards to the potential applications of algorithmic information theory to geometric measure theory, as well as to what settings AIT applies.

Note that this introduction as well as most of the contents feeding these notes were originally produced in my doctoral dissertation from 2025.

• Chapter 1: We fix some notation and review the basic definitions and results relevant to our discussion about AIT and GMT. Central to our work are the outer measures induced by premeasures on a space, various cover and test notions from algorithmic randomness, and measures of algorithmic information content such as Kolmogorov complexity and semimeasures. In particular, Theorem 1.8.3 relates three notions from the partial randomness literature: success by a lower-semicomputable continuous semimeasure, success by a constructive supergale, and covering by a sequence of strong Solovay tests with rapidly shrinking weights.

• Chapter 2: We establish some basic properties of the lift of Kolmogorov complexity to Euclidean space. Theorem 2.1.1 shows that the order of optimizers in the definition of conditional prefix complexity makes no difference up to sub-linear factors. Theorem 2.1.11 proves a conditional symmetry of information for conditional prefix complexity. Lemma 2.2.2 confirms a modulus processing inequality for conditional prefix complexity under computable, uniformly continuous maps, which implies conditional dimension is invariant under bi-computable, bi-Lipschitz continuous maps in Theorem 2.2.4.