{'fraction_non_alphanumeric': 0.04704248819772285, 'fraction_numerical': 0.013810978431917061, 'mean_word_length': 4.187361951406896, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithmic Fractal Dimensions in Geometric Measure Theory

The development of algorithmic fractal dimensions in this century has had many fruitful interactions with geometric measure theory, especially fractal geometry in Euclidean spaces. We survey these developments, with emphasis on connections with computable functions on the reals, recent uses of algorithmic dimensions in proving new theorems in classical (non-algorithmic) fractal geometry, and directions for future research.


Introduction
In early 2000, classical Hausdorff dimension [32] was shown to admit a new characterization in terms of betting strategies called martingales [51]. This characterization enabled the development of various effective, i.e., algorithmic, versions of Hausdorff dimension obtained by imposing computability and complexity constraints on these martingales. These algorithmic versions included resource-bounded dimensions, which impose dimension structure on various complexity classes [52], the (constructive) dimensions of infinite binary sequences, which interact usefully with algorithmic information theory [53], and the finite-state dimensions of infinite binary sequences, which interact usefully with data compression and Borel normality [19]. Soon thereafter, classical packing dimension [96,94] was shown to admit a new characterization in terms of martingales that is exactly dual to the martingale characterization of Hausdorff dimension [1]. This led immediately to the development of strong resource-bounded dimensions, strong (constructive) dimension, and  [1], which are all algorithmic versions of packing dimension. In the years since these developments, hundreds of research papers by many authors have deepened our understanding of these algorithmic dimensions.
Most work to date on effective dimensions has been carried out in the Cantor space, which consists of all infinite binary sequences. This is natural, because effective dimensions speak to many issues that were already being investigated in the Cantor space. However, the classical fractal dimensions from which these effective dimensions arose-Hausdorff dimension and packing dimension-are powerful quantitative tools of geometric measure theory that have been most useful in Euclidean spaces and other metric spaces that have far richer structures than the totally disconnected Cantor space.
This chapter surveys research results to date on algorithmic fractal dimensions in geometric measure theory, especially fractal geometry in Euclidean spaces. This is a small fraction of the existing body of work on algorithmic fractal dimensions, but it is substantial, and it includes some exciting new results.
It is natural to identify a real number with its binary expansion and to use this identification to define algorithmic dimensions in Euclidean spaces in terms of their counterparts in Cantor space. This approach works for some purposes, but it becomes a dead end when algorithmic dimensions are used in geometric measure theory and computable analysis. The difficulty, first noted by Turing in his famous correction [98], is that many obviously computable functions on the reals (e.g., addition) are not computable if reals are represented by their binary expansions [100]. We thus take a principled approach from the beginning, developing algorithmic dimensions in Euclidean spaces in terms of the quantity K r (x) in the following paragraph, so that the theory can seamlessly advance to sophisticated applications.
Algorithmic dimension and strong algorithmic dimension are the most extensively investigated effective dimensions. One major reason for this is that these algorithmic dimensions were shown by the second author and others [68,1,57] to have characterizations in terms of Kolmogorov complexity, the central notion of algorithmic information theory. In Section 2 below we give a brief introduction to the Kolmogorov complexity K r (x) of a point x in Euclidean space at a given precision r.
In Section 3 we use the above Kolmorogov complexity notion to develop the algorithmic dimension dim(x) and the strong algorithmic dimension Dim(x) of each point x in Euclidean space. This development supports the useful intuition that these dimensions are asymptotic measures of the density of algorithmic information in the point x. We discuss how these dimensions relate to the local dimensions that arise in the so-called thermodynamic formalism of fractal geometry; we discuss the history and terminology of algorithmic dimensions; we review the prima facie case that algorithmic dimensions are geometrically meaningful; and we discuss what is known about the circumstances in which algorithmic dimensions agree with their classical counterparts. We then discuss the authors' use of algorithmic dimensions to analyze self-similar fractals [57]. This analysis gives us a new, information-theoretic proof of the classical formula of Moran [73] for the Hausdorff dimensions of selfsimilar fractals in terms of the contraction ratios of the iterated function systems that generate them. This new proof gives a clear account of "where the dimension comes from" in the construction of such fractals. Section 3 concludes with a survey of the dimensions of points on lines in Euclidean spaces, a topic that has been surprisingly challenging until a very recent breakthrough by N. Lutz and Stull [63].
We survey interactive aspects of algorithmic fractal dimensions in Euclidean spaces in Section 4, starting with the mutual algorithmic dimensions developed by Case and the first author [13]. These dimensions, mdim(x : y) and Mdim(x : y), are analogous to the mutual information measures of Shannon information theory and algorithmic information theory. Intuitively, mdim(x : y) and Mdim(x : y) are asymptotic measures of the density of the algorithmic information shared by points x and y in Euclidean spaces. We survey the fundamental properties of these mutual dimensions, which are analogous to those of their information-theoretic analogs. The most important of these properties are those that govern how mutual dimensions are affected by functions on Euclidean spaces that are computable in the sense of computable analysis [100]. Specifically, we review the information processing inequalities of [13], which state that mdim( f (x) : y) ≤ mdim(x : y) and Mdim( f (x) : y) ≤ Mdim(x : y) hold for all computable Lipschitz functions f , i.e., that applying such a function f to a point x cannot increase the density of algorithmic information that it contains about a point y. We also survey the conditional dimensions dim(x|y) and Dim(x|y) recently developed by the first author and N. Lutz [56]. Roughly speaking, these conditional dimensions quantify the density of algorithmic information in x beyond what is already present in y.
It is rare for the theory of computing to be used to answer open questions in mathematical analysis whose statements do not involve computation or related aspects of logic. In Section 5 we survey exciting new developments that do exactly this. We first describe new characterizations by the first author and N. Lutz [56] of the classical Hausdorff and packing dimensions of arbitrary sets in Euclidean spaces in terms of the relativized dimensions of the individual points that belong to them. These characterizations are called point-to-set principles because they enable one to use a bound on the relativized dimension of a single, judiciously chosen point x in a set E in Euclidean space to prove a bound on the classical Hausdorff or packing dimension of the set E. We illustrate the power of the point-to-set principle by giving an overview of its use in the new, information-theoretic proof [56] of Davies's 1971 theorem stating that the Kakeya conjecture holds in the Euclidean plane [20]. We then discuss two very recent uses of the point-to-set principle to solve open problems in classical fractal geometry. These are N. Lutz and D. Stull's strengthened lower bounds on the Hausdorff dimensions of generalized Furstenberg sets [63] and N. Lutz's extension of the fractal intersection formulas for Hausdorff and packing dimensions in Euclidean spaces from Borel sets to arbitrary sets. These are, to the best of our knowledge, the first uses of algorithmic information theory to solve open problems in classical mathematical analysis.
We briefly survey promising directions for future research in Section 6. These include extending the algorithmic analysis of self-similar fractals [57] to other classes of fractals, extending algorithmic dimensions to metric spaces other than Euclidean spaces, investigating algorithmic fractal dimensions that are more effective than constructive dimensions (e.g., polynomial-time or finite-state fractal dimensions) in fractal geometry, and extending algorithmic methods to rectifiability and other aspects of geometric measure theory that do not necessarily concern fractal geometry. In each of these we begin by describing an existing result that sheds light on the promise of further inquiry.
Overviews of algorithmic dimensions in Cantor space appear in [23,69], though these are already out of date. Even prior to the development of algorithmic fractal dimensions, a rich network of relationships among gambling strategies, Hausdorff dimension, and Kolmogorov complexity was uncovered by reserach of Ryabko [79,80,81,82], Staiger [89,90,91], and Cai and Hartmanis [11]. A brief account of this "prehistory" of algorithmic fractal dimensions appears in section 6 of [53].

Algorithmic Information in Euclidean Spaces
Algorithmic information theory has most often been used in the set {0, 1} * of all finite binary strings. The conditional Kolmogorov complexity (or conditional algorithmic information content) of a string x ∈ {0, 1} * given a string y ∈ {0, 1} * is Here U is a fixed universal Turing machine, and |π| is the length of a binary " program" π. Hence K(x|y) is the minimum number of bits required to specify x to U, when y is provided as side information. We refer the reader to any of the standard texts [49,23,75,87] for the history and intuition behind this notion, including its essential invariance with respect to the choice of the universal Turing machine U. The Kolmogorov complexity (or algorithmic information content) of a string x ∈ {0, 1} * is then where λ is the empty string. Routine binary encoding enables one to extend the definitions of K(x) and K(x|y) to situations where x and y range over other countable sets such as N, Q, N × Q, etc.
The key to "lifting" algorithmic information theory notions to Euclidean spaces is to define the Kolmogorov complexity of a set E ⊆ R n to be (Shen and Vereshchagin [88] used a very similar notion for a very different purpose.) Note that K(E) is the amount of information required to specify not the set E itself, but rather some rational point in E. In particular, this implies that Note also that, if E contains no rational point, then K(E) = ∞.
The Kolmogorov complexity of a point x ∈ R n at precision r ∈ N is where B ε (x) is the open ball of radius ε about x, i.e., the number of bits required to specify some rational point q ∈ Q n satisfying |q − x| < 2 −r , where |q − x| is the Euclidean distance of q − x from the origin.

Dimensions of Points
We now define the (constructive) dimension of a point x ∈ R n to be and the strong (constructive) dimension of x to be We note that dim(x) and Dim(x) were originally defined in terms of algorithmic betting strategies called gales [53,1]. The identities (1) and (2) were subsequent theorems proven in [57], refining very similar results in [68,1]. These identities have been so convenient for work in Euclidean space that it is now natural to regard them as definitions.
Since K r (x) is the amount of information required to specify a rational point that approximates x to within 2 −r (i.e., with r bits of precision), dim(x) and Dim(x) are intuitively the lower and upper asymptotic densities of information in the point x. This intuition is a good starting point, but the fact that dim(x) and Dim(x) are geometrically meaningful will only become evident in light of the mathematical consequences of (1) and (2) surveyed in this chapter.
It is an easy exercise to show that, for all x ∈ R n , If x is a computable point in R n , then K r (x) = o(r), so dim(x) = Dim(x) = 0. On the other hand, if x is a random point in R n (i.e., a point that is algorithmically random in the sense of Martin-Löf [65] Hence the dimensions of points range between 0 and the dimension of the Euclidean space that they inhabit. In fact, for every real number α ∈ [0, n], the dimension level and the strong dimension level set are uncountable and dense in R n [53,1]. The dimensions dim(x) and Dim(x) can coincide, but they do not generally do so. In fact, the set DIM 0 ∩ DIM n str is a comeager (i.e., topologically large) subset of R n [37].
Classical fractal geometry has local, or pointwise, dimensions that are useful, especially in connection with dynamical systems. Specifically, if ν is an outer measure on R n , i.e., a function ν : , and if ν is locally finite (i.e., every x ∈ R n has a neighborhood N with ν(N) < ∞), then the lower and upper local dimensions of ν at a point x ∈ R n are and respectively, where log = log 2 [25]. Until very recently, no relationship was known between the dimensions dim(x) and Dim(x) and the local dimensions (6) and (7). However, N. Lutz recently observed that a very non-classical choice of the outer measure ν remedies this. For where K(E) is defined as in (1). Then κ is easily seen to be an outer measure on R n that is finite (i.e., κ(R n ) < ∞), hence certainly locally finite, whence the local dimensions dim loc κ and Dim loc κ are well defined. In fact we have the following. and There is a direct conceptual path from the classical Hausdorff and packing dimensions to the dimensions of points defined in (1) and (2). The Hausdorff dimension dim H (E) of a set E ⊆ R n was introduced by Hausdorff [32] before 1920 and is arguably the most important notion of fractal dimension. Its classical definition, which may be found in standard texts such as [93,25,7], involves covering the set E by families of sets with diameters vanishing in the limit. In all cases, 0 ≤ dim H (E) ≤ n.
At the beginning of the present century, in order to formulate versions of Hausdorff dimensions that would work in complexity classes and other algorithmic set-tings, the first author [52] gave a new characterization of Hausdorff dimension in terms of betting strategies, called gales, on which it is easy to impose computability and complexity conditions. Of particular interest here, he then defined the constructive dimension cdim(E) of a set E ⊆ R n exactly like the gale characterization of dim H (E), except that the gales were now required to be lower semicomputable [53]. He then defined the dimension dim(x) of a point x ∈ R n to be the constructive dimension of its singleton, i.e., dim(x) = cdim({x}). The existence of a universal Turing machine made it immediately evident that constructive dimension has the absolute stability property that for all x ∈ R n . Accordingly, constructive dimension has since been investigated pointwise. As noted earlier, the second author [68] then proved the characterization (1) as a theorem. Two things should be noted about the preceding paragraph. First, these early papers were written entirely in terms of binary sequences, rather than points in Euclidean space. However, the most straightforward binary encoding of points bridges this gap. (In this survey we freely use those results from Cantor space that do extend easily to Euclidean space.) Second, although the gale characterization is essential for polynomial time and many other stringent levels of effectivization, constructive dimension can be defined equivalently by effectivizing Hausdorff's original formulation [77].

The Correspondence Principle
In 2001, the first author conjectured that there should be a correspondence principle (a term that Bohr had used analogously in quantum mechanics) assuring us that for sufficiently simple sets E ⊆ R n , the constructive and classical dimensions agree, i.e., Hitchcock [34] confirmed this conjecture, proving that (10) holds for any set E ⊆ R n that is a union of sets that are computably closed, i.e., that are Π 0 1 in Kleene's arithmetical hierarchy. (This means that (10) holds for all Σ 0 2 sets, and also for sets that are nonuniform unions of Π 0 1 sets.) Hitchcock also noted that this result is the best possible in the arithmetical hierarchy, because there are Π 0 2 sets E (e.g., E = {z}, where z is a Martin-Löf random point that is ∆ 0 2 ) for which (10) fails. By (9) and (10) we have which is a very nonclassical, pointwise characterization of the classical Hausdorff dimensions of sets that are unions of Π 0 1 sets. Since most textbook examples of fractal sets are Π 0 1 , (11) is a strong preliminary indication that the dimensions of points are geometrically meaningful.
The packing dimension dim P (E) of a set E ⊆ R n was introduced in the early 1980s by Tricot [96] and Sullivan [94]. Its original definition is a bit more involved that that of Hausdorff dimension [25,7] and implies that dim After the development of constructive versions of Hausdorff dimension outlined above, Athreya, Hitchcock, and the authors [1] undertook an analogous development for packing dimension. The gale characterization of dim P (E) turns out to be exactly dual to that of dim H (E), with just one limit superior replaced by a limit inferior. The strong constructive dimension cDim(E) of a set E ⊆ R n is defined by requiring the gales to be lower semicomputable, and the strong dimension of a point x ∈ R n is Dim(x) = cDim({x}). The absolute stability of strong constructive dimension, holds for all E ⊆ R n , as does the Kolmogorov complexity characterization (2). All this was shown in [1], but a correspondence principle for strong constructive dimension was left open. In fact, Conidis [16] subsequently used a clever priority argument to construct a Π 0 1 set E ⊆ R n for which cDim(E) = dim P (E). It is still not known whether some simple, logical definability criterion for E implies that cDim(E) = dim P (E). Staiger's proof that regular ω-languages E satisfy this identity is an encouraging step in this direction [92].

Self-Similar Fractals
The first application of algorithmic dimensions to fractal geometry was the authors' investigation of the dimensions of points in self-similar fractals [57]. We give a brief exposition of this work here, referring the reader to [57] for the many missing details.
Self-similar fractals are the most widely known and best understood classes of fractals [25]. Cantor's middle-third set, the von Koch curve, the Sierpinski triangle, and the Menger sponge are especially well known examples of self-similar fractals.
Briefly, a self-similar fractal in a Euclidean space R n is generated from an initial nonempty closed set D ⊆ R n by an iterated function system (IFS), which is a finite list S = (S 0 , S 1 , . . . , S k−1 ) of k ≥ 2 contracting similarities S i : D → D. Each of these similarities S i is coded by the symbol i in the alphabet Σ = {0, . . . , k − 1}, and each S i has a contraction ratio c i ∈ (0, 1). The IFS S is required to satisfy Moran's open set condition [73], which says that there is a nonempty open set G ⊆ D whose images S i (G), for i ∈ Σ , are disjoint subsets of G.
For example, the Sierpinski triangle is generated from the set D ⊆ R 2 consisting of the triangle with vertices v 0 = (0, 0), v 1 = (1, 0), and v 2 = (1/2, √ 3/2), together with this triangle's interior, by the IFS S = (S 0 , for p ∈ D. Note that Σ = {0, 1, 2} and c 0 = c 1 = c 2 = 1/2 in this example. Note also that the open set condition is satisfied here by letting G be the topological interior of D. Each infinite sequence T ∈ Σ ∞ codes a point S(T ) ∈ D that is obtained by applying the similarities coded by the successive symbols in T in a canonical way.
(See Figure 1.) The Sierpinski is the attractor (or invariant set) of S and D, which consists of all points S(T ) for T ∈ Σ ∞ .
The main objective of [57] was to relate the dimension and strong dimension of each point S(T ) ∈ R n in a self-similar fractal to the corresponding dimensions of the coding sequence T . As it turned out, the algorithmic dimensions in Σ ∞ had to be extended in order to achieve this.
The similarity dimension of an IFS S = (S 0 , . . . , S k−1 ) with contraction ratios c 0 , . . . , c k−1 ∈ (0, 1) is the unique solution sdim(S) = s of the equation The similarity probability measure of S is the probability measure on Σ that is implicit in (13), i.e., the function π S : for each i ∈ Σ . If the contraction ratios of S are all the same, then π S is the uniform probability measure on Σ , but this is not generally the case. We extend π S to the domain Σ * by setting for each w ∈ Σ * . We define the Shannon S-self-information of each string w ∈ Σ * to be the quantity Finally, we define the dimension of a sequence T ∈ Σ ∞ with respect to the IFS S to be Similarly, the strong dimension of T with respect to S is The dimension (17) is a special case of an algorithmic Billingsley dimension [6,99,12]. These are treated more generally in [57].
A set F ⊆ R n is a computably self-similar fractal if it is the attractor of some D and S as above such that the contracting similarities S 0 , . . . , S k−1 are all computable in the sense of computable analysis.
The following theorem gives a complete analysis of the dimensions of points in computably self-similar fractals.  [57]) If F ⊆ R n is a computably self-similar fractal and S is an IFS testifying to this fact, then, for all points x ∈ F and all coding sequences T ∈ Σ ∞ for x, and The proof of Theorem 3.2 is nontrivial. It combines some very strong coding properties of iterated function systems with some geometric Kolmogorov complexity arguments.
The following characterization of continuous functions on the reals is one of the oldest and most beautiful theorems of computable analysis. [45,46]) A function f : R n → R m is continuous if and only if there is an oracle A ⊆ N relative to which f is computable.
Using Lacombe's theorem it is easy to derive the classical analysis of self-similar fractals (which need not be computably self-similar) from Theorem 3.2.
Corollary 3.4. (Moran [73], Falconer [24]) For every self-similar fractal F ⊆ R n and every IFS S that generates F, Proof. Let F and S be as given. By Lacombe's theorem there is an oracle A ⊆ N relative to which S is computable. It follows by a theorem by Kamo and Kawamura [41] that the set F is Π 0 1 relative to A, whence the relativization of (11) tells us that We then have Intuitively, Theorem 3.2 is stronger than its Corollary 3.4, because Theorem 3.2 gives a complete account of "where the dimension comes from".

Dimension Level Sets
The dimension level sets DIM α and DIM α str defined in (4) and (5) have been the focus of several investigations. It was shown in [53,1] that, for all 0 ≤ α ≤ n, Hitchcock, Terwijn, and the first author [33] investigated the complexities of these dimension level sets from the viewpoint of descriptive set theory. Following standard usage [74], we write Σ 0 k and Π 0 k for the classes at the kth level (k ∈ Z + ) of the Borel hierarchy of subsets of R n . That is, Σ 0 1 is the class of all open subsets of R n , each Π 0 k is the class of all complements of sets in Σ 0 k , and each Σ 0 k+1 is the class of all countable unions of sets in Π 0 k . We also write Σ 0 k and Π 0 k for the classes of the kth level of Kleene's arithmetical hierarchy of subsets of R n . That is, Σ 0 1 is the class of all computably open subsets of R n , each Π 0 k is the class of all complements of sets in Σ 0 k , and each Σ 0 k+1 is the class of all effective (computable) unions of sets in Π 0 k . Recall that a real number α is ∆ 0 2 -computable if there is a computable function f : N → Q such that lim k→∞ f (k) = α.
The following facts were proven in [33].
Weihrauch and the first author [59] investigated the connectivity properties of sets of the form where I ⊆ [0, n] is an interval. After making the easy observation that each of the sets DIM [0,1) and DIM (n−1,n] is totally disconnected, they proved that each of the sets DIM [0,1] and DIM [n−1,n] is path-connected. These results are especially intriguing in the Euclidean plane, where they say that extending either of the sets DIM [0,1) and DIM (1,2] to include the level set DIM 1 transforms it from a totally disconnected set to a path-connected set. This suggests that DIM 1 is somehow a very special subset of R 2 . Turetsky [97] investigated this matter further and proved that DIM 1 is a connected set in R n . He also proved that DIM [0,1) ∪ DIM (1,2] is not a path-connected subset of R 2 .

Dimensions of Points on Lines
Since effective dimension is a pointwise property, it is natural to study the dimension spectrum of a set E ⊆ R n , i.e., the set sp(E) = {dim(x) | x ∈ E }. This study is far from obvious even for sets as apparently simple as straight lines. We review in this section the results obtained so far, mainly for the case of straight lines in R 2 .
As noted in section 3.4, the set of points in R 2 of dimension exactly one is connected, while the set of points in R 2 with dimension less than 1 is totally disconnected. Therefore every line in R 2 contains a point of dimension 1. Despite the surprising fact that there are lines in every direction that contain no random points [55], the first author and N. Lutz have shown that almost every point on any line with random slope has dimension 2 [56]. Still all these results leave open fundamental questions about the structure of the dimension spectra of lines, since they don't even rule out the possibility of a line having the singleton set {1} as its dimension spectrum.
Very recently this latest open question has been answered in the negative. N. Lutz and Stull [63] have proven the following general lower bound on the dimension of points on lines in R 2 .
Taking x 1 = 0 and x 2 a Martin-Löf random real relative to (a, b), Theorem 3.5 gives us two points in the line, (0, b) and (x 2 , ax 2 + b), whose dimensions differ by at least one, so the dimension spectrum cannot be a singleton.
We briefly sketch here the main intuitions behind the (deep) proof of Theorem 3.5, fully based on algorithmic information theory. Theorem 3.5's aim is to connect The proof is based on the property that says that under the following two conditions There is an extra ingredient to finish this intuition.While condition (ii) can be shown to hold in general, condition (i) can only be proven in a particular relativized world whereas the conclusion of the theorem still holds for every oracle.
N. Lutz and Stull [62] have also shown that the dimension spectrum of a line is always infinite, proving the following two results. The first theorem proves that if dim(a, b) = Dim(a, b) then the corresponding line contains a length one interval.

Mutual and Conditional Dimensions
Just as the dimension of a point x in Euclidean space is the asymptotic density of the algorithmic information in x, the mutual dimension between two points x and y in Euclidean spaces is the asymptotic density of the algorithmic information shared by x and y. In this section, we survey this notion and the data processing inequalities, which estimate the effect of computable functions on mutual dimension. We also survey the related notion of conditional dimension.

Mutual Dimensions
The mutual (algorithmic) information between two rational points p ∈ Q m and q ∈ Q n is I(p : q) = K(p) − K(p|q).
This notion, essentially due to Kolmogorov [44], is an analog of mutual entropy in Shannon information theory [86,18,49]. Intuitively, K(p|q) is the amount of information in p not contained in q, so I(p : q) is the amount of information in p that is contained in q. It is well known [49] that, for all p ∈ Q m and q ∈ Q n , in the sense that the magnitude of the difference between the two sides of (2) is o(min{K(p), K(q)}). This fact is called symmetry of information, because it immediately implies that I(p : q) ≈ I(q : p).
The ideas in the rest of this section were introduced by Case and the first author [13]. In the spirit of (1) they defined the mutual information between sets E ⊆ R m and F ⊆ R n to be I(E : F) = min {I(p : q) | p ∈ Q m ∩ E and q ∈ Q n ∩ F } .
This is the amount of information that rational points p and q must share in order to be in E and F, respectively. Note that, for all E 1 , E 2 ⊆ R m and F 1 , F 2 ⊆ R n , The mutual information between two points x ∈ R m and y ∈ R n at precision r ∈ N is I r (x : y) = I(B 2 −r (x) : B 2 −r (y)).
This is the amount of information that rational approximations of x and y must share, merely due to their proximities (distance less than 2 −r ) to x and y.
In analogy with (1) and (2), the lower and upper mutual dimensions between points x ∈ R m and y ∈ R m are mdim(x : y) = lim inf r→∞ I r (x : y) r and Mdim(x : y) = lim sup r→∞ I r (x : y) r , respectively.
The following theorem shows that the mutual dimensions mdim and Mdim have many of the properties that one should expect them to have. The proof is involved and includes a modest generalization of Levin's coding theorem [47,48].  [13]) For all x ∈ R m and y ∈ R n , the following hold. 9. If x and y are independently random, then Mdim(x : y) = 0.
The expressions dim(x, y) and Dim(x, y) in 7 and 8 above refer to the dimensions of the point (x, y) ∈ R m+n . In 9 above, x and y are independently random if (x, y) is a Martin-Löf random point in R m+n .
More properties of mutual dimensions may be found in [13,14].

Data Processing Inequalities
The data processing inequality of Shannon information theory [18] says that, for any two probability spaces X and Y , any set Z, and any function f : X → Z, i.e., the induced probability space f (X) obtained by "processing the information in X through f " has no greater mutual entropy with Y than X has with Y . More succintly, f (X) tells us no more about Y than X tells us about Y . The data processing inequality of algorithmic information theory [49] says that, for any computable partial function f : {0, 1} * → {0, 1} * , there is a constant c f ∈ N (essentially the number of bits in a program that computes f ) such that, for all strings x ∈ dom f and y ∈ {0, 1} * , That is, modulo the constant c f , f (x) contains no more information about y than x contains about y. The data processing inequality for the mutual dimension mdim should say that every nice function f : R m → R n has the property that, for all x ∈ R m and y ∈ R k , mdim( f (x) : y) ≤ mdim(x : y).
But what should "nice" mean? A nice function certainly should be computable in the sense of computable analysis [10,43,100]. But this is not enough. For example, there is a function f : R → R 2 that is computable and space-filling in the sense that [0, 1] 2 ⊆ range f [83,17]. For such a function, choose x ∈ R such that dim( f (x)) = 2, and let y = f (x). Then ≥ mdim(x : y), so (6) fails. Intuitively, the above failure of (6) occurs because the function f is extremely sensitive to its input, a property that " nice" functions do not have. A function f : The following data processing inequalities show that computable Lipschitz functions are "nice". and Mdim( f (x) : y) ≤ Mdim(x : y) Several more theorems of this type and applications of these appear in [13].

Conditional Dimensions
A comprehensive theory of the fractal dimensions of points in Euclidean spaces requires not only the dimensions dim(x) and Dim(x) and the mutual dimensions mdim(x : y) and Mdim(x : y), but also the conditional dimensions dim(x|y) and Dim(x|y) formulated by the first author and N. Lutz [56]. We briefly describe these formulations here. The conditional Kolmogorov complexity K(p|q), defined for rational points p ∈ Q m and q ∈ Q n , is lifted to the conditional dimensions in the following four steps.
1. For x ∈ R m , q ∈ Q n , and r ∈ N, the conditional Kolmogorov complexity of x at precision r given q iŝ 2. For x ∈ R m , y ∈ R n , and r, s ∈ N, the conditional Kolmogorov complexity of x at precision r given y at precision s is 3. For x ∈ R m , y ∈ R n , and r ∈ N, the conditional Kolmogorov complexity of x given y at precision r is K r (x|y) = K r,r (x|y). Steps 1, 2, and 4 of the above lifting are very much in the spirit of what has been done in section 2, 3.1, and 4.1 above.
Step 3 appears to be problematic, because using the same precision bound r for both x and y makes the definition seem arbitrary and "brittle". However, the following result shows that this is not the case. r .
The following result is useful for many purposes.
Theorem 4.4. (chain rule for K r ) For all x ∈ R m and y ∈ R n , An oracle for a point y ∈ R n is a function g : N → Q n such that, for all s ∈ N, |g(s) − y| ≤ 2 −s . The Kolmogorov complexity of a rational point p ∈ Q m relative to a point y ∈ R n is K y (p) = max {K g (p) | g is an oracle for y } , where K g (p) is the Kolmogorov complexity of p when the universal machine has access to the oracle g. The purpose of the maximum here is to prevent K y (p) from using oracles g that code more than y into their behaviors. For x ∈ R m and y ∈ R n , the dimension dim y (x) relative to y is defined from K y (p) exactly as dim(x) was defined from K(p) in Sections 2 and 3.1 above. The relativized strong dimension Dim y (x) is defined analogously.
The following result captures the intuition that conditioning on a point y is a restricted form of oracle access to y.  and Mdim(x : y) ≤ Dim(x) − dim(x|y).

The Point-to-Set Principle
Many of the most challenging problems in geometric measure theory are problems of establishing lower bounds on the classical fractal dimensions dim H (E) and dim P (E) for sets E ⊆ R n . Although such problems seem to involve global properties of the sets E and make no mention of algorithms, the dimensions of points have recently been used to prove new lower bound results for classical fractal dimensions.
The key to these developments is the following pair of theorems of the first author and N. Lutz.
The relativized dimensions dim A (x) and Dim A (x) here are defined by substituting (1) and (2). It is to be emphasized that these two theorems completely characterize dim H (E) and dim P (E) for all sets E ⊆ R n . These characterizations are called point-to-set principles because they enable one to use a lower bound on the relativized dimension of a single, judiciously chosen point x ∈ E to establish a lower bound on the classical dimension of the set E itself. More precisely, for example, Theorem 5.1 says that, in order to prove a lower bound dim H (E) ≥ α, it suffices to show that, for every oracle A ⊆ N and every ε > 0, there is a point x ∈ E such that dim A (x) ≥ α − ε. In some cases, it can in fact be shown that, for every oracle A ⊆ N, there is a point x ∈ E such that dim A (x) ≥ α. While the arbitrary oracle A is essential for the correctness of such proofs, the discussion below shows that its presence has not been burdensome in applications to date.

Plane Kakeya Sets
The first application of the point-to-set principle was not a new theorem, but rather a new, information-theoretic proof of an old theorem. We describe this proof here because it illustrates the intuitive power of the point-to-set principle.
A Kakeya set in R n is a set K ⊆ R n that contains a unit segment in every direction. Sometime before 1920, Besicovitch [4,5] proved the then-surprising existence of Kakeya sets of Lebesgue measure 0 in R n for all n ≥ 2 and asked whether Kakeya sets in R 2 can have dimension less than 2 [20]. The famous Kakeya conjecture (in its most commonly stated form) asserts a negative answer to this and the analogous questions in higher dimensions. That is, the Kakeya conjecture says that every Kakeya set in a Euclidean space R n has Hausdorff dimension n. This conjecture holds trivially for n = 1 and Davies [20] proved that it holds for n = 2. The Kakeya conjecture remains an important open problem for n ≥ 3 [101,95].
Our objective here is to sketch the new proof by the first author and N. Lutz [56] of Davies's theorem, that the Kakeya conjecture holds in the Euclidean plane R 2 . This proof uses the following lower bound on the dimensions of points in a line y = mx + b.
We do not prove this lemma here, but note that the proof relativizes, so the lemma holds relative to every oracle A ⊆ N.
To prove Davies's theorem, let K ⊆ R 2 be a Kakeya set. By the point-to-set principle, fix A ⊆ N such that Fix m ∈ [0, 1] such that dim A (m) = 1.
(This holds for any m that is random relative to A.) Since K is Kakeya, there is a unit segment L ⊆ K of slope m. Let (x 0 , y 0 ) be the left endpoint of L, let q ∈ Q ∩ [x 0 , x 0 + 1/2], and let L ′ be the unit segment of slope m whose endpoint is (x 0 − q, y 0 ). Then L ′ crosses the y-axis at the point b = mq + y 0 . By Lemma 5.3 and (Such x exists, because almost every x ∈ [0, 1/2] satisfies (6) and (7).) In the language of section 5.1, our "judiciously chosen point" is (x + q, mx + b) ∈ L ⊆ K, and the point-to-set principle tells us that it suffices to prove that But this is now easy. Since q is rational, (7) and two applications of the chain rule (7) tell us that

whence (5) and (6) tell us that (8) holds.
This information-theoretic proof of Davies can be summarized in very intuitive terms: Because K is Kakeya, it contains a unit segment L whose slope m has dimension 1 relative to A. A rational shift of L to a unit segment L ′ crosses the y-axis at some point b. Lemma 5.3 then gives us a point (x, mx + b) on L ′ that has dimension 2 relative to A. The point on L from which (x, mx + b) was shifted lies in K and also has dimension 2 relative to A, so K has Hausdorff dimension 2.
The following two sections discuss recent uses of this method to prove new theorems in classical fractal geometry.

Intersections and Products of Fractals
We now consider two fundamental, nontrivial, textbook theorems of fractal geometry. The first, over thirty years old and called the intersection formula, concerns the intersection of one fractal with a random translation of another fractal.
Theorem 5.4. (Kahane [40], Mattila [66,67]) For all Borel sets E, F ⊆ R n and almost every z ∈ R n , The second theorem, over sixty years old and called the product formula, concerns the product of two fractals.
Theorem 5.5. (Marstrand [64]) For all E ⊆ R n and F ⊆ R n , In a recent breakthrough, algorithmic dimension was used to prove the following extension of the intersection formula from Borel sets to all sets. We include the simple (given the machinery that we have developed) and instructive proof here.
Theorem 5.6. (N. Lutz [61]) For all sets E, F ⊆ R n and almost every z ∈ R n , Proof. Let E, F ⊆ R n and z ∈ R n . The theorem is trivially affirmed if F + z is disjoint from E, so assume not. By the point-to-set principle, fix an oracle A ⊆ N such that Let ε > 0. Since E ∩ (F + z) = / 0, the point-to-set principle tells us that there is a point x ∈ E ∩ (F + z) satisfying Now (x, x − z) ∈ E × F, so (10), Theorem 3.5, Lemma 4.5, and (11) tell us that Since ε is arbitrary here, it follows that Since almost every z ∈ R n is Martin-Löf random relative to A and hence satisfies dim A (z) = n, this affirms the theorem.
The paper [61] shows that the same method gives a new proof of the analog of Theorem 5.6 for packing dimension. This result was already known to hold for all sets E and F [26], but the new proof makes clear what a strong duality between Hausdorff and packing dimensions is at play in the intersection formulas.
The paper [61] also gives a new, algorithmic proof of the following known extension of Theorem 5.5.
Theorem 5.7. (Marstrand [64], Tricot [96]) For all E ⊆ R m and F ⊆ R n , This new proof is much simpler than previously known proofs of Theorem 5.7, roughly as simple as previously known proofs of the restriction of Theorem 5.7 to Borel sets. The new proof is also quite natural, using the point-to-set principle to derive Theorem 5.7 from the formally similar Theorem 4.7.

Generalized Furstenberg Sets
For α ∈ (0, 1], a plane set E ⊆ R 2 is said to be of Furstenberg type with parameter α or, more simply, α-Furstenberg, if, for every direction e ∈ S 1 (where S 1 is the unit circle in R 2 ), there is a line L e in direction e such that dim H (L e ∩ E) ≥ α.
According to Wolff [101], the following well-known bound is probably due to Furstenberg and Katznelson.
Note that every Kakeya set in the plane is 1-Furstenberg (since it contains a line segment, which has Hausdorff dimension 1, in every direction e ∈ S 1 ), so Davies's theorem follows from the case α = 1 of Theorem 5.8. It is an open question -one with connections to Falconer's distance conjecture [42] and Kakeya sets [101]whether Theorem 5.8 can be improved.
In 2012, Molter and Rela generalized α-Furstenberg sets in a natural way. For α, β ∈ (0, 1], a set E ⊆ R 2 is (α, β )-generalized Furstenberg if there is a set J ⊆ S 1 such that dim H (J) ≥ β and, for every e ∈ J, there is a line L e in direction e such that dim H (L e ∩ E) ≥ α. They then proved the following lower bound.

Beyond Self-Similarity
In previous sections we have analyzed the dimension of points in self-similar fractals, but interesting natural examples need more elaborated concepts that combine self-similarity with random selection. In [31] Gu, Moser, and the authors started the more challenging task of analyzing the dimensions of points in random fractals. They focused on fractals that are randomly selected subfractals of a given selfsimilar fractal.
Let F ⊆ R n be a computably self-similar fractal as defined in section 3.3, with S = (S 0 , . . . , S k−1 ) the corresponding IFS, and Σ = {0, . . . , k − 1}. Recall that each point x ∈ F has a coding sequence T ∈ Σ ∞ meaning that the point x is obtained by applying the similarities coded by the successive symbols in T . We are interested in certain randomly selected subfractals of the fractal F.
The specification of a point in such a subfractal can be formulated as the outcome of an infinite two-player game between a selector that selects the subfractal and a coder that selects a point within the subfractal. Specifically, the selector selects r out of the k similarities and this choice depends on the coder's earlier choices, that is, a selector is a function σ : Γ * → [Σ ] r where [Σ ] r is the set of all r-element subsets of Σ , alphabet Γ = {0, . . . , r − 1} and each element in Γ * represents a coder's earlier history. A coder is a sequence U ∈ Γ ∞ , that is, the coder is selecting a point in the subfractal by repeatedly choosing a similarity out of the r previously picked by the selector. Once a selector σ and a coder U have been chosen, the outcome of the selector-coder game is a point determined by the sequence σ * U ∈ Σ ∞ , that can be precisely defined as Each selector σ specifies (selects) the subfractal F σ of F consisting of all points with coding sequence T for which T is an outcome of playing σ against some coder, The focus of [31] is in randomly selected subfractals of F, by which we mean subfractals F σ of F for which the selector σ is random with respect to some probability measure. That is, we are interested in the case where the coder is playing a "game against nature" (in order to make precise the idea of algorithmically random selector each selector σ : Γ * → [Σ ] r is identified with its characteristic sequence Gu et al. determine the dimension spectra of a wide class of such randomly selected subfractals, showing that each such fractal has a dimension spectrum that is a closed interval whose endpoints can be computed or approximated from the parameters of the fractal. In general, the maximum of the spectrum is determined by the degree to which the coder can reinforce the randomness in the selector, while the minimum is determined by the degree to which the coder can cancel randomness in the selector. This randomness cancellation phenomena has also arisen in other contexts, notably dimension spectra of random closed sets [2,21] and of random translations of the Cantor set [22]. The main result in [31] concerns subfractals that are similarity random, that is, F σ defined by a selector σ that isπ S -random. Herê π S is the natural extension of π s , the similarity probability measure on Σ defined in Section 3.3. Theorem 6.1. [31] For every similarity random subfractal F σ of F, the dimension spectrum sp(F σ ) is an interval satisfying [s * log(k−1)−log(r−1+A(k−r)) In particular, if all the contraction ratios of F have the same value c, then every similarity-random (i.e., uniformly random) subfractal F σ of F has dimension spectrum where s * = sdim(S) = (log k)/(log 1 c ). Many challenging open questions remain concerning the analysis of the dimension of points in more general versions of random fractals, both by completing the results in [31] to random selectors for different probability measures and by considering generalizations such as self-affine fractals and fractals with randomly chosen contraction ratios.

Beyond Euclidean Spaces
While Euclidean space has a very well-behaved metric based on a Borel measure µ, where for instance s-Hausdorff measure coincides with µ for s = 1, this is not the case for other metric spaces. Since both Hausdorff and packing dimension can be defined in any metric space, the second author has considered in [70] the extension of algorithmic dimension to a large class of separable metric spaces, the class of spaces with a computable nice cover. This extension includes an algorithmic information characterization of constructive dimension, based on the concept of Kolmogorov complexity of a point at a certain precision, which is an extension of the concept presented in section 2 for Euclidean space.

Beyond Computability
Resource-bounded dimension, introduced in [52] by the first author, has been a very fruitful tool in the quantitative study of complexity classes, see [35,54] for the main results. Many of the main complexity classes have a suitable resource bound for which the corresponding dimension is adequate for the class, since it has maximal value for the whole class.
The development of resource-bounded dimension was based on a characterization of Hausdorff dimension in terms of betting strategies, imposing different complexity constraints on those strategies to obtain the different resource-bounded dimensions. Contrary to the case of computability constraints introduced in section 3, many important resource-bounds such as polynomial time dimension do not have corresponding algorithmic information characterizations (although more elaborated compression algorithms characterizations have been obtained in [50,38]).
In fact the study of gambling under very low complexity constraints, finite-state computability, has been studied at least since the seventies [85,27] and the corresponding effective dimension, finite-state dimension, was studied by Dai, Lathrop, and the two authors [19] where finite-state dimension is characterized in terms of finite-state compression.
For the definition of resource-bounded dimension, a class of languages C is represented via characteristic sequences as a set of infinite binary sequences C ⊆ {0, 1} ∞ . Using binary representation each language can be seen as a real number in [0, 1] and resource-bounded dimension as a tool in Euclidean space. Resourcebounded dimension has a natural extension Σ ∞ for other finite alphabets Σ and the first question is therefore whether the choice of alphabet is relevant for the study of Euclidean space. A satisfactory answer is given in [36] where it is proven that polynomial-time dimension is invariant under base change, that is, for every base b and set X ⊆ R the set of base-b-representations of all elements in X has a polynomial-time dimension independent of b.
Finite-state dimension is not closed under base change, but its connections with number theory are deep. Borel introduced normal numbers in [8], defining a real number α to be Borel normal in base b if for every finite sequence w of base-b digits, the asymptotic, empirical frequency of w in the base-b expansion of α is b −|w| . There is a tight relationship of Borel-normality and finite-state dimension, since a real number is normal in base b iff its base b representation is a finite-state dimension 1 sequence [85,9]. It is known [15,84] that there are numbers that are normal in one base but not in another, so the nonclosure under base change property of finite-dimension is a corollary of these results. Absolutely normal numbers are real numbers that are normal in every base, so they correspond to real numbers whose base-b representation has finite-dimension 1 for every base b, this characterization has been used in very effective constructions of absolutely normal numbers [3,58]. It is natural to ask whether there are real numbers for which the finite-state dimension of its base-b representations is strictly between 0 and 1 and does not depend on the base b.

Beyond Fractals
This chapter's primary focus is the role of algorithmic fractal dimensions in fractal geometry. However, it should be noted that fractal geometry is only a part of geometric measure theory, and that algorithmic methods may shed light on many other aspects of geometric measure theory.
Many questions in geometric measure theory involve rectifiability [28]. The simplest case of this classical notion is the rectifiability of curves. A curve in R n is a continuous function f : [0, 1] → R n . The length of a curve f is where the supremum is taken over all dissections a of [0, 1], i.e., all a = (a 0 , . . . , a k ) with 0 = a 0 < a 1 < . . . < a k = 1. Note that length( f ) is the length of the actual path traced by f , which may "retrace" parts of its range. (In fact, there are computable curves f for which every computable curve g with the same range must do unboundedly many such retracings [30].) A curve f is rectifiable if length( f ) < ∞.
Gu and the authors [29] posed the fanciful question, " Where can an infinitely small nanobot go?" Intuitively, the nanobot is the size of a Euclidean point, and its motion is algorithmic, so its trajectory must be a curve f : [0, 1] → R n that is computable in the sense of computable analysis [100]. Moreover, the nanobot's trajectory f should be rectifiable. This last assumption, aside from being intuitively reasonable, prevents the question from being trivialized by space-filling curves [83,17].
The above considerations translate our fanciful question about a nanobot to the following mathematical question. Which points in R n (n ≥ 2) lie on rectifiable computable curves? In honor of an anonymous, poetic reviewer who called the set of all such points "the beaten path", we write BP (n) for the set of all points in R n that lie on rectifiable computable curves. The objective of [29] was to characterize the elements of BP (n) .
A few preliminary observations on the set BP (n) are in order here. Every computable point in R n clearly lies in BP (n) , so BP (n) is a dense subset of R n . It is also easy to see that BP (n) is path-connected. On the other hand, the ranges of rectifiable curves have Hausdorff dimension 1 [25] and there are only countably many computable curves, so BP (n) is a countable union of sets of Hausdorff dimension 1 and hence has Hausdorff dimension 1. Since n ≥ 2, this implies that most points in R n do not lie on the beaten path BP (n) .
For each rectifiable computable curve f , the set range f is a computably closed, i.e., Π 0 1 , subset of R n . By the preceding paragraph and Hitchcock's correspondence principle (11), it follows that cdim(BP (n) ) = 1, whence every point x ∈ BP (n) satisfies dim(x) ≤ 1. This is a necessary, but not sufficient condition for membership in BP (n) , because the complement of BP (n) contains points of arbitrarily low dimension [29]. Characterizing membership in BP (n) thus requires algorithmic methods to be extended beyond fractal dimensions.
The "analyst's traveling salesman theorem" of geometric measure theory characterizes those subsets of Euclidean space that are contained in rectifiable curves. This celebrated theorem was proven for the plane by Jones [39] and extended to high-dimensional Euclidean spaces by Okikiolu [76]. The main contribution of [29] is to formulate the notion of a computable Jones constriction, an algorithmic version of the infinitary data structure implicit in the analyst's traveling salesman theorem, and to prove the computable analyst's traveling salesman theorem, which says that a point in Euclidean space lies on the beaten path BP (n) if and only if it is "permitted" by some computable Jones constriction.
The computable analysis of points in rectifiable curves has continued in at least two different directions. In one direction, Rettinger and Zheng have shown (answering a question in [29]) that there are points in BP (n) that do not lie on any computable curve of computable length [78] and extended this to obtain a four-level hierarchy of simple computable planar curves that are point-separable in the sense that the sets of points lying on curves of the four types are distinct [102]. In another direction, McNicholl [71] proved that there is a point on a computable arc (a set computably homeomorphic to [0, 1]) that does not lie in BP (n) . In the same paper, McNicholl used a beautiful geometric priority argument to prove that there is a point on a computable curve of computable length that does not lie on any computable arc.
It is apparent from the above results that algorithmic methods will have a great deal more to say about rectifiability and other aspects of geometric measure theory.